home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / searchbm.zip / POSBM.DOC < prev    next >
Text File  |  1988-07-01  |  13KB  |  228 lines
  1.     Faster String Searches
  2.     Dr. Dobb's Journal #153 July 1989, p.74 and 98.
  3.  
  4.     -----------------------------------------
  5.     Boyer-Moore may be the algorithm you need
  6.     -----------------------------------------
  7.     by Costas Menico
  8.  
  9.     Costas Menico is a senior software developer and part owner of The 
  10.     Software Bottling Company. He can be reached at 6600 Long Island 
  11.     Expressway, Maspeth, NY 11378.
  12.  
  13.     While programming several of my company's products, I have many times 
  14.     come across the need to perform a string search to accomplish a certain 
  15.     task. A string search is the function used to find a string A (the 
  16.     pattern) in a string B (the text) and return the position of A in B.
  17.  
  18.     After realizing that the built-in string search functions of many 
  19.     language compilers used simple brute-force algorithms, I set out to 
  20.     find and implement an equivalent string-search function that would 
  21.     perform at a fraction of the speed of the built-in function.
  22.  
  23.     The Brute-Force Method
  24.  
  25.     As the name implies, the brute-force method of performing a string 
  26.     search involves an exhaustive search from the start of the pattern 
  27.     until there is a match or the end of the string is reached.
  28.  
  29.     Each character in the pattern is compared left to right with each 
  30.     character in the string. The scanning is continued until all of the 
  31.     characters in the pattern match an equivalent length in the string. If 
  32.     no match occurs, the pattern is moved one character to the right and a 
  33.     new search is begun.
  34.  
  35.     Assume we want to search for the pattern HEAD in the string 
  36.     "MAXIMOODHEADROOM". The search is shown in Figure 1. The method shown 
  37.     is time-consuming, because every character in the string must be 
  38.     compared with every other character until a final match is found. Nine 
  39.     steps were taken to discover the sample pattern. Using a program that 
  40.     must perform thousands of searches is a time-consuming way of looking 
  41.     up a pattern.
  42.  
  43.     +--------------------------------------------------------------------+
  44.     | Pattern = H E A D                                                  |
  45.     | String  = M A X I M O O D H E A D R O O M                          |
  46.     |                                                                    |
  47.     |      1)   H                        H Does not match, move right.   |
  48.     |      2)     H                      H Does not match, move right.   |
  49.     |      3)       H                    H Does not match, move right.   |
  50.     |      4)         H                  H Does not match, move right.   |
  51.     |      5)           H                H Does not match, move right.   |
  52.     |      6)             H              H Does not match, move right.   |
  53.     |      7)               H            H Does not match, move right.   |
  54.     |      8)                 H          H Does not match, move right.   |
  55.     |      9)                   H E A D  HEAD finally matches.           |
  56.     +--------------------------------------------------------------------+
  57.     Figure 1: Brute-force search
  58.  
  59.     The Boyer-Moore Method
  60.  
  61.     After looking through some impressive (and complex) algorithms, I came 
  62.     across an elegant and easily implemented algorithm called the Boyer-
  63.     Moore method, named for the pair of scientists who invented it. This is 
  64.     a hybrid algorithm that uses pattern analysis combined with brute 
  65.     force.
  66.  
  67.     To implement the algorithm in assembler, I used MASM and linked it into 
  68.     Turbo Pascal 4.0. The algorithm is also easily converted to work with C 
  69.     and Basic. For the assembly language program (called POSBM), see 
  70.     Listing One, page 98; for the benchmark test program see Listing Two, 
  71.     page 99.
  72.  
  73.     The basic idea behind the Boyer-Moore technique is the movement of the 
  74.     pattern more than one character at a time during the search for a 
  75.     matching character. This saves search steps, thereby increasing search 
  76.     speed. You may wonder how a whole pattern can be moved to the right 
  77.     without a search through any of the characters in between. The answer 
  78.     is simple. All that is required is a 256-character array that defines 
  79.     the pattern. This array (called a SKIPARRAY) is built every time the 
  80.     search function is called. Each position corresponds to the value of 
  81.     each character in the ASCII character set.
  82.  
  83.     The algorithm is simple. A SKIPARRAY of 256 bytes is filled with the 
  84.     length of the pattern. Starting from the right of the pattern, each 
  85.     character is read and its offset placed into the SKIPARRAY, using the 
  86.     characters ASCII value as the index (see Figure 2).
  87.  
  88.     +--------------------------------------------------------------------+
  89.     |                        A  B  C  D  E  F  G  H  I  ... Z            |
  90.     | SKIPARRAY position ... 65 66 67 68 69 70 71 72 73 ... 91           |
  91.     | Original values        4  4  4  4  4  4  4  4  4  ... 4            |
  92.     | Values with "HEAD"     1  4  4  0  2  4  4  3  4  ... 4            |
  93.     +--------------------------------------------------------------------+
  94.     Figure 2: SKIPARRAY values with the HEAD pattern
  95.  
  96.     The pattern is then placed against the string for the search. At the 
  97.     rightmost position of the pattern the corresponding character in the 
  98.     string is read and its ASCII value ist used as an index into the 
  99.     SKIPARRAY. The value in the SKIPARRAY will determine how far to slide 
  100.     the pattern to the right, with one exception. A value of 0 means that 
  101.     the rightmost character in the pattern is lined up with an exact 
  102.     character in the string. Because this is a possible match, a reverse 
  103.     compare is performed on the remaining characters in the string (that 
  104.     is, a reverse brute-force compare). If the pattern matches, the offset 
  105.     is noted in the string. Otherwise, the pattern slides over by one 
  106.     position and the process is repeated.
  107.  
  108.     To better explain this process I will use as an example the pattern 
  109.     HEAD. The SKIPARRAY is first filled with the length of the pattern. 
  110.     Once this is completed the SKIPARRAY will contain 4s in all 256 
  111.     positions.
  112.  
  113.     Next, we put the skip value for each character in the pattern into the 
  114.     SKIPARRAY. To do this, the offset of each character is taken from the 
  115.     end of HEAD and placed at the ASCII position in the SKIPARRAY. For the 
  116.     pattern HEAD, the SKIPARRAY is transformed by putting in the 
  117.     corresponding values of 3, 2, 1 and 0 at 72 (H), 69 (E), 65 (A) and 68 
  118.     (D) positions (see Figure 3).
  119.  
  120.     +--------------------------------------------------------------------+
  121.     | Pattern = H E A D                                                  |
  122.     | String  = M A X I M O O D H E A D R O O M                          |
  123.     | 1)        H E A D                                                  |
  124.     | 2)                H E A D                                          |
  125.     | 3)                  H E A D                                        |
  126.     | 4)                        H E A D                                  |
  127.     +--------------------------------------------------------------------+
  128.     Figure 3: Using Boyer-Moore, we find a match in four steps
  129.  
  130.     The pattern is then scanned right to left to determine how far to move 
  131.     the pattern for each character in the string. To find the pattern HEAD 
  132.     in MAXIMOODHEADROOM, HEAD is positioned at the start of the string. 
  133.     This places the character D of the pattern HEAD under the character I 
  134.     in the string (see step 1 in Figure 3).
  135.  
  136.     Because there is no match, that is, D is not equal to I, the SKIPARRAY 
  137.     is indexed at the position of the value for I, which is found to be 4. 
  138.     As I is not in the pattern, HEAD is positioned four characters to the 
  139.     right of the mismatched position.
  140.  
  141.     The D in the pattern (see step 2 in Figure 3) is now positioned under 
  142.     the D in the string. This indicates, that the last character of the 
  143.     pattern matches the corresponding character in the string. We therefore 
  144.     proceed to match the remaining characters by using a reverse brute-
  145.     force method. In this case, the A in the pattern will not match the O 
  146.     in the string. Because this was a brute-force compare, we only move the 
  147.     pattern one character to the right.
  148.  
  149.     The D (see step 3 in Figure 3) is now positioned under the H in the 
  150.     string. As D is not equal to H, we index into the SKIPARRAY and find 
  151.     that the skip value for H is three. HEAD now slides to the right three 
  152.     characters.
  153.  
  154.     The D in the pattern (see step 4 in Figure 3) is again lined up under 
  155.     the D in the string. By comparing the remaining characters of HEAD 
  156.     backwards from the D position, we find that the pattern matches 
  157.     successfully and record the starting position in the string.
  158.  
  159.     The program used to perform the Boyer-Moore search method is shown in 
  160.     Listing One. It is assembled using MASM (or TASM) and the OBJ file is 
  161.     linked in to the Turbo Pascal program. It is called by using the name 
  162.     POSBM the same way you would call the POS() function in Turbo Pascal. 
  163.     The way this is set up will only work on parameters of type STRING (see 
  164.     Listing Two), which limit the search to 255 characters. You can easily 
  165.     modify the program to pass arrays the same way they are passed in C.
  166.  
  167.     To call POSBM from C you must modify the structure CSTK to conform to 
  168.     the C calling sequence. You must change the initial code to copy the 
  169.     addresses of the PATADDR and STRADDR from the calling stack, to PATTXT 
  170.     and STRTXT. The length of the strings must also be computed (by 
  171.     searching for a 0 using a SCASB instruction) and placed in the 
  172.     variables PATLEN and STRLEN. Last, the way in which you return from the 
  173.     function should be changed to leave the calling values on the stack. 
  174.     Note that the function POSBM is declared FAR.
  175.  
  176.     Limitations to the Boyer-Moore Method
  177.  
  178.     Some patterns may not be suitable for this method. If your pattern has 
  179.     repeating characters matching against a text of repeating characters, 
  180.     the Boyer-Moore method will actually be slower than brute-force. For 
  181.     example, the bit-map pattern 01111111 in a bit-map string of all 
  182.     11111111 would require a lengthy search because the 0 in the pattern 
  183.     would not be compared until all the 1s have been matched from right to 
  184.     left. The pattern would then be moved over by one position and the 
  185.     search tries again, thus defeating the algorithm's purpose.
  186.  
  187.     There have been some clever ways to avoid this problem by analyzing the 
  188.     pattern but, for all intents and purposes, the simple algorithm works 
  189.     very well for text searches.
  190.  
  191.     Benchmarks
  192.  
  193.     To illustrate the speed difference between brute force and Boyer-Moore, 
  194.     I have put together a small test program that compares the speed of the 
  195.     built-in function POS() of Turbo Pascal 4.0 (which uses the brute-force 
  196.     method) and the assembly language function POSBM() presented in this 
  197.     article.
  198.  
  199.     To run the program, you must first assemble the function POSBM.ASM on 
  200.     Listing One with MASM or TASM. This will create an .OBJ module. Next, 
  201.     compile the Turbo Pascal program in Listing Two. The function will be 
  202.     linked in when the {$L POSBM.OBJ} directive is encountered. Because the 
  203.     function is declared as FAR, we must include the directive {$F+} in the 
  204.     program to notify Pascal that the function should be called with FAR 
  205.     instructions.
  206.  
  207.     The program starts out by generating a random string 255 characters 
  208.     long and uses the last five characters of the string as the pattern. 
  209.     The pattern is then searched in the string using POS() and POSBM() by 
  210.     putting the searches in a long loop to emphasize the time difference. 
  211.     You may want to increase the value of 'longloop' if you have a fast 
  212.     machine to see the significantly higher start and end times. The 
  213.     POSBM() is usually 400 percent faster than the POS() function.
  214.  
  215.     Conclusion
  216.  
  217.     I have used this algorithm in a number of programs with impressive 
  218.     results. If you're looking for a way to speed up your program, check to 
  219.     see if the bottleneck is your string search functions. The Boyer-Moore 
  220.     algorithm will give immediate results.
  221.  
  222.  
  223.     Man at the keyboard: Tom Weitzel #114
  224.                          224 Winthrop Avenue
  225.                          Lawrence MA 01843
  226.                          (508) 975-2834
  227.                          U.S.A.
  228.