home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / tug__002 / boyer.doc < prev    next >
Encoding:
Text File  |  1988-08-14  |  4.8 KB  |  132 lines
  1. TUG PDS CERT 1.01 (Documentation)
  2.  
  3. ==========================================================================
  4.  
  5.                   TUG PUBLIC DOMAIN SOFTWARE CERTIFICATION
  6.  
  7. The Turbo User Group (TUG) is recognized by Borland International as the
  8. official support organization for Turbo languages.  This file has been
  9. verified by the TUG library staff.  We are reasonably certain that the
  10. information contained in this file is public domain material, but
  11. it is also subject to any restrictions applied by its author.
  12.  
  13. This diskette contains information determined to be in the PUBLIC
  14. DOMAIN, provided as a service of TUG for the use of its members.  The
  15. Turbo User Group will not be liable for any damages, including any lost
  16. profits, lost savings or other incidental or consequential damages arising
  17. out of the use of or inability to use the contents, even if TUG has been
  18. advised of the possibility of such damages, or for any claim by any
  19. other party.
  20.  
  21. To the best of our knowledge, the information in this file is accurate.
  22.  
  23. If you discover an error in this file, we would appreciate it if you would
  24. report it to us.  To report bugs, or to request information on membership
  25. in TUG, please contact us at:
  26.  
  27.              Turbo User Group
  28.              PO Box 1510
  29.              Poulsbo, Washington USA  98370
  30.  
  31. --------------------------------------------------------------------------
  32.                        F i l e    I n f o r m a t i o n
  33.  
  34. * DESCRIPTION
  35. Documentation file explaining about Boyer-MOORE.
  36.  
  37. * ASSOCIATED FILES
  38. SEARCHES.PAS
  39. BOYER.DOC
  40. SEARCHES.DOC
  41.  
  42. * CHECKED BY
  43. DRM - 08/14/88
  44.  
  45. * KEYWORDS
  46. TURBO PASCAL V4.0 DOCUMENTATION SEARCH INLINE
  47.  
  48. ==========================================================================
  49. }
  50.     W. Vann Hall
  51.     Pala Designs
  52.     P.O. Box 10804
  53.     Arlington, VA 22210
  54.     CIS 70346,1144
  55.     MCI WVHALL
  56.  
  57.     ABOUT Boyer-MOORE:
  58.  
  59.     Boyer-Moore is an attempt to speed up the usually serial text search.
  60.     Traditionally, text searches proceed from the first character onward.
  61.     (In these examples, "string" refers to string we're trying to locate,
  62.     "text" the array of characters we're trying to find the string in.  
  63.     These all ignore case sensitivity, matching around line boundaries,
  64.     punctuation, etc.)
  65.  
  66.     String to find:        STRING
  67.     Text to find it in:    HOW YOU SEARCH FOR A STRING
  68.  
  69.     Our StringPointer and TextPointer both start at 1.  We compare 
  70.     String[1] and Text[1].  Since "S" and "H" don't match, we increment the 
  71.     text pointer and compare again.  At TextPointer = 9, the "S" of
  72.     "STRING" and the "S" of "SEARCH" match, so we increment TextPointer 
  73.     *and* StringPointer and compare String[2] and Text[10].  "T" and "E" 
  74.     don't match, so we reset StringPointer and increment TextPointer again.  
  75.     And so on.  You can see that it takes 22 comparisons before we locate 
  76.     the correct "S" and a full 27 before we know that we have located 
  77.     "STRING." 
  78.  
  79.     Boyer-Moore, on the other hand, works from the end of the string (but 
  80.     still the beginning of the text).  First, it creates a look-up table of 
  81.     values corresponding to the distance of the first occurence of each 
  82.     character from the end of the string.  For instance, the table for
  83.     "STRING" would read:
  84.  
  85.     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
  86.     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
  87.  
  88.     Note that characters not located in the string are set to 
  89.     Length(String), as it the final character.  
  90.  
  91.     Since a 6-character string can't be located entirely within the first 5 
  92.     characters, we start by comparing the String[6] -- "G" -- with Text[6]:
  93.     "O".  They don't match, so we increment TextPointer by the value 
  94.     associated with "O" in the table; that is, by 6.  Our next compare is 
  95.     "G" with the "R" in "SEARCH".  We now increment TextPointer by "R"'s 
  96.     value, 3, and compare "S" to " ".  And so on.  Here's a tracing of the 
  97.     progression; the letter to be compared is highlighted by lower casing: 
  98.  
  99.     STRINg
  100.     HOW YoU SEARCH FOR A STRING
  101.  
  102.           STRINg
  103.     HOW YOU SEArCH FOR A STRING
  104.  
  105.              STRINg
  106.     HOW YOU SEARCH^FOR A STRING
  107.  
  108.                    STRINg
  109.     HOW YOU SEARCH FOR A STRING
  110.  
  111.                          STRINg
  112.     HOW YOU SEARCH FOR A STRINg
  113.  
  114.                          STRIng
  115.     HOW YOU SEARCH FOR A STRIng
  116.  
  117.                          STRing
  118.     HOW YOU SEARCH FOR A STRing
  119.  
  120.                          STring
  121.     HOW YOU SEARCH FOR A STring
  122.  
  123.                          String
  124.     HOW YOU SEARCH FOR A String
  125.  
  126.                          string
  127.     HOW YOU SEARCH FOR A string
  128.     
  129.     There; 10 comparisons total.  You can see how this would speed
  130.     searching a long text -- enough to make up for the additional overhead
  131.     of compiling the look-up table.
  132.