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 compression ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

, 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 ju ...

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'' ≤ '' ...

Elias gamma coding Elias γ code or Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand. Encoding To code a number ''x'' � ...

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) 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 {{algorithm-stub