精确字符串匹配算法

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

In 1977 Robert Boyer and L. Moore 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 being searched for and had a method 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 the fundamental logic is still sound in a different world under very 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 requiring any form of tiling scheme and this capacity very well suits the design of the Boyer Moore exact pattern matching algorithm.

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

Usage would include tasks like recursively searching files for virus patterns, searching databases for keys or data, text and word processing and any other task that requires handling large amounts of data at very high speed. 

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

The versions presented here are coded in 32 bit Microsoft assembler (MASM) and include a main version 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 speed and mismatch recovery speed in a practical sense that has been 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 source code in three assembler modules and a Microsoft format library that can be used by both MASM and Visual C/C++. To use the modules in VC++, the correct prototypes must be written. The parameters are 32 bit unsigned integers. 

代码是以两种形式提供的，一种是三个汇编模块的原代码，另一种是可以被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 the length of the pattern which in this case is 9 characters. The 256 members represent the full range of characters in the ASCII character set. A second pass is then made on the table that places a descending count from the original length of the pattern in the ASCII table for each character that oclearcase/" target="_blank" >ccurs.

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

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

The table constructed in this manner allows the algorithm to determine in one access if the character being compared is within the search pattern or not. The first character compared is the end character 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. Character "a" has a shift of 8 so the pattern is shifted 8 characters 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 GOOD SUFFIX shift. The next character being compared is "f" which is not within the patern and this requires a different strategy to handle the shift. The logic of the Boyer Moore design is that 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                  "algorithm" 
                                  | 

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" 
         123456789 

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

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

The following character compared in the source is "e" which is also not in the table and it produces a BAD CHARACTER shift on the first position of the comparison 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 character 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 compare 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 both plain text and binary files. What will happen if there is a repeated sequence of characters that are within the characters used in the search pattern is that the value in the table for the GOOD SUFFIX shift will produce 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 values are overwritten at the same position in the table so you do not have an incremental decrementing of the values for each character position.

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

    Boooo 
    4111 

If the GOOD SUFFIX shift is applied 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 match 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 SUFFIX 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 the complete Boyer Moore algorithm are based on the two different shifts that the original uses, the SBM.ASM version uses the GOOD SUFFIX shift from the table without the BAD CHARACTER shift, the BMH.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 faster on older machines and some AMD machines because the shorter pipeline with a lower penalty for register stalls better suits the code design. The BMH.ASM version is faster on a late model Intel machine because it better suits the longer pipeline of later Intel processors and is less prone to branch prediction buffer penalties. This version will show much slower speeds if the character range is limited to characters that are within the search pattern as it only does a single increment in that situation. The original algorithm BM.ASM averages better across x86 processors and is less vulnerable in worst case situations. The range of variation between all three versions is about 10%. The original version is within a few percent of the fastest tests on both types of machines and this reflects its dependence on logic rather than just fast loop code. 
 

原文转自：http://www.ltesting.net