home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / packer / arc / arctool / searches.doc < prev    next >
Encoding:
Text File  |  1988-09-29  |  3.7 KB  |  89 lines
  1.                        F i l e    I n f o r m a t i o n
  2.  
  3. * DESCRIPTION
  4. Documentation file for SEARCHES.PAS.
  5.  
  6. * ASSOCIATED FILES
  7. SEARCHES.PAS
  8. BOYER.DOC
  9. SEARCHES.DOC
  10.  
  11. }
  12. { SEARCHES  --  A unit for rapidly searching a buffer for a string.
  13.  
  14.   Version 1.00 - 10/26/1987 - Initial release
  15.  
  16.   Scott Bussinger
  17.   Professional Practice Systems
  18.   110 South 131st Street
  19.   Tacoma, WA  98444
  20.   (206)531-8944
  21.   Compuserve 72247,2671
  22.  
  23.   This UNIT for Turbo Pascal version 4.0 provides contains high speed
  24. routines for searching buffers for strings.  To include this unit in your
  25. program add SEARCHES to the USES clause in your main program.
  26.   The unit actually has two routines which do the same thing in different
  27. ways.  The first is BlockPos which takes three parameters; a buffer
  28. containing the data be searched, the size of the buffer and the string to be
  29. searched for.  This routine is written in assembly language with inline code
  30. and is very fast since it takes advantage of special comparison instructions
  31. in the 8086 instruction set.  Note the the buffer is assumed to be based from
  32. a lower index of 1.  The result is the offset of the match within the buffer.
  33. A failure to match returns a 0.  This routine was originally written by Randy
  34. Forgaard for use with Turbo Pascal 3.0.
  35.   The second search routine is based on the Boyer-Moore search algorithm and
  36. is coded strictly in Pascal.  It is MUCH, MUCH slower than BlockPos and is
  37. included only because I felt like converting it and it doesn't hurt anything
  38. to include it in the unit.  Actually, the Boyer-Moore algorithm is quite a
  39. good search algorithm for some cases but doesn't do very well here because
  40. BlockPos is written in assembly language and BoyerMoore isn't.  I don't expect
  41. anyone will use this routine, but for those who want to, there are two steps
  42. to using the BoyerMoore routines.  The first is to process the search string
  43. into a special form for the actual search routine itself.  This procedure is
  44. called MakeBoyerTable and converts a string into a special record type called
  45. a BoyerTable.  This need only be done once for a given search string.  The
  46. second procedure is the search procedure itself and is called BoyerMoore.  For
  47. parameters, it takes the buffer containing data to be searched, the size of
  48. that buffer, the starting location in the buffer (in case you want to continue
  49. a previous search from where you left off), and the BoyerTable you created
  50. using MakeBoyerTable.  Again, the Buffer is assumed to be based from 1 and the
  51. result is the offset where the match was found (0 indicating not found).
  52. These routines are based on some routines written by Van Hall for Turbo Pascal
  53. 3.0 and I've included his original description of the Boyer-Moore algorithm in
  54. a separate file called BOYER.DOC for those who are interested.
  55.   Note that in general, the buffer can contain any data and the search string
  56. need not be text but rather any data in a string form.  For example, to search
  57. for a CR/LF sequence use #13#10 as the search string.
  58.   You can compile this file to create a test program using these routines.  It
  59. allows you to enter a search string and looks in this documentation file for
  60. the chosen string. }
  61.  
  62. program Test;
  63.  
  64. uses Searches;
  65.  
  66. var Buffer: array[1..maxint] of char;
  67.     Size: word;
  68.     Fyle: file;
  69.     Str: string;
  70.     Table: BoyerTable;
  71.  
  72. begin
  73. assign(Fyle,'SEARCHES.DOC');
  74. reset(Fyle,1);
  75. blockread(Fyle,Buffer,maxint,Size);
  76. close(Fyle);
  77. repeat
  78.   write('String to search for:');
  79.   readln(Str);
  80.  
  81.   writeln('  BlockPos = ',BlockPos(Buffer,Size,Str));
  82.  
  83.   MakeBoyerTable(Str,Table);
  84.   writeln('  BoyerMoore = ',BoyerMoore(Buffer,Size,1,Table))
  85.  
  86. until Str = ''
  87. end.
  88. 
  89.