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
- ^ 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. S2CID 5854590.
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
- Algorithm BSTW
- v
- t
- e
Data compression methods
| Entropy type |
|
|---|---|
| Dictionary type | |
| Other types | |
| Hybrid |
| Transform type | |
|---|---|
| Predictive type |
| Concepts | |
|---|---|
| Codec parts |
| Concepts | |
|---|---|
| Methods |
| Concepts | |
|---|---|
| Codec parts |
- Compressed data structures
- Entropy
- Information theory
- Kolmogorov complexity
- Prefix code
- Quantization
- Rate–distortion
- Redundancy
- Symmetry
- Smallest grammar problem
Compression formats- Compression software (codecs)
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e
