Run-Length Encoding (RLE)

• 第一位表示由0或者1开头
• 之后用prefix-free integer encoding表示每一个Run的长度
  • 后x位表示这个run的binary长度
  • 前x-1位填零, 为unary表示后x位的长度减一

Huffman Coding

• 用binary trie表示字典中的所有字符
• 将文本依照trie转成binary

• 将每个字符存入独立的trie中
• 确定每个字符的出现次数(频率), 一个trie的比重(weight)即为trie中字符的频率和
• 将weight最小的两个trie合并成一个新trie
• 重复上一步直到只剩下一个trie

MTF

• 用字典中, 字符的index表示字符
• 使用动态字典, 将出现过的字符移到字典开头, 以减小下次出现时该字符的index值
• MTF本身不能达到压缩的目的, 需配合prefix-free integer encoding或者huffman

LZW

• 字典编码使用固定长度k, 字典总共有2^k个entry
• 字典由所有单字符开头, 剩余entry留空
• 从第二个encode的字符[组]开始, 将其首字符与上一个encode的字符[组], 组成一个新的字符组, 并存入字典中
• 当这个字符组合再次出现的时候, 即可用一个编码代表整个字符组

BWT

• 将整个string S写成各种cyclic shift, 用$表示string结尾
• 比如abcd$可以写成abcd$, bcd$a, cd$ab, d$abc, $abcd
• 将所有cyclic shift排序
• 将排序后的所有cyclic shift的最后一位按顺序组合成新的string, 既是Encoded的string C

• 给Encoded的string C的每一个字符一个序号, 从0到n-1
• 将字符和序号一起排序. 排序后的序号提取为Array N
• for(i = N[N[0]], i != N[0], i = N[i]) print(C[i]);