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).
|