跳转到内容

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

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 压缩过程
序列 栈表 说明 输出 操作 
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

外部链接

[编辑]
检索自“https://zh.wikipedia.org/w/index.php?title=Move-to-front变换&oldid=66096303”