我正在阅读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(名为V)的后缀数组进行排序,方法是将其索引为
数组W

我不完全了解如何通过索引W对后缀进行排序。
例如:在排序的某个时刻,假设您有两个后缀ij,并且必须对其进行比较。由于您正在索引W,因此您正在检查4个字符。
假设它们的前四个字符相同。然后,您将需要检查每个后缀的下四个字符,并通过从W中每个后缀的第4个位置进行访问来进行检查。
这是正确的吗?这种“将字符打包成单词”真的可以加快速度吗?

最佳答案

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

但是,有两点要注意:

  • 当您比较后缀i和j时(如您的示例),您确实比较了条目W [i]和W [j]。其结果与您在字典上比较字符S [i..i + 3]和S [j..j + 3]的四个字符的结果相同,因此您节省了相当于三个字符比较的计算时间。是的,如果结果表明两个四倍体相同,则必须继续比较W [i + 1]和W [j + 1],但是:您不会立即进行比较。他们的算法的工作方式是基数排序。也就是说,您可以在进行初始比较后立即将后缀放入存储桶中(可能将它们都放入同一个存储桶中),然后在内部对存储桶进行递归排序。
  • Burrows和Wheeler在原始论文中描述的算法(您引用了该示例;例如,有一个here副本)不是1994年的最佳后缀数组构造算法。首先,在2003年发现了几种O(N)直接施工方法;其次,从那时起,对实现进行了许多进一步的改进。 1994年论文的核心思想是使用Burrows-Wheeler转换作为字符串压缩的基础,而不是转换本身的确切生成方式。
  • 10-07 16:29
    查看更多