12

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

假设 S=abracadabra

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

（注意：S'是原始的，附加S了 kEOF个字符，k 是适合机器字的字符数（我在 32 位机器中，所以k=4）

EOF = '$'

如我错了请纠正我：

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

然后，算法说你必须通过索引S数组来对（命名为 V）的后缀数组进行排序。W

我不完全理解如何通过索引来对后缀进行排序W。例如：在排序的某个时刻，假设你有两个后缀，i和j，你必须比较它们。由于您正在索引W，因此您当时正在检查 4 个字符。
假设它们具有相同的前 4 个字符。然后，您必须检查每个后缀的下一个 4 个字符，并通过从W. 这是正确的吗？这种“将字符打包成单词”真的可以加快速度吗？

4

2 回答 2

4

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

不过，有两点需要说明：

  1. 当您比较后缀 i 和 j 时，就像在您的示例中一样，您确实比较了条目 W[i] 和 W[j]。其结果与您按字典顺序比较四个字符 S[i..i+3] 和 S[j..j+3] 的结果相同，因此您节省了相当于三个字符比较的计算时间。是的，如果结果表明两个四元组相同，则必须继续比较 W[i+1] 和 W[j+1]，但是：您不会立即进行。他们的算法工作方式是基数排序。也就是说，您在初始比较之后立即将后缀放入桶中（可能两者都放入同一个桶中），然后在内部对桶进行递归排序。
  2. The algorithm described in the original paper by Burrows and Wheeler (from which you cite; there is a copy here for example), which is from 1994, is not the optimal suffix array construction algorithm. Firstly, in 2003 several O(N), direct construction methods were discovered; secondly, since then, many further improvements to the implementation were made. The core of the 1994 paper is the idea of using the Burrows-Wheeler transform as basis for string compression, not the exact way the transform itself is generated.
于 2012-02-24T15:14:48.093 回答
0

数组 V 不是后缀数组，而是 W 的索引数组。排序完成后，V 应该将索引保存到 W 中，这样如果

V[i] <= V[j]

然后

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

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

于 2011-10-11T17:32:48.663 回答