在Boyer-Moore算法的原始摘要中,经常出现短语来传递字符。这个短语到底是什么意思?我不是以英语为母语的人,谷歌搜索结果对我没有帮助。
我在董事会上问这个问题,因为背景可能看起来很重要。
该算法有两个循环:一个在潜在匹配子字符串上的外循环和一个在每个潜在匹配子串的字符上的内循环。
考虑在字符串"FROGBIG"中搜索"BIG"。
外部循环在可能出现"BIG"的潜在位置上迭代——在FROGBIG中,(最多)有5个这样的位置。
12345
FROGBIG
BIG (outer loop index=1)
BIG (outer loop index=3)
对于每次比较,内部循环都会对模式的字符进行迭代。因此,对于1的外循环索引,内循环将比较"BIG"和FRO"在字符串BIG上迭代,向后,一次一个字符(最多3个比较)。
123
ORF
GIB
G (inner loop index = 1)
B (inner loop index = 3)
算法(我不想讨论)正在优化这些循环,以避免不必要的比较。也就是说,在FRO和BIG(外循环1)的比较过程中,内循环只会比较"G"与"O"(内循环1),而不会比较"R"与"I"(内环2)或"B"与"F"(内环3)。此外,在将"FRO"与"BIG"进行比较后,外循环将跳过ROG与BIG(外循环2)和OGB与BIG的比较(外循环3),立即移动到GBI与BIG之间(外循环4)。
在讨论内循环(在"G"、"I"one_answers"B"上)时,作者首先使用了"pass"一词。当作者说"传递一个字符"时,"字符"指的是内部循环迭代的单个字符"G"、"I"one_answers"B"。"通行证"一词的使用方式与我给出街道指示的方式相同:"你将经过橡树街,经过枫树街,到达橄榄街"。但作者描述的不是经过街道,而是"经过的人物":"你会经过G,经过I才能到达B"。
为了进一步澄清,作者还经常使用"通过"一词作为形容词"通过"。因此,他们经常提到一个"已通过的角色"。在这种情况下,"传递的字符"只是内部循环必须检查(或"传递")才能到达当前字符的字符。在我的街道方向上,一旦旅行者到达橄榄街,人们就会称橡树街和枫树街为"过往街道"。在算法中,如果内部循环在"I"处,则"G"是"传递字符";如果它在"B",那么"传递的字符"指的是"G"one_answers"I"。
最后,作者继续使用惯例的"传递字符"来分析整体效率。在论文中,"通过将引用字符串的数量除以在找到模式之前传递的字符数i-1"。在这里,我相信他们指的是在找到模式之前必须传递的搜索字符串中的字符数。如果我没有记错的话,这似乎有点倾斜:"传递的字符数"实际上只是"字符串中第一个出现的模式的位置"。因此,在图1中,效率实际上被测量为,"对于某个长度的模式(3代表"BIG"),算法检查了潜在匹配字符串(5代表"FROGBIG":FRO、ROG、OGB、GBI和BIG)的百分比是多少?"
您的链接已经将"传递的字符数多于检查的字符数"重新表述如下:
因此,该算法具有不同寻常的特性,即在大多数情况下,并不是所有"字符串"的前"i"个字符都被检查。
I.O.W.:并不是所有传递给算法的字符都必须经过检查。
希望能有所帮助!
在此上下文中"传递字符"更接近于"跳过"字符或不检查字符。
以下伪代码"通过"char
阵列中的奇数索引字符
char[] charArray = ['a','b','c', ...];
// increment by 2 to "pass" every other character
for (int i=0; i<charArray.Length; i+=2)
{
Print(charArray[i]);
}
编辑:虽然以上在许多情况下都是正确的,但在您提供的链接的上下文中,这不是它的使用方式(正如@KevinKirkpatrick向我指出的那样)
简而言之,您提供的链接上下文中的"已传递字符"表示"将来不会检查的任何字符"。
换句话说,如果您通过递增(而不是递减)索引来循环遍历数组,那么"传递"的字符都是索引低于当前索引的字符。这意味着在索引i
处"传递一个字符"意味着将索引递增到大于i
。