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

外部連結

• 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）.