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