burrows-wheeler-transform - 用于大弦的 Burrow Wheeler 实现

Question

我尝试在 burrow Wheelers 循环字符串数组中旋转一个非常大的字符串。

但是我的输入大约是 200000 个字符，当输入这么大时，我无法运行代码，因为它用完了堆空间。

我的教授说实现它的唯一方法是线性内存占用。我不知道这意味着什么。

我能知道还有什么其他方法可以创建一个内存高效的循环字符串并在不耗尽内存的情况下使用它吗

Answer 1

减少内存使用的技巧是创建一个循环后缀数组，它可以使用快速排序的变体n lg n在平均情况下按比例完成（并且内存与 成比例n），它单独考虑字符串中的每个字符（又名 3 路字符串快速排序；它在概念上类似于基数排序）。

即使这需要太多内存，您也需要限制 burrows-wheeler 变换以对固定大小的块进行操作（对 X 个字符执行编码，然后是下一个 X 个字符，等等，直到您对整个字符串进行编码，反转解码过程）。