java – BurrowsWheeler转换(BWT)的最佳排序算法
发布时间：2020-12-15 04:09:11 所属栏目：Java 来源：网络整理
导读：Burrows Wheeler Transformation让我陷入了一些问题.这是一个大学项目,但这只是其中很小的一部分.整个项目由3种不同的算法组成,用于数据压缩. 我只想弄清楚什么是最节省内存和时间的排序算法用于Burrows Wheeler Transformation中的后缀排序？编码需要尽可能
|
Burrows Wheeler Transformation让我陷入了一些问题.这是一个大学项目,但这只是其中很小的一部分.整个项目由3种不同的算法组成,用于数据压缩.
我只想弄清楚什么是最节省内存和时间的排序算法用于Burrows Wheeler Transformation中的后缀排序？编码需要尽可能高效. 对于较小的数组,排序实际上并不会真正起作用,但是当我们压缩的文本文件变得越来越大时,使用低效排序算法所消耗的时间实际上会破坏时间和内存效率. 任何帮助将不胜感激,提前感谢！ 编辑 我们用Java编写代码,只是意识到我从未提及过. 解决方法
许多基于BWT的实用压缩工具都基于DivSufSort和MSufSort.但是它们的O(n ^ 2)性能最差,你必须在排序前对数据使用一些预处理方法.
理论上,为了获得最佳时间/空间成本,请尝试使用sa-is和sa-ds. 如果您正在尝试自己编写后缀排序算法,我建议您从快速简单的QSufSort开始. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |