home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / tug__002 / searches.doc < prev    next >
Encoding:
Text File  |  1988-08-14  |  5.2 KB  |  126 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 for SEARCHES.PAS.
  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. { SEARCHES  --  A unit for rapidly searching a buffer for a string.
  51.  
  52.   Version 1.00 - 10/26/1987 - Initial release
  53.  
  54.   Scott Bussinger
  55.   Professional Practice Systems
  56.   110 South 131st Street
  57.   Tacoma, WA  98444
  58.   (206)531-8944
  59.   Compuserve 72247,2671
  60.  
  61.   This UNIT for Turbo Pascal version 4.0 provides contains high speed
  62. routines for searching buffers for strings.  To include this unit in your
  63. program add SEARCHES to the USES clause in your main program.
  64.   The unit actually has two routines which do the same thing in different
  65. ways.  The first is BlockPos which takes three parameters; a buffer
  66. containing the data be searched, the size of the buffer and the string to be
  67. searched for.  This routine is written in assembly language with inline code
  68. and is very fast since it takes advantage of special comparison instructions
  69. in the 8086 instruction set.  Note the the buffer is assumed to be based from
  70. a lower index of 1.  The result is the offset of the match within the buffer.
  71. A failure to match returns a 0.  This routine was originally written by Randy
  72. Forgaard for use with Turbo Pascal 3.0.
  73.   The second search routine is based on the Boyer-Moore search algorithm and
  74. is coded strictly in Pascal.  It is MUCH, MUCH slower than BlockPos and is
  75. included only because I felt like converting it and it doesn't hurt anything
  76. to include it in the unit.  Actually, the Boyer-Moore algorithm is quite a
  77. good search algorithm for some cases but doesn't do very well here because
  78. BlockPos is written in assembly language and BoyerMoore isn't.  I don't expect
  79. anyone will use this routine, but for those who want to, there are two steps
  80. to using the BoyerMoore routines.  The first is to process the search string
  81. into a special form for the actual search routine itself.  This procedure is
  82. called MakeBoyerTable and converts a string into a special record type called
  83. a BoyerTable.  This need only be done once for a given search string.  The
  84. second procedure is the search procedure itself and is called BoyerMoore.  For
  85. parameters, it takes the buffer containing data to be searched, the size of
  86. that buffer, the starting location in the buffer (in case you want to continue
  87. a previous search from where you left off), and the BoyerTable you created
  88. using MakeBoyerTable.  Again, the Buffer is assumed to be based from 1 and the
  89. result is the offset where the match was found (0 indicating not found).
  90. These routines are based on some routines written by Van Hall for Turbo Pascal
  91. 3.0 and I've included his original description of the Boyer-Moore algorithm in
  92. a separate file called BOYER.DOC for those who are interested.
  93.   Note that in general, the buffer can contain any data and the search string
  94. need not be text but rather any data in a string form.  For example, to search
  95. for a CR/LF sequence use #13#10 as the search string.
  96.   You can compile this file to create a test program using these routines.  It
  97. allows you to enter a search string and looks in this documentation file for
  98. the chosen string. }
  99.  
  100. program Test;
  101.  
  102. uses Searches;
  103.  
  104. var Buffer: array[1..maxint] of char;
  105.     Size: word;
  106.     Fyle: file;
  107.     Str: string;
  108.     Table: BoyerTable;
  109.  
  110. begin
  111. assign(Fyle,'SEARCHES.DOC');
  112. reset(Fyle,1);
  113. blockread(Fyle,Buffer,maxint,Size);
  114. close(Fyle);
  115. repeat
  116.   write('String to search for:');
  117.   readln(Str);
  118.  
  119.   writeln('  BlockPos = ',BlockPos(Buffer,Size,Str));
  120.  
  121.   MakeBoyerTable(Str,Table);
  122.   writeln('  BoyerMoore = ',BoyerMoore(Buffer,Size,1,Table))
  123.  
  124. until Str = ''
  125. end.
  126.