algorithm - 哪种算法最适合 Burrows-Wheeler 变换？

Question

似乎许多实现 BWT 的压缩器将其与算术编码或霍夫曼编码结合使用。 (请随意提名更多，特别是如果他们更好的话。)

我的第一个问题是:为什么字典编码器(例如 LZW 或 LZSS)与 BWT 一起使用是一个更糟糕的选择？

我的第二个问题是:哪种算法最好用？

Answer 1

1. BWT 使用所有大小的上下文，而实际的 LZ 实现几乎不能使用小于 3 的上下文。
2. BWT 受益于 block 内的每个匹配项，而正常的 LZ 实现仅在前瞻窗口中找到匹配项。

但是LZ在很多情况下并不是一个更差的选择。 LZ 是一种在线算法，可以在流上工作，而 BWT 必须在大块上工作并且需要大量内存。 LZ的解压效率很高，而BWT至少还需要5n的额外空间。

BWT 的性能与后缀排序有关。有很多实用的后缀排序算法:MSufSort/DivSufSort/Archon/QSufSort/DeepSwallow，以及O(n)时间的理论最优算法:SA-IS/SA-DS。

PS/如果您正在编写基于 BWT 的压缩器，请多注意编码 BWT 的输出而不是 BWT 本身，因为有许多用于 BWT 转换的实用库，并且它们中的大多数共享相同的接口(interface)。只需在您的项目中使用其中一个即可。