> mtf | move | front <
// Move-to-Front —— 為更佳壓縮效果而動態重排清單
自我調適
會自動適應資料中的區域模式。
善用區域性
最近出現的符號擁有較小的索引，壓縮率更佳。
bzip2 的一部分
在 bzip2 壓縮流程中，通常用於 BWT 之後的階段。
>> 技術說明
MTF 的運作方式:
MTF 維護一個包含所有可能符號的清單。當編碼某個符號時，會輸出該符號在清單中的目前位置，然後將它移到清單最前端。如此一來，最近使用的符號會集中在前端、索引較小，而後續的熵編碼就能更有效率地壓縮資料。
編碼範例:
文字："banana" 初始清單：[a,b,c,d,...] "b"：索引 1，將 b→前端 [b,a,c,d,...] "a"：索引 1，將 a→前端 [a,b,c,d,...] "n"：索引 13，將 n→前端 [n,a,b,c,...] "a"：索引 1，將 a→前端 [a,n,b,c,...] "n"：索引 1，將 n→前端 [n,a,b,c,...] "a"：索引 1，將 a→前端 [a,n,b,c,...] 輸出：[1,1,13,1,1,1]
為什麼要使用 MTF:
- >提升區域重複資料的可壓縮性
- >與 BWT 有良好搭配
- >實作簡單
- >可逆轉換
- >可依模式自動調整
>> 常見問題
什麼是 Move-to-Front 編碼？
MTF 是一種資料轉換演算法，會將每個符號編碼為在動態更新清單中的索引。每次完成編碼後，該符號會被移到清單最前端，讓經常出現的符號擁有較小的索引。
為什麼要把 MTF 和 BWT 一起使用？
BWT 會把相似的上下文集中在一起，產生許多區域重複。MTF 再把這些重複轉成較小的數字（包含大量 0 和 1），非常適合接續使用區段長度編碼或 Huffman 編碼來進一步壓縮。
MTF 的清單是怎麼運作的？
清單一開始包含依序排列的 256 個可能位元組值。隨著符號被編碼，已使用的符號會移到清單前端。最近使用的符號會停留在前端附近、索引較小，而長期未使用的符號則會被推向尾端、索引變大。
MTF 和其他轉換相比有何不同？
MTF 是為接在 BWT 後面而設計的。單獨使用時效果有限，但在將 BWT 輸出轉換成更容易壓縮的形式方面非常出色。與算術編碼相比，它實作更簡單，但在壓縮最優性上略遜一籌。
// 計算範例
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// 程式碼範例
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> 更多問題
問：Move-to-Front 有什麼用？
答：MTF 本身不是壓縮，而是一種轉換：最近出現的符號獲得較小的索引，產生大量 0 和 1，便於後續熵編碼（霍夫曼、算術編碼）壓縮。
問：它與 Burrows-Wheeler 轉換有什麼關係？
答：BWT 會把相同字元聚成連續段，MTF 再把它們變成一串小數字，尤其是 0。bzip2 使用的就是 BWT → MTF → RLE → 霍夫曼 這條鏈。
問：MTF 是無損且可逆的嗎？
答：是。解碼端從相同的初始清單出發，重複相同的移動即可還原。初始清單（字元集與順序）兩端必須一致。