我正在阅读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个位置访问它们来进行检查。
这样做是否正确?这种“将字符打包成单词”的方法真的可以加快速度吗?
abra brac raca...
)是作者想要的打包方式吗?可能应该是abra cada...
吧?你能提供一下这句话的更多上下文吗? - gcbenison