Burrows–Wheeler变换

对长度N的块，概念上列出全部N个循环移位，按字典顺序排列，然后取排序矩阵最后一列L。同时记录原始文本所在行的编号I，输出这两项；这张矩阵是定义和解释工具，不要求实现真的保存N乘N个字符。

原报告用abraca举例，排序后末列为caraab，原始行编号为1，编号从零起。这一版本保存的是(L,I)，不能把末列单独当成完整可逆表示；使用特殊结束符的其他约定，则须另外规定符号与还原规则。

参考：[1]

末列和首列都是原块字符的排列，所以把L排序就能得到首列F。对同一个字符，按它在两列中从上到下出现的次序一一对应，便可建立行之间的前驱联系；再从I出发沿这些联系恢复整个原块。

这个对应利用排序后的循环移位之间的关系，并不是从字符频率猜原文。频率只能给出每个字符有多少次，不能决定它们原来的次序；还原所需的末列次序与行编号必须保留。

参考：[1]

排序把具有相似后续上下文的循环移位放在一起，末列中的前驱字符也可能出现更集中的局部规律。报告在变换之后使用移到前端等处理，再交给统计编码；收益来自整条编码流程，不是把字符数量相同的末列直接叫作更短文件。

实际压缩还须计入块边界、原始行编号及后续模型的信息。块越大，排序和还原需要的内存及等待也可能增加。比较方案应按完整表示与实现资源衡量，而不是只展示一段看起来更重复的末列。

参考：[1]