似乎许多实现 BWT 的压缩器将它与算术编码或霍夫曼编码结合使用。(随意提名更多,特别是如果他们更好的话。)
我的第一个问题是:为什么像 LZW 或 LZSS 这样的字典编码器与 BWT 一起使用是更糟糕的选择?
我的第二个问题是:哪个是最好的全能算法?
似乎许多实现 BWT 的压缩器将它与算术编码或霍夫曼编码结合使用。(随意提名更多,特别是如果他们更好的话。)
我的第一个问题是:为什么像 LZW 或 LZSS 这样的字典编码器与 BWT 一起使用是更糟糕的选择?
我的第二个问题是:哪个是最好的全能算法?
但在很多情况下,LZ 并不是一个更糟糕的选择。LZ 是一种在线算法,可以在流上工作,而 BWT 必须在大块上工作,并且消耗大量内存。LZ 的解压效率很高,而 BWT 仍然需要至少 5n 的额外空间。
BWT 的性能与后缀排序有关。有很多实用的后缀排序算法:MSufSort/DivSufSort/Archon/QSufSort/DeepSwallow,还有理论上O(n)时间的最优算法:SA-IS/SA-DS。
PS/ 如果您正在编写基于 BWT 的压缩器,请多注意编码 BWT 的输出而不是 BWT 本身,因为有许多用于 BWT 转换的实用库,并且它们中的大多数共享相同的接口。只需在您的项目中使用其中之一。