我在 Burrows Wheeler 转型中遇到了一些问题。这是一个大学项目,但这只是其中很小的一部分。整个项目由 3 种不同的算法组成,用于数据压缩。
我只是想弄清楚在 Burrows Wheeler 转换中用于后缀排序的内存和时间效率最高的排序算法是什么?编码需要尽可能高效。
对于较小的数组,排序不会真正影响它,但是当我们压缩的文本文件变得越来越大时,使用低效排序算法所消耗的时间确实会破坏时间和内存效率。
任何帮助将不胜感激,提前致谢!
编辑
顺便说一句,我们用 Java 编写代码,才意识到我从未提到过。
最佳答案
许多实用的基于 BWT 的压缩工具都是基于 DivSufSort 和 MSufSort。但是他们有 O(n^2) 最差的性能,你必须在排序之前对你的数据使用一些预处理方法。
为了理论上的最佳时间/空间成本,请尝试 sa-is 和 sa-ds。
如果您正在尝试自己编写后缀排序算法,我建议您从快速简单的 QSufSort 开始。
关于java - Burrows Wheeler 变换 (BWT) 的最佳排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15966785/