home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / VORX / BOYER.ARC / BOYER.PAS
Pascal/Delphi Source File  |  1986-04-10  |  19KB  |  507 lines
  1.  
  2. PROGRAM TimeTest;
  3.  
  4. { ============================================================================ )
  5.  
  6.     W. Vann Hall
  7.     Pala Designs
  8.     P.O. Box 10804
  9.     Arlington, VA 22210
  10.     CIS 70346,1144
  11.     MCI WVHALL
  12.  
  13. { ============================================================================ )
  14.  
  15.     TimeTest compares the operating speed of two non-Turbo Pos functions 
  16.     that allow a string to be mapped into an array of <= MaxInt chars.  One 
  17.     is a typical search algorithm but is written in InLine machine code; 
  18.     the other is an implementation of the Boyer-Moore search algorithm as 
  19.     described in the September 1984 Scientific American, but coded in Turbo 
  20.     Pascal.  The results are a tad surprising.
  21.  
  22.     Boyer-Moore, as you might guess from the description below, is very 
  23.     dependent on the nature of the search string -- length, false starts, 
  24.     etc.  As a result, comparisons with the InLine BlockPos function vary 
  25.     according to target string.  BlockPos seems about 10 times faster for 
  26.     searches for a short target string with a number of false hits.  It 
  27.     runs about 6 times faster on an unsuccessful search.  However, it only 
  28.     runs about twice as fast in searching for a long string with few false 
  29.     hits.  (Remember, too, that we are comparing apples and oranges here: 
  30.     InLine code against a pure-Turbo implementation.)
  31.  
  32.     Code has been stolen from several places for this demo.  The timer 
  33.     functions are lifted from Neil J. Rubenking's CONTAINS.PAS (available 
  34.     on Borland SIG DL 1 as "CONTAN.PAS"), while the InLine "BlockPos"
  35.     function is a creation of Randy Forgaard and was sent to me in a SIG 
  36.     message.  The careful benchmarker will want to test 500 or more 
  37.     repetitions of the loops instead of 50; the current program takes about 
  38.     3 minutes to compile and run.
  39.     
  40.     ======================================================================
  41.  
  42.     ABOUT Boyer-MOORE:
  43.  
  44.     Boyer-Moore is an attempt to speed up the usually serial text search.
  45.     Traditionally, text searches proceed from the first character onward.
  46.     (In these examples, "string" refers to string we're trying to locate,
  47.     "text" the array of characters we're trying to find the string in.  
  48.     These all ignore case sensitivity, matching around line boundaries,
  49.     punctuation, etc.)
  50.  
  51.     String to find:        STRING
  52.     Text to find it in:    HOW YOU SEARCH FOR A STRING
  53.  
  54.     Our StringPointer and TextPointer both start at 1.  We compare 
  55.     String[1] and Text[1].  Since "S" and "H" don't match, we increment the 
  56.     text pointer and compare again.  At TextPointer = 9, the "S" of 
  57.     "STRING" and the "S" of "SEARCH" match, so we increment TextPointer 
  58.     *and* StringPointer and compare String[2] and Text[10].  "T" and "E" 
  59.     don't match, so we reset StringPointer and increment TextPointer again.  
  60.     And so on.  You can see that it takes 22 comparisons before we locate 
  61.     the correct "S" and a full 27 before we know that we have located 
  62.     "STRING." 
  63.  
  64.     Boyer-Moore, on the other hand, works from the end of the string (but 
  65.     still the beginning of the text).  First, it creates a look-up table of 
  66.     values corresponding to the distance of the first occurence of each 
  67.     character from the end of the string.  For instance, the table for
  68.     "STRING" would read:
  69.  
  70.     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
  71.     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
  72.  
  73.     Note that characters not located in the string are set to 
  74.     Length(String), as it the final character.  
  75.  
  76.     Since a 6-character string can't be located entirely within the first 5 
  77.     characters, we start by comparing the String[6] -- "G" -- with Text[6]: 
  78.     "O".  They don't match, so we increment TextPointer by the value 
  79.     associated with "O" in the table; that is, by 6.  Our next compare is 
  80.     "G" with the "R" in "SEARCH".  We now increment TextPointer by "R"'s 
  81.     value, 3, and compare "S" to " ".  And so on.  Here's a tracing of the 
  82.     progression; the letter to be compared is highlighted by lower casing: 
  83.  
  84.     STRINg
  85.     HOW YoU SEARCH FOR A STRING
  86.  
  87.           STRINg
  88.     HOW YOU SEArCH FOR A STRING
  89.  
  90.              STRINg
  91.     HOW YOU SEARCH^FOR A STRING
  92.  
  93.                    STRINg
  94.     HOW YOU SEARCH FOR A STRING
  95.  
  96.                          STRINg
  97.     HOW YOU SEARCH FOR A STRINg
  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.     There; 10 comparisons total.  You can see how this would speed
  115.     searching a long text -- enough to make up for the additional overhead
  116.     of compiling the look-up table.  
  117.  
  118. ( ============================================================================ }
  119.  
  120. TYPE
  121.  
  122. String255       =   STRING[255];
  123. OnOrOff         =   (On, Off);      { Used by timer function }
  124. ArrayType       =   ARRAY[1..MaxInt] OF CHAR;
  125.  
  126. VAR
  127.  
  128. ByteArray       :   ARRAY[1..MaxInt] OF BYTE;
  129. TextArray       :   ArrayType ABSOLUTE ByteArray;
  130. DummyInt        :   INTEGER;
  131. OK              :   BOOLEAN;
  132. MakeItEasy      :   BYTE;
  133. StringLength    :   BYTE;
  134. FindString      :   String255;
  135. Count           :   BYTE;
  136. ArrayLength     :   INTEGER;
  137. Start           :   REAL;           { Used by timer function }
  138. Time            :   REAL;           { Used by timer function }
  139. CharArray       :   ARRAY[#0..#127] OF BYTE;
  140. CharCount       :   #0..#127;
  141.  
  142. { ============================================================================ )
  143.                             TIMER MODULE BEGINS HERE 
  144.              Timer functions from Neil J. Rubenking's CONTAINS.PAS.
  145.  
  146.       NOTE:  Because checking the time TAKES time, timings for very short 
  147.       events will not be correct.  You will want to time 100, 1000, or even 
  148.       10000 repetitions of short events.  
  149. ( ============================================================================ }
  150.  
  151. PROCEDURE Timer(O : OnOrOff);
  152.  
  153. TYPE
  154.  
  155. RegPack =   RECORD
  156.             ax, bx, cx, dx, bp, si, di, ds, es, flags : Integer;
  157.             END;
  158.  
  159. VAR
  160.  
  161. RecPack :   RegPack;
  162. Hour    :   INTEGER;
  163. Min     :   INTEGER;
  164. Sec     :   INTEGER;
  165. Hun     :   INTEGER;
  166.  
  167. BEGIN
  168.  
  169. WITH RecPack DO
  170.     BEGIN
  171.     ax := $2C SHL 8;
  172.     END;
  173. Intr($21, recpack);       {call interrupt}
  174. WITH RecPack DO
  175.     BEGIN
  176.     Hour := cx SHR 8;
  177.     Min := cx AND $FF;
  178.     Sec := dx SHR 8;
  179.     Hun := dx AND $FF;
  180.     END;
  181. IF O = On THEN
  182.     BEGIN
  183.     Start := Hour*3600+Min*60+Sec+Hun/100;
  184.     Time := 0;
  185.     END
  186. ELSE
  187.     BEGIN
  188.     Time := Hour*3600+Min*60+Sec+Hun/100-Start;
  189.     Start := 0;
  190.     END;
  191. END;                                   { Timer }
  192.  
  193. { ============================================================================ )
  194.                                     BlockPos
  195.                 InLine replacement for the turbo "Pos" function.
  196.  
  197.        By Randy Forgaard, 70307,521.  Uploaded as a Borland SIG message.
  198.  
  199. ( ============================================================================ }
  200.  
  201. FUNCTION BlockPos ( VAR Buffer; 
  202.                         Size:   INTEGER;
  203.                         S   :   String255): INTEGER; 
  204. BEGIN
  205.  
  206.     {Load "buffer" address into ES:DI, "buffer" offset into BX, Length(s) -
  207.      1 into DX, contents of "s[1]" into AL, offset of "s[2]" into SI, and
  208.      "size" - Length(s) + 1 into CX.  If "size" < Length(s), or if
  209.      Length(s) = 0, return zero.}
  210.  
  211.     Inline($1E/               {        PUSH    DS           }
  212.            $16/               {        PUSH    SS           }
  213.            $1F/               {        POP     DS           }
  214.            $C4/$BE/>buffer/   {        LES     DI,buffer[BP]}
  215.            $89/$FB/           {        MOV     BX,DI        }
  216.            $8B/$8E/>size/     {        MOV     CX,size[bp]  }
  217.            $8D/$76/<s+2/      {        LEA     SI,s+2[bp]   }
  218.            $8A/$46/<s+1/      {        MOV     AL,s+1[bp]   }
  219.            $8A/$56/<s/        {        MOV     DL,s[bp]     }
  220.            $84/$D2/           {        TEST    DL,DL        }
  221.            $74/$23/           {        JZ      ERROR        }
  222.            $FE/$CA/           {        DEC     DL           }
  223.            $30/$F6/           {        XOR     DH,DH        }
  224.            $29/$D1/           {        SUB     CX,DX        }
  225.            $76/$1B/           {        JBE     ERROR        }
  226.  
  227.     {Scan the ES:DI buffer, looking for the first occurrence of "s[1]."  If
  228.      not found prior to reaching Length(s) characters before the end of the
  229.      buffer, return zero.  If Length(s) = 1, the entire string has been
  230.      found, so report success.}
  231.  
  232.          $FC/               {        CLD                  }
  233.          $F2/               {NEXT:   REPNE                }
  234.          $AE/               {        SCASB                }
  235.          $75/$16/           {        JNE     ERROR        }
  236.          $85/$D2/           {        TEST    DX,DX        }
  237.          $74/$0C/           {        JZ      FOUND        }
  238.  
  239.     {Compare "s" (which is at SS:SI) with the ES:DI buffer, in both cases
  240.      starting with the first byte just past the length byte of the string.
  241.      If "s" does not match what is at the DI position of the buffer, reset
  242.      the registers to the values they had just prior to the comparison, and
  243.      look again for the next occurrence of the length byte.}
  244.  
  245.            $51/               {        PUSH    CX           }
  246.            $57/               {        PUSH    DI           }
  247.            $56/               {        PUSH    SI           }
  248.            $89/$D1/           {        MOV     CX,DX        }
  249.            $F3/               {        REPE                 }
  250.            $A6/               {        CMPSB                }
  251.            $5E/               {        POP     SI           }
  252.            $5F/               {        POP     DI           }
  253.            $59/               {        POP     CX           }
  254.            $75/$EC/           {        JNE     NEXT         }
  255.  
  256.     {String found in buffer.  Set AX to the offset, within buffer, of the
  257.      first byte of the string (the length byte), assuming that the first
  258.      byte of the buffer is at offset 1.}
  259.  
  260.            $89/$F8/           {FOUND:  MOV     AX,DI        }
  261.            $29/$D8/           {        SUB     AX,BX        }
  262.            $EB/$02/           {        JMP     SHORT RETURN }
  263.  
  264.     {An "error" condition.  Return zero.}
  265.  
  266.            $31/$C0/           {ERROR:  XOR     AX,AX        }
  267.            $1F/               {RETURN: POP     DS           }
  268.            $8B/$E5/           {        MOV     SP,BP        }
  269.            $5D/               {        POP     BP           }
  270.            $C2/$08/$01)       {        RET     108H         }
  271.  
  272.   END {BlockPos};
  273.  
  274. { ============================================================================ )
  275.                                   Boyer-Moore
  276.  
  277.              My implementation of the Boyer-Moore search algorithm.
  278.  
  279.     Simple modifications to make this routine more useful include UpCase-
  280.     ing both the string and the text character to allow case-insensitive 
  281.     matching; allowing a space (#32) in the string to match any number of 
  282.     characters of value #10, #13, or #32, to allow matching around line 
  283.     breaks; and the building of an inverted table and backwards search 
  284.     mechanism, to allow searches for preceding hits (useful interactively; 
  285.     for instance, in a text editor).  
  286.  
  287. ( ============================================================================ }
  288.  
  289. PROCEDURE MakeTable (MatchString    :   String255);
  290.  
  291. VAR
  292.  
  293. StringLength    :   BYTE ABSOLUTE MatchString;
  294.  
  295. VAR
  296.  
  297. Counter :   BYTE;
  298.  
  299. BEGIN
  300. FillChar(CharArray[#0],128,StringLength);
  301. FOR Counter := StringLength-1 DOWNTO 1 DO
  302.     IF CharArray[MatchString[Counter]] = StringLength THEN
  303.         CharArray[MatchString[Counter]] := StringLength-Counter;
  304. END;
  305.  
  306. { ---------------------------------------------------------------------------- }
  307.  
  308. FUNCTION Boyer_Moore( VAR   Buffer      :   ArrayType;
  309.                             StartPointer:   INTEGER;
  310.                             ArraySize   :   INTEGER;
  311.                             MatchString :   String255)  : INTEGER;
  312.  
  313. VAR
  314.  
  315. ArrayPointer    :   INTEGER;
  316. StringLength    :   BYTE ABSOLUTE MatchString;
  317. StringPointer   :   BYTE;
  318.  
  319. BEGIN
  320. StringPointer := StringLength;
  321. ArrayPointer := (StartPointer+StringLength)-1;
  322. REPEAT
  323. IF Buffer[ArrayPointer] = MatchString[StringPointer] THEN
  324.     BEGIN
  325.     ArrayPointer := Pred(ArrayPointer);
  326.     StringPointer := Pred(StringPointer);
  327.     END
  328. ELSE
  329.     BEGIN
  330.     StringPointer := StringLength;
  331.     ArrayPointer := ArrayPointer+CharArray[Buffer[ArrayPointer]];
  332.     END;
  333. UNTIL (StringPointer = 0) OR (ArrayPointer >= ArrayLength);
  334. IF NOT (StringPointer = 0) THEN
  335.     Boyer_Moore := 0
  336. ELSE
  337.     Boyer_Moore := ArrayPointer+1;
  338. END;
  339.  
  340. { ============================================================================ )
  341.                            Simple readfile operation.
  342.               Uses source for this program as text to be searched.
  343. ( ============================================================================ }
  344.  
  345. PROCEDURE ReadFile (NameStr     :   String255);
  346.  
  347. VAR
  348.  
  349. InFile      :   FILE;
  350. CharFile    :   FILE OF CHAR;
  351. Records     :   INTEGER;
  352.  
  353. BEGIN
  354. Assign(InFile,NameStr);
  355. Reset(InFile);
  356. Records := FileSize(InFile);
  357. BlockRead(InFile,ByteArray,Records);
  358. Close(InFile);
  359. Assign(CharFile,NameStr);
  360. Reset(CharFile);
  361. ArrayLength := FileSize(CharFile);
  362. Close(CharFile);
  363. End;
  364.  
  365. { ============================================================================ )
  366.                                       MAIN
  367.     This program tests 50 repetitions of the BlockPos and Boyer-Moore 
  368.     functions, with several variations, using the program's source code for 
  369.     the text to be searched.  As given here, both search functions are 
  370.     case-sensitive; thus, the target string is given in lower-case in the 
  371.     source code and then UpCased.  This allows us to be certain, for 
  372.     example, that the "end." matched in some of the tests is the upper-case 
  373.     "end." at the close of the source and not the "end." in thios sentence.
  374.  
  375.     Variations include searches for a short string ("end.") with many false 
  376.     hits (on "end;"); searches for a longer, less ambiguous string; unsuc-
  377.     cessful searches; and searches for repeated occurences of a word (in 
  378.     Boyer-Moore, only).  In addition, the MakeTable procedure is included 
  379.     in one of the Boyer-Moore loops in the first test to show that construct-
  380.     ing the table takes little time.  
  381.  
  382. ( ============================================================================ }
  383.  
  384. BEGIN
  385. ClrScr;
  386. ReadFile('NEWCON.PAS');
  387.  
  388. { ------ Test 1 --------------------- }
  389.  
  390. FindString := 'end.';
  391. FOR Count := 1 TO Ord(FindString[0]) DO
  392.     FindString[Count] := UpCase(FindString[Count]);
  393.  
  394. WriteLn('Test of BlockPos function ');
  395. Write('50 successful tries (with many false hits) take ');
  396. timer(on);
  397. FOR Count := 1 TO 50 DO
  398.     DummyInt := BlockPos(TextArray,ArrayLength,FindString);
  399. timer(off);
  400. WriteLn( time:1:2, ' seconds');
  401. Writeln;
  402.  
  403. WriteLn('Test of Boyer-Moore function (MakeTable in loop)');
  404. Write('50 successful tries (with many false hits) take ');
  405. timer(on);
  406. FOR Count := 1 TO 50 DO
  407.     BEGIN
  408.     MakeTable(FindString);
  409.     DummyInt := Boyer_Moore(TextArray,1,ArrayLength,FindString);
  410.     END;
  411. timer(off);
  412. WriteLn( time:1:2, ' seconds');
  413. Writeln;
  414.  
  415. WriteLn('Test of Boyer-Moore function (MakeTable not in loop)');
  416. Write('50 successful tries (with many false hits) take ');
  417. timer(on);
  418. MakeTable(FindString);
  419. FOR Count := 1 TO 50 DO
  420.     DummyInt := Boyer_Moore(TextArray,1,ArrayLength,FindString);
  421. timer(off);
  422. WriteLn( time:1:2, ' seconds');
  423. Writeln;
  424.  
  425. { ------ Test 2 --------------------- }
  426.  
  427. FindString := 'few screwy hits with this zany target';
  428. FOR Count := 1 TO Ord(FindString[0]) DO
  429.     FindString[Count] := UpCase(FindString[Count]);
  430.  
  431. WriteLn('Test of BlockPos function ');
  432. Write('50 successful tries (with few false hits) take ');
  433. timer(on);
  434. FOR Count := 1 TO 50 DO
  435.     DummyInt := BlockPos(TextArray,ArrayLength,FindString);
  436. timer(off);
  437. WriteLn( time:1:2, ' seconds');
  438. Writeln;
  439.  
  440. WriteLn('Test of Boyer-Moore function (MakeTable not in loop)');
  441. Write('50 successful tries (with few false hits) take ');
  442. timer(on);
  443. MakeTable(FindString);
  444. FOR Count := 1 TO 50 DO
  445.     DummyInt := Boyer_Moore(TextArray,1,ArrayLength,FindString);
  446. timer(off);
  447. WriteLn( time:1:2, ' seconds');
  448. Writeln;
  449.  
  450. { ------ Test 3 --------------------- }
  451.  
  452. FindString := 'not here.';
  453. FOR Count := 1 TO Ord(FindString[0]) DO
  454.     FindString[Count] := UpCase(FindString[Count]);
  455.  
  456. WriteLn('Test of BlockPos function ');
  457. Write('50 unsuccessful tries take ');
  458. timer(on);
  459. FOR Count := 1 TO 50 DO
  460.     DummyInt := BlockPos(TextArray,ArrayLength,FindString);
  461. timer(off);
  462. WriteLn( time:1:2, ' seconds');
  463. Writeln;
  464.  
  465. WriteLn('Test of Boyer-Moore function (MakeTable not in loop)');
  466. Write('50 unsuccessful tries take ');
  467. timer(on);
  468. MakeTable(FindString);
  469. FOR Count := 1 TO 50 DO
  470.     DummyInt := Boyer_Moore(TextArray,1,ArrayLength,FindString);
  471. timer(off);
  472. WriteLn( time:1:2, ' seconds');
  473. Writeln;
  474.  
  475. { ------ Test 4 --------------------- }
  476.  
  477. FindString := 'fake';
  478. FOR Count := 1 TO Ord(FindString[0]) DO
  479.     FindString[Count] := UpCase(FindString[Count]);
  480.  
  481. WriteLn('Test of repeating Boyer-Moore function ');
  482. Write('50 successful tries (with few false hits) take ');
  483. timer(on);
  484. DummyInt := 1;
  485. MakeTable(FindString);
  486. FOR Count := 1 TO 50 DO
  487.     BEGIN
  488.     DummyInt := Boyer_Moore(TextArray,DummyInt,ArrayLength,FindString);
  489.     END;
  490. timer(off);
  491. WriteLn( time:1:2, ' seconds');
  492.  
  493. { ============================== TARGET STRINGS ============================== }
  494.  
  495. {
  496.        FEW SCREWY HITS WITH THIS ZANY TARGET
  497.        FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE
  498.        FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE
  499.        FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE
  500.        FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE
  501.        FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE FAKE
  502. }
  503.  
  504. END.
  505. 
  506.  
  507. Press <CR> to continue: