The Algorithm BSTW is a
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
, named after its designers, Bentley,
Sleator,
Tarjan and Wei in 1986.
BSTW is a dictionary-based algorithm that uses a
move-to-front transform
The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually ...
to keep recently seen dictionary entries at the front of the dictionary. Dictionary references are then encoded using any of a number of encoding methods, usually
Elias delta coding
Elias δ code or Elias delta code is a universal code encoding the positive integers developed by Peter Elias.
Encoding
To code a number ''X'' ≥ 1:
# Let ''N'' = ⌊log2 ''X''⌋; be the highest power of 2 in ''X'', so 2''N'' ≤ ' ...
or
Elias gamma coding.
References
This algorithm was published in the following paper: "A Locally Adaptive Data Compression Scheme", Communications of the ACM, 1986, volume 29 number 4, pp. 320–330.
A related idea was published in Ryabko, B. Ya. "Data compression by means of a book stack", Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
The original name of this code is "book stack". The history of discovery of the book stack (or
move-to-front
The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually j ...
) code can be found here: Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Comments to:
A locally adaptive data compression scheme by J. L. Bentley, D. D. Sleator, R. E. Tarjan and V. K. Wei. Comm. ACM 30 (1987), no. 9, 792–794.
External links
Lossless compression algorithms
Data compression
{{algorithm-stub