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 压缩过程, 迭代 ...
Move-To-Front 压缩过程
|
迭代
|
序列
|
栈表
|
说明
|
a n n b a a
a n n b a a
a n n b a a
a n n b a a
a n n b a a
a n n b a a
结果
|
0
0,13
0,13,0
0,13,0,2
0,13,0,2,2
0,13,0,2,2,0
0,13,0,2,2,0
|
abcdefghijklmnopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
bnacdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
|
Index of a = 0; record 0; a is on the top
Index of n = 13; record 13; move n to the top
Index of n = 0; record 0; n is on the top
Index of b = 2; record 2; move b to the top
Index of a = 2; record 2; move a to the top
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 压缩过程, 序列 ...
Move-To-Front 压缩过程
|
序列
|
栈表
|
说明
|
输出
|
操作
|
0,13,0,2,2,0
0,13,0,2,2
0,13,0,2
0,13,0
0,13
0
结果
|
abncdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
bnacdefghijklmopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
|
Index of 0 = a; record a
Index of 0 = a; record a
Index of 0 = b; record b
Index of 0 = n; record n
Index of 0 = n; record n
Index of 0 = a; record a
|
a
a a
b a a
n b a a
n n b a a
a n n b a a
a n n b a a
|
move a to the 0
move a to the 2
move b to the 2
move n to the 0
move n to the 13
move a to the 0
|
关闭
外部链接