我正在阅读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
对后缀进行排序。例如:在排序的某个时刻,假设您有两个后缀
i
和j
,并且必须对其进行比较。由于您正在索引W
,因此您正在检查4个字符。假设它们的前四个字符相同。然后,您将需要检查每个后缀的下四个字符,并通过从
W
中每个后缀的第4个位置进行访问来进行检查。这是正确的吗?这种“将字符打包成单词”真的可以加快速度吗?
最佳答案
您在问题中的描述方式是完全准确的。是的,它可以加快速度,因为就像您所说的,它一次可以比较四个字符。
但是,有两点要注意: