Burrows–Wheeler Transform - Optimization


A number of optimizations can make these algorithms run more efficiently without changing the output. In BWT, there is no need to represent the table in either the encoder or decoder. In the encoder, each row of the table can be represented by a single pointer into the strings, and the sort performed using the indices. Some care must be taken to ensure that the sort does not exhibit bad worst-case behavior: Standard library sort functions are unlikely to be appropriate. In the decoder, there is also no need to store the table, and in fact no sort is needed at all. In time proportional to the alphabet size and string length, the decoded string may be generated one character at a time from right to left. A "character" in the algorithm can be a byte, or a bit, or any other convenient size.

There is no need to have an actual 'EOF' character. Instead, a pointer can be used that remembers where in a string the 'EOF' would be if it existed. In this approach, the output of the BWT must include both the transformed string, and the final value of the pointer. That means the BWT does expand its input slightly. The inverse transform then shrinks it back down to the original size: it is given a string and a pointer, and returns just a string.

A complete description of the algorithms can be found in Burrows and Wheeler's paper, or in a number of online sources.

Read more about this topic:  Burrows–Wheeler Transform

Other articles related to "optimization":

Mobile Robotics Laboratory At IISc - Projects Undertaken - Glowworm Swarm Optimization (GSO): A Bio-inspired Optimization Paradigm
... The glowworm swarm optimization (GSO) algorithm is an optimization technique developed for simultaneous capture of multiple optimums of multi-modal ...
Optimization - Notation - Optimal Input Arguments
... Similarly, or equivalently represents the pair (or pairs) that maximizes (or maximize) the value of the objective function, with the added constraint that x lie in the interval (again, the actual maximum value of the expression does not matter) ... In this case, the solutions are the pairs of the form (5, 2kπ) and (−5,(2k+1)π), where k ranges over all integers ...
Sequential Minimal Optimization
... Sequential minimal optimization (SMO) is an algorithm for efficiently solving the optimization problem which arises during the training of support vector machines ...
List Of Optimization Software - Free and Open Source Software
... Name License Brief info ADMB BSD nonlinear optimization framework, using automatic differentiation ASCEND GPL mathematical modelling system COIN-OR SYMPHONY GPL integer ... MATLAB Toolbox for solving linear, nonlinear, continuous and discrete optimization problems ...