Boyer-Moore 字符串匹配 - 良好的后缀移位
Boyer-Moore String Matching - Good suffix shift
我理解错误符号 table。在好的后缀 table 中,距离是否应该计算为从最右边出现的模式到模式文本末尾的距离?在那种情况下,下面的 table 不应该将所有距离 (d2) 设为 1(除了最后一个条目为 5),因为相同的模式在它的紧邻左侧可用吗?
类似的话,下面的table也没看懂。有帮助吗?
参考:
问题 - 第 6 页,问题 7。
答案 - 第 11 页
计算机算法的设计与分析- Anany Levitin ( https://umutzafer.files.wordpress.com/2012/01/solu7.pdf )
正文 - The design and analysis of computer algorithms- Anany Levitin(第 263 页)
好的后缀规则正在寻找已匹配后缀的实例其中前一个字符不同。例如,在您的第一个 table 中的 "good suffix" 00
的情况下,移位会寻找一个 00
的实例,而不是 [=12] =].
为什么?因为我们知道 "good suffix" 之前的 0
不匹配;否则我们不会试图改变。
在第二个table中,找不到这样的实例。因此,我们寻找与 "good suffix".
的后缀相匹配的模式的合理前缀
有时书本中并没有像您希望的那样在此类算法中明确提及事情,问题是,寻找匹配部分的出现具有不同的前导字符也意味着没有在 char 前面就是模式 01010 中的情况,当 k=1 时,索引 0 处的 0 前面没有 1(实际上没有任何东西)和匹配且前面有 1 的 0 之间的距离是 4,因此 D2= 4.
当 k=1 匹配部分的后缀 0 被发现作为从索引 0 开始的前缀并且它们之间的距离为 4 所以 D2=4,当 k=3 我们的匹配部分前面有 1 但是我们看到另一个 010 开始在索引 0 之前没有任何重要的东西,它们之间的距离是 2,所以 D2=2。最后,当匹配部分的 k=4 后缀 010 在索引 0 处找到时,它与我们的后缀 010 的距离为 2,因此 D2 再次为 2.
我理解错误符号 table。在好的后缀 table 中,距离是否应该计算为从最右边出现的模式到模式文本末尾的距离?在那种情况下,下面的 table 不应该将所有距离 (d2) 设为 1(除了最后一个条目为 5),因为相同的模式在它的紧邻左侧可用吗?
类似的话,下面的table也没看懂。有帮助吗?
参考:
问题 - 第 6 页,问题 7。
答案 - 第 11 页
计算机算法的设计与分析- Anany Levitin ( https://umutzafer.files.wordpress.com/2012/01/solu7.pdf )
正文 - The design and analysis of computer algorithms- Anany Levitin(第 263 页)
好的后缀规则正在寻找已匹配后缀的实例其中前一个字符不同。例如,在您的第一个 table 中的 "good suffix" 00
的情况下,移位会寻找一个 00
的实例,而不是 [=12] =].
为什么?因为我们知道 "good suffix" 之前的 0
不匹配;否则我们不会试图改变。
在第二个table中,找不到这样的实例。因此,我们寻找与 "good suffix".
的后缀相匹配的模式的合理前缀有时书本中并没有像您希望的那样在此类算法中明确提及事情,问题是,寻找匹配部分的出现具有不同的前导字符也意味着没有在 char 前面就是模式 01010 中的情况,当 k=1 时,索引 0 处的 0 前面没有 1(实际上没有任何东西)和匹配且前面有 1 的 0 之间的距离是 4,因此 D2= 4.
当 k=1 匹配部分的后缀 0 被发现作为从索引 0 开始的前缀并且它们之间的距离为 4 所以 D2=4,当 k=3 我们的匹配部分前面有 1 但是我们看到另一个 010 开始在索引 0 之前没有任何重要的东西,它们之间的距离是 2,所以 D2=2。最后,当匹配部分的 k=4 后缀 010 在索引 0 处找到时,它与我们的后缀 010 的距离为 2,因此 D2 再次为 2.