Move-to-front变换
MTF（Move-To-Front）是一种数据编码方式，作为一个额外的步骤，用于提高数据压缩技术效果。MTF主要使用的是数据“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现。
MTF的主要思想
（1）首先维护一个文本字符集大小的栈表，“recently used symbols”（最近访问过的字符），其中每个不同的字符在其中占一个位置，位置从0开始编号。（2）扫描需要重新编码的文本数据，对于每个扫描到的字符，使用该字符在“recently used symbols”中的index替换，并将该字符提到“recently used symbols”的栈顶的位置(index为0的位置)。重复上一步骤，直到文本扫描结束。
MTF的压缩过程
以字符串“annbaa”为例（“annbaa”在这里为字符串“banana”经过BWT变换后的结果Bzip2 Burrows-Wheeler变换）。基于recently used symbols，设立一个栈表“abcdefghijklmnopqrstuvwxyz”。
| Move-To-Front 压缩过程 | |||||
|---|---|---|---|---|---|
| 迭代 | 序列 | 栈表 | 说明 | ||
a n n b a a |
0 |
abcdefghijklmnopqrstuvwxyz |
Index of a = 0; record 0; a is on the top | ||
MTF的压还原过程
以序列“0, 13, 0, 2, 2, 0”为例（“0, 13, 0, 2, 2, 0”在这里为字符串“aaabnn”经过MVT压缩后的结果）。基于栈表“abncdefghijklmopqrstuvwxyz”，n的指数为0，z的指数为25。
| Move-To-Front 压缩过程 | |||||
|---|---|---|---|---|---|
| 序列 | 栈表 | 说明 | 输出 | 操作 | |
0,13,0,2,2,0 |
abncdefghijklmopqrstuvwxyz |
Index of 0 = a; record a |
a |
move a to the 0 | |
外部链接
- J. L. Bentley; D. D. Sleator; R. E. Tarjan; V. K. Wei. A Locally Adaptive Data Compression Scheme. Communications of the ACM. 1986, 29 (4) [2017-03-07]. doi:10.1145/5684.5688. （原始内容存档于2020-02-19）.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
