精确字符串匹配算法

Boyer Moore Exact Pattern Matching  Algorithms 
精确字符串匹配算法 
written in 32 bit Microsoft Assembl er 
使用32位微软汇编器 

In 1977 Robert Boyer and L. Mo ore published a new exact pattern matching algorithm that had superior  logic to existing versions, it performed the character comparison in reverse order to the pattern b eing searched for and had a me thod that did not require the  full pattern to be searched if a mismatch was found. Legend has it that the original algorithm  was coded in PDP-10 assembler.

1977年,Robert Boyer和L.Moore发表了一种新的精确字符串匹配算法,这种算法在逻辑上相对于现有的算法有了很大的超越.它对要搜索的字符串实施逆序字符比较,而且有一种找到了不匹配就不需要对整个字符串进行搜索的方法.这种算法还有最初在PDP-10汇编器上实现的奇迹. 

Computer hardware has changed very  considerably since that time yet th e fundamental logic is still sound in a different world under ver y different conditions. Modern personal computers now have the capacity to work on very large sources and often have enough memory to handle those sources without requiri ng any form of tiling scheme a nd this capacity very well suits the design of the Boyer Moore exact pattern matching algorithm.

计算机硬件相对于那个时代已经有了巨大的发展,但是基础的逻辑仍然处在一种非常迥异的状况中.现代个人电脑已经有能力处理非常大的文本,而且有足够的内存空间来处理那些文本而不要求任何形式的碎瓦片方案（tiling scheme）.个人电脑的能力也能很好的实现Boyer Moore精确字符串匹配算法。

Usage would include tasks like recu rsively searching files for virus p atterns, searching databases for keys or data, text and word processin g and any other task that requ ires handling large amounts of data  at very high speed. 

这种算法的用途包括采用递归方式搜索文件中的病毒字符串，在数据库中搜索关键字或数据，文本和单词的处理，还有其他要求非常高速地处理大量数据的场合。

The versions presented here are cod ed in 32 bit Microsoft assembler (MASM) and include a main versio n that is reasonably close to  the original design and two other variant versions that use parts of the original design. The coding  is designed for both search s peed and mismatch recovery speed in  a practical sense that has be en determined by direct benchmarking. While all three achieve ”sublinearity “, the code design is aimed at  the delivery of performance, not character count theory based on assumptions related to older ANSI  C code. 

这里的版本是由32位微软汇编器（MASM）实现的，其中包含一个和原始设计很接近的主程序，和另外两个使用了部分原始设计的程序。这些代码是根据既追求搜索速度又追求不匹配的恢复速度的原则设计的，满足由直接的基准确定的实际需求。由于这三点都达到了“次线性”，所以代码设计的目标在于实现的结果，而不是基于与旧式的ANSI C代码相关的假设的字符计数理论。

The code is provided as both s ource code in three assembler modul es and a Microsoft format library that can be used by both M ASM and Visual C/C++. To use t he modules in VC++, the correct prototypes must be written. The p arameters are 32 bit unsigned integ ers. 

代码是以两种形式提供的，一种是三个汇编模块的原代码，另一种是可以被MASM和Visual C/C++利用的微软格式的库。要在VC++中使用这些模块，必须使用正确的原型。参数是32位的无符号整型。

How does it work ? 
工作原理 
The following example is set up to search for the pattern within the source. 

下面是在原文本中搜索字符串的例子。


Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern ”algorithm” 

Constructing the Table 
建表 
A 256 member table is constructed that is initially filled with t he length of the pattern which in this case is 9 characters. The 256 members represent the full  range of characters in the AS CII character set. A second pass is then made on the table t hat places a descending count from the original length of the pat tern in the ASCII table for ea ch character that occurs.

首先建立一个包含256个成员的表格，填充的数目为字符串的长度，在这种情况中就是填充9个字符。256个字符表达了整个ASCII字符表的范围。然后，在字符串中的字符出现在表格中的相应位置填入从字符串长度递减的计数。

87654321 <- shift values for each character （每一个字符的移动值） 

The table constructed in this manne r allows the algorithm to determine  in one access if the characte r being compared is within the search pattern or not. The first character compared is the end c haracter of the pattern ”m” to the corresponding position in the  source. 

这样构建表格可以使算法通过一次访问就能判断要比较的字符是不是在搜索的字符串中。第一个比较的字符是字符串中的最后一个字符“m”在原文本中相应的位置的字符（也就是“a”。）

                  | 
Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern ”algorithm” 
                  | 

The character being compared is ”a”  which is within the characters that are in the pattern. Characte r ”a” has a shift of 8 so  the pattern is shifted 8 char acters right.

要比较的字符“a”是在字符串中的字符。字符“a”有8个偏移（相对于最后一个字符），所以将字符串向又移动八个字符。


                           | 
Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern         ”algorithm” 
                           | 

The GOOD SUFFIX shift
“完美后缀”移动 
The shift that was just performed has normally been called the GO OD SUFFIX shift. The next character  being compared is ”f” which i s not within the patern and th is requires a different strategy to  handle the shift. The logic o f the Boyer Moore design is th at if a character is compared  that is not within the characters that are in the pattern, no match can be found by comparing any further characters at this  position so the pattern can be shifted completely past the mismatching  character. 

