Burrows Wheeler Transformation让我陷入了一些问题.这是一个大学项目,但这只是其中很小的一部分.整个项目由3种不同的算法组成,用于数据压缩.
我只想弄清楚什么是最节省内存和时间的排序算法用于Burrows Wheeler Transformation中的后缀排序？编码需要尽可能高效.
对于较小的数组,排序实际上并不会真正起作用,但是当我们正在压缩的文本文件变得越来越大时,使用低效排序算法所消耗的时间实际上会破坏时间和内存效率.
任何帮助将不胜感激,提前感谢!
编辑
我们用Java编写代码,只是意识到我从未提及过.
许多基于BWT的实用压缩工具都基于DivSufSort和MSufSort.但是它们的O(n ^ 2)性能最差,你必须在排序前对数据使用一些预处理方法.
理论上,为了获得最佳时间/空间成本,请尝试使用sa-is和sa-ds.
如果您正在尝试自己编写后缀排序算法,我建议您从快速简单的QSufSort开始.