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

Question

我正在阅读Burrows和Wheeler论文中的块排序算法。

这是算法的一步：

初始化一个由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$$$

然后，该算法要求您按照通过索引数组W来对名为V的S后缀数组进行排序。

我不完全理解如何通过索引数组W来排序后缀。例如，在某个排序点上，假设您获得了两个后缀：i和j，并且您必须比较它们。由于您正在通过索引数组W进行索引，因此每次检查4个字符。
假设它们都具有相同的前4个字符。然后，您将不得不检查每个后缀的下4个字符，并通过从W中的第4个位置访问它们来进行检查。 这样做是否正确？这种“将字符打包成单词”的方法真的可以加快速度吗？

- Guido Tarsia

---

你确定这个(abra brac raca...)是作者想要的打包方式吗？可能应该是abra cada...吧？你能提供一下这句话的更多上下文吗？ - gcbenison

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变换作为字符串压缩的基础，而不是生成变换本身的确切方式。

- jogojapan

Answer 2

数组V不是后缀数组，而是指向W中索引的数组。排序完成后，V应该保存指向W的索引，以便如果

V[i] <= V[j]

那么

 W[V[i]] <= W[V[j]].

希望我说得对 :) 完全匹配并不是问题，任何顺序都可以。重点是当您应用反向转换时，需要能够恢复W以便恢复原始字符串，并且W的相同元素不会导致任何问题。

- Ben Fulton