排序Burrows Wheeler变换（BWT）算法的旋转字符串

Question

我目前正在使用BWT以获得乐趣。 :-)

我已经了解了BWT，我认为BWT在理论上并不复杂。但是，直到现在我还不知道如何实际分类旋转的字符串。

我应该将所有旋转的字符串放在数组中，以便我可以使用像Bubble Sort，Selection或其他方法这样的初始排序算法对它们进行排序？有人告诉我这是不好的做法，因为将N个元素保存到一个数组需要更多次。

那么，我在旋转琴弦的时候如何对旋转的琴弦进行排序呢？

任何人都可以回答这个问题，非常感谢！

谢谢你提前！

汤普森

Answer 1

不太一个答案，但是当我实现了一个BWT算法，我使用的客户端代码呈现here的位置。

历史笔记的一项，它出现了C qsort比C++ std :: sort算法快得多。 CodeGuru上有人建议使用std :: stable_sort，并将性能提高到C qsort所在的位置。这是在VC6。

也运行测试以找到理想的字符串长度 - 排序不是线性的。我正在为传输协议编写压缩程序，因此压缩必须足以支付自己的费用。如果内存为我提供了正确的工作，在733MHz的机器上工作大约4kb。

Answer 2

BWT是一个相当容易实现的方法，但是它的弱点在于要压缩的数据变得越来越慢。

我已经对这个算法做了一个快速分析，结果是（纠正我，如果我错了）在最坏的情况下需要O（n^2），但是可以在最好的情况下达到恒定的时间案件。

事实证明，BWT的大量消耗时间是排序旋转的字符串时。对于那些喜欢玩算法的人来说，现在改善排序似乎是一个热门话题。 :-)

好的，当你使用BWT编码数据时，你应该做的第一件事是将一个独特的字符放在数据中。它用于告诉编码器在找到这个字符时终止了排序过程。例如：说你要压缩字符串 “香蕉” 和步骤：

BANANA $阿纳纳$ B NANA $ BA ANA $班纳$ BANA一个$巴南$ BANANA

旋转的字符串：$ BANANA

使用诸如“$ BANANA”之类的唯一字符（EOF）对字符串排序会更快，因此不会使用任何唯一字符。

我已经张贴关于这个算法一个贫穷的文章...

http://philipstel.wordpress.com/2010/02/10/discussion-of-burrows-wheeler-transform-algorithm/

线性时间用很少的额外空间运行