刚才进行的移动叫作“‘完美后缀‘移动”。下面一个要比较的字符是“f”，但是这个字符没有在字符串中出现，所以要求用不同的方法来移动。Boyer Moore算法的逻辑就是：一旦发现比较的字符不在字符串中，那么向后寻找这个位置的字符都找不到匹配的，所以整个字符串可以移过那个不匹配的字符。

                                    | 
Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern                  ”algo rithm” 
                                    | 

The BAD CHARACTER shift
“不匹配字符”移动 
This shift is usually called the BAD CHARACTER shift and it is calculated in a different manner. The table for the BAD CHARACTER shift occurs in this form. 

这种移动通常称为“‘不匹配字符’移动”，这要用不同的方法来计算移动值。“不匹配字符移动”表要有如下形式。

Pattern ”algorithm” 
         123456 789 

Some of the older implementation ha ve constructed a second table but there is a far more efficient way to do it. The loop tha t does the reverse comparisons must  have a loop counter and this loop counter produces the descendin g shift value that can be used  to perform the BAD CHARACTER  shift. The above shift that mismatc hed on the character ”f” occurred on the first comparison after t he shift so the shift past the  mismatching character is 9. 

有一些旧式的实现建造了第二张表，但是有一种比这效率要高得多的做法。进行逆序比较的循环必须有一个计数器，这个计数器产生用于“不匹配字符”的移动的递减的位移值。上面的移动发生在不匹配的字符“f”上，所以字符串相对于那个字符的位移为9。

The following character compared in the source is ”e” which is al so not in the table and it produces a BAD CHARACTER shift on  the first position of the com parison so the shift is also 9 . 

下面要比较的字符是“e”，它也不是字符串中的，所以字符串相对于它产生的“不匹配字符”的位移也是9。

                                             | 
Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern                           ”algorithm”  
                                             | 

The next mismatch is ”a” which occurs in the search pattern. This  lines up with the first chara cter of the pattern being searched for. The shift value in the table for the character ”a” is 8 which will produce the match being searched for.

下一个不匹配字符是“a”，这个字符是在搜索字符串中的。这个字符出现在搜索字符串的第一个位置上。表中字符“a”的移动值为8，这就产生了匹配。

                                                     | 
Source  ”This is a test of the Boyer Moore algorithm.” 
Pattern                                   ”algorithm” 
                                                     | 

The reverse comparison loop will co mpare all of the characters in the pattern to the position in the source and will produce a match at the end. 

逆序比较循环将对字符串中的所有字符和对应原文本中的位置进行比较，最终产生匹配。

The additional heuristic
附加的启发式搜索 
The is the need to produce an addition heuristic to handle the occurrence of repeated sequences of characters which is common in b oth plain text and binary files. What will happen if there is a repeated sequence of characters that are within the characters use d in the search pattern is tha t the value in the table for the GOOD SUFFIX shift will prod uce a shift that goes past the  correct match. 

在普通的文本和二进制文件中重复的字符序列是很常见的，所以需要有附加的启发式搜索来处理这种情况。如果有一串重复的字符是字符串中的字符，那么，“完美后缀”移动表格中的值将产生跳过正确匹配的移动。

           | 
    xxxxBooooxxxx 
      Boooo 
           | 

When the GOOD SUFFIX shift table is constructed from the characters in a pattern that has repeated sequences, the repeat character valu es are overwritten at the same position in the table so you  do not have an incremental decremen ting of the values for each ch aracter position.

当“完美字符”移动表格是由有重复序列的字符串建造时，重复的字符在表中同样的位置被覆盖，所以不需要对每一个位置的值递增。

    Boooo 
    4111 

If the GOOD SUFFIX shift is ap plied with these values in the table, the pattern will be shifted  past the correct match. 

如果“完美后缀”移动按照表中这样的值进行，字符串就会移过正确的匹配。

                | 
    xxxxBooooxxxx 
           Boooo 
                | 

The additional heuristic calculates the number of comparisons made in  the current position and subtracts  that from the GOOD SUFFIX shift. This will produce the correct ma tch in most instances but the  subtraction can also produce 0 so to ensure that a shift is  applied in the worst case, if  the calculated value is less than 1, a minimum shift of one  is performed. 

附加的启发式搜索计算当前位置进行的比较的次数，然后从“良好后缀”移动中减去这个数。这在大部分情况中可以产生正确的匹配，但是减法也能产生0，所以为了保证在最坏的情况中也能产生一个移动，如果计算出来的值小于1，至少要产生一个移动。

        | 
    xxxxBooooxxxx 
      Boooo 
        | 

Two comparisons have been made at this position so the GOOD SUFFI X shift of 4 for ”B” has  2 subtracted from it to produce a shift of 2 characters.

在这个位置进行了两次比较，所以原本值为4的字符“B”减去了2 ，产生了2个“良好后缀”移动 。

 
             | 
    xxxxBooooxxxx 
        Boooo 
              | 

The two variations 
The two variations supplied with th e complete Boyer Moore algorithm ar e based on the two different s hifts that the original uses, the SBM.ASM version uses the GOOD S UFFIX shift from the table without the BAD CHARACTER shift, the B MH.ASM uses the BAD CHARACTER shift  and simply increments the location  if the character occurs within the table. 

Both will produce reasonable performance  because they have less overhead than the original. Their performance in loop speed must be offset against the lack of the extra logic that is used in the  original algorithm. 

The SBM.ASM version is generally fa ster on older machines and some AMD machines because the shorter