跳至內容

Move-to-front變換

維基百科,自由的百科全書

MTFMove-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

外部連結