BurrowsWheeler变换的最佳排序算法
我在Burrows变换中遇到了一些问题。这是一个大学项目，但这只是其中的一小部分。整个项目由3种不同的算法组成，用于数据压缩。
我只是想找出什么是最节省内存和时间的排序算法，用于在Burrows转换中的后缀排序？编码必须尽可能高效。
对于较小的数组，排序不会真正影响它，但是当我们正在压缩的文本文件越来越大时，使用低效排序算法所花费的时间确实会破坏时间和内存效率。
任何帮助都将不胜感激，谢谢！
编辑
顺便说一句，我们用Java编写代码，只是意识到我从来没有提到过。
回答 2
Stack Overflow用户
发布于 2013-04-12 10:41:17
许多实用的基于小波变换的压缩工具都是基于DivSufSort和MSufSort的。但是它们具有O(n^2)最差的性能，在排序之前必须对数据使用一些预处理方法。
为了在理论上获得最佳的时间/空间成本，请尝试sa-is和sa-ds。
如果您试图自己编写后缀排序算法，我建议您从快速简单的QSufSort开始。
Stack Overflow用户
发布于 2013-12-04 06:17:42
正如richselian所提到的，排序是二次型的，而基于后缀数组的算法是线性的。如果您的数组是小的，这并不重要，但更大的数组产生更好的压缩结果。您可以在这里找到一个基于后缀数组的完整的java实现：https://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java (最多16 to的数组)。至于"java是慢的“这一论点，我谨此表示不同意。
https://stackoverflow.com/questions/15966785
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号