> 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 是一种数据变换算法，它把每个符号编码为在动态更新列表中的索引。每次编码后，该符号会被移到列表前端，这样经常出现的符号就会拥有更小的索引。
为什么要和 BWT 一起使用 MTF？
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 是无损且可逆的吗？
答：是。解码端从相同的初始列表出发，重复相同的移动即可还原。初始列表（字符集与顺序）两端必须一致。