3

我在 Burrows Wheeler Transformation 上遇到了一些问题。这是一个大学项目，但这只是其中很小的一部分。整个项目由 3 种不同的算法组成，用于数据压缩。

我只是想弄清楚在 Burrows Wheeler 转换中用于后缀排序的内存和时间效率最高的排序算法是什么？编码需要尽可能高效。

对于较小的数组，排序不会真正影响它，但是当我们压缩的文本文件变得越来越大时，使用低效的排序算法所消耗的时间确实会破坏时间和内存效率。

任何帮助将不胜感激，在此先感谢！

编辑

顺便说一句，我们用 Java 编码，只是意识到我从未提到过。

4

2 回答 2

6

许多实用的基于 BWT 的压缩工具都基于DivSufSort和MSufSort。但是它们的性能最差 O(n^2)，您必须在排序之前对数据使用一些预处理方法。

为了获得理论上的最佳时间/空间成本，请尝试sa-is和sa-ds。

如果你想自己写一个后缀排序算法，我建议你从快速简单的QSufSort开始。

于 2013-04-12T10:41:17.650 回答
1

正如richselian 所提到的，排序是二次的，而基于后缀数组的算法是线性的。如果您的阵列很小，那没关系，但更大的阵列会产生更好的压缩结果。您可以在这里找到基于后缀数组的 BWT 的完整 java 实现作为示例：https ://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java （数组高达 16MB）。至于“java很慢”的论点，我会恭敬地不同意。

于 2013-12-04T06:17:42.610 回答