home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / turbopas / bmsearch.zip / BOYER.DOC next >
Text File  |  1987-09-08  |  3KB  |  83 lines
  1.     W. Vann Hall
  2.     Pala Designs
  3.     P.O. Box 10804
  4.     Arlington, VA 22210
  5.     CIS 70346,1144
  6.     MCI WVHALL
  7.  
  8.     ABOUT Boyer-MOORE:
  9.  
  10.     Boyer-Moore is an attempt to speed up the usually serial text search.
  11.     Traditionally, text searches proceed from the first character onward.
  12.     (In these examples, "string" refers to string we're trying to locate,
  13.     "text" the array of characters we're trying to find the string in.  
  14.     These all ignore case sensitivity, matching around line boundaries,
  15.     punctuation, etc.)
  16.  
  17.     String to find:        STRING
  18.     Text to find it in:    HOW YOU SEARCH FOR A STRING
  19.  
  20.     Our StringPointer and TextPointer both start at 1.  We compare 
  21.     String[1] and Text[1].  Since "S" and "H" don't match, we increment the 
  22.     text pointer and compare again.  At TextPointer = 9, the "S" of
  23.     "STRING" and the "S" of "SEARCH" match, so we increment TextPointer 
  24.     *and* StringPointer and compare String[2] and Text[10].  "T" and "E" 
  25.     don't match, so we reset StringPointer and increment TextPointer again.  
  26.     And so on.  You can see that it takes 22 comparisons before we locate 
  27.     the correct "S" and a full 27 before we know that we have located 
  28.     "STRING." 
  29.  
  30.     Boyer-Moore, on the other hand, works from the end of the string (but 
  31.     still the beginning of the text).  First, it creates a look-up table of 
  32.     values corresponding to the distance of the first occurence of each 
  33.     character from the end of the string.  For instance, the table for
  34.     "STRING" would read:
  35.  
  36.     A=6  B=6  C=6  D=6  E=6  F=6  G=6  H=6  I=2  J=6  K=6  L=6  M=6
  37.     N=1  O=6  P=6  Q=6  R=3  S=5  T=4  U=6  V=6  W=6  X=6  Y=6  Z=6
  38.  
  39.     Note that characters not located in the string are set to 
  40.     Length(String), as it the final character.  
  41.  
  42.     Since a 6-character string can't be located entirely within the first 5 
  43.     characters, we start by comparing the String[6] -- "G" -- with Text[6]:
  44.     "O".  They don't match, so we increment TextPointer by the value 
  45.     associated with "O" in the table; that is, by 6.  Our next compare is 
  46.     "G" with the "R" in "SEARCH".  We now increment TextPointer by "R"'s 
  47.     value, 3, and compare "S" to " ".  And so on.  Here's a tracing of the 
  48.     progression; the letter to be compared is highlighted by lower casing: 
  49.  
  50.     STRINg
  51.     HOW YoU SEARCH FOR A STRING
  52.  
  53.           STRINg
  54.     HOW YOU SEArCH FOR A STRING
  55.  
  56.              STRINg
  57.     HOW YOU SEARCH^FOR A STRING
  58.  
  59.                    STRINg
  60.     HOW YOU SEARCH FOR A STRING
  61.  
  62.                          STRINg
  63.     HOW YOU SEARCH FOR A STRINg
  64.  
  65.                          STRIng
  66.     HOW YOU SEARCH FOR A STRIng
  67.  
  68.                          STRing
  69.     HOW YOU SEARCH FOR A STRing
  70.  
  71.                          STring
  72.     HOW YOU SEARCH FOR A STring
  73.  
  74.                          String
  75.     HOW YOU SEARCH FOR A String
  76.  
  77.                          string
  78.     HOW YOU SEARCH FOR A string
  79.     
  80.     There; 10 comparisons total.  You can see how this would speed
  81.     searching a long text -- enough to make up for the additional overhead
  82.     of compiling the look-up table.
  83.