我已经成功地为我正在编写的compressiontestbed实现了BWT阶段(使用常规字符串排序)。我可以应用BWT，然后逆BWT变换，输出与输入匹配。现在我想使用后缀数组加速创建BW索引表。我发现了2个相对简单的、据说是快速的O(n)后缀数组创建算法，DC3和SA-IS，它们都带有C++/C源代码。我尝试使用源(开箱即用的编译SA-IS源也可以找到here)，但未能获得正确的后缀数组/BWT索引表。这是我所做的:T=输入数据，SA=输出后缀数组，n=T的大小，K=字母大小，BWT=BWT索引表我处理8位字节，但两种算法都需要一个以零字节形式的唯一标记/EOF标记(DC3需要3个，S

我试图实现Burrows-Wheeler在python中转换。(这是网课的作业之一，但希望自己做了一些功课，才有资格求助)。该算法的工作原理如下。取一个以特殊字符(在我的例子中是$)结尾的字符串，并从这个字符串创建所有循环字符串。按字母顺序对所有这些字符串进行排序，特殊字符总是小于任何其他字符。在此之后获取每个字符串的最后一个元素。这给了我一个单行:''.join([i[-1]foriinsorted([text[i:]+text[0:i]foriinxrange(len(text))])]对于相当大的字符串(这足以解决问题)，这是正确且相当快的:60000chars-16secs40