如何在块排序中对数组后缀进行排序

Question

我正在阅读Burrows和Wheeler论文中的块排序算法.这是算法的一个步骤:

假设S = abracadabra

初始化N个字W [0,...,N-1]的数组W,使得W [i]包含排列的字符S'[i,...,i + k-1],以便进行整数比较.这些词同意对k字符串的词典比较.将字符打包成单词有两个好处:它允许使用对齐的内存访问一次比较两个前缀k个字节,并且它允许消除许多慢速情况

(注意:S'是附加S了k个EOF字符的原件,k是适合机器字的字符数(我是32位机器,所以k=4)

EOF = '$'

如我错了请纠正我:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

然后,算法说你必须S通过索引到数组W来对后缀数组(名为V)进行排序.

我不完全明白你如何通过索引来排序后缀W.例如:在分选的某一点,假设你得到两个后缀,i并且j,你必须对它们进行比较.由于您正在编入索引W,因此您当时要检查4个字符.
假设它们具有相同的前4个字符.然后,您必须检查每个后缀的下4个字符,并通过从每个后缀的第4个位置访问来完成W.这是正确的吗？这种"将字符包装成文字"真的能加快速度吗？

Answer 1

您在问题中描述它的方式是完全准确的。是的，它加快了速度，因为就像你说的，它一次比较四个字符。

不过，有两点需要说明：

1. 当您比较后缀 i 和 j 时，就像在您的示例中一样，您确实比较了条目 W[i] 和 W[j]。其结果与按字典顺序比较四元组字符 S[i..i+3] 和 S[j..j+3] 的结果相同，因此您节省的计算时间相当于三个字符比较的时间。是的，如果结果表明两个四元组相同，您必须继续比较 W[i+1] 和 W[j+1]，但是：您不会立即这样做。他们的算法的工作方式是基数排序。也就是说，您在初始比较后立即将后缀放入存储桶中（可能都放入同一个存储桶中），然后以递归方式在内部对存储桶进行排序。
2. Burrows 和 Wheeler 的原始论文（您从中引用；例如，这里有一份副本）中描述的算法（来自 1994 年）并不是最佳后缀数组构造算法。首先，2003年发现了几种O(N)直接构造方法；其次，自那时以来，实施工作取得了许多进一步的改进。1994 年论文的核心思想是使用 Burrows-Wheeler 变换作为字符串压缩的基础，而不是变换本身生成的确切方式。