> mtf | move | front <

MTF is a data transformation algorithm that encodes each symbol as its index in a dynamically updated list. After encoding each symbol, it's moved to the front of the list, giving frequently used symbols smaller indices.

BWT clusters similar contexts together, creating local repetitions. MTF then transforms these repetitions into small numbers (many 0s and 1s), which compress very well with subsequent Run-Length or Huffman encoding.

The list starts with all 256 possible byte values in order. As symbols are encoded, they move to the front. Recently used symbols stay near the front with small indices, while unused symbols drift to larger indices.

MTF is specifically designed to work after BWT. It's not effective alone but excels at converting BWT's output into a form that compresses well. It's simpler than arithmetic coding but less optimal.

Move-to-Front（前移编码）是 bzip2 压缩流水线的关键中间步骤。bzip2 的完整流水线如下：
1. RLE-1：运行长度编码（处理非常长的相同字节序列）。
2. BWT（Burrows-Wheeler Transform）：把相似上下文聚在一起，产生大量局部重复。
3. MTF：把 BWT 产生的局部重复转成大量 0 和小数值。
4. RLE-2：对 MTF 输出的 0 串再做 RLE。
5. Huffman 编码：熵编码最后压缩。

MTF 的直觉：维护一个 256 字节的符号表，每次读到一个字节，输出它在表中的位置，然后把它移到表首。如果 BWT 后输出是 aaaabbbbcccc...，MTF 的输出会是 a=a, a=0, a=0, a=0, b=1, b=0, b=0, b=0, c=2, c=0, c=0, c=0——大量 0，Huffman 能把 0 压成 1-2 bit。

这就是为什么 bzip2 对文本压缩比 gzip 好 10-15%：MTF + BWT 的组合在结构化文本上特别有效。

两者都利用“局部重复”，但方式完全不同：

RLE（游程编码）：把连续相同的字节压成 (count, byte) 对。
• AAAABBBCC → (4,A)(3,B)(2,C)
• 只对 完全连续 的重复有效。
• 纯文本很少连续重复，所以效果差。

MTF（前移编码）：把“最近使用的符号”编码成小索引。
• ABCABCABC → 第一次 A/B/C 是 0/1/2（大索引），之后的 A/B/C 都是 1/1/1（小索引）。
• 对 模式重复 有效，不要求字符连续。

两者经常组合使用：bzip2 把 MTF 后的 0 串再用 RLE-2 压缩，充分利用两种局部性。

A minimal MTF implementation is about 10 lines:

# Encode
def mtf_encode(data):
    table = list(range(256))
    result = []
    for byte in data:
        idx = table.index(byte)
        result.append(idx)
        table.pop(idx)
        table.insert(0, byte)
    return result

# Decode
def mtf_decode(indices):
    table = list(range(256))
    result = []
    for idx in indices:
        byte = table[idx]
        result.append(byte)
        table.pop(idx)
        table.insert(0, byte)
    return bytes(result)