Algorithm BSTW

The Algorithm BSTW is a data compression algorithm, named after its designers, Bentley, Sleator, Tarjan and Wei in 1986.[1] BSTW is a dictionary-based algorithm that uses a move-to-front transform 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 or Elias gamma coding.

References
  1. Bentley, Jon Louis; Sleator, Daniel D.; Tarjan, Robert E.; Wei, Victor K. (1986). "A locally adaptive data compression scheme". Communications of the ACM. 29 (4): 320–330. CiteSeerX 10.1.1.69.807. doi:10.1145/5684.5688.

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.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.