home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1725 < prev    next >
Text File  |  1990-12-28  |  7KB  |  210 lines
  1. Newsgroups: alt.sources
  2. From: chris@mimsy.umd.edu (Chris Torek)
  3. Subject: [comp.lang.c] Re: strstr sources: a summary of responses
  4. Message-ID: <1990Aug27.191251.21720@math.lsa.umich.edu>
  5. Date: Mon, 27 Aug 90 19:12:51 GMT
  6.  
  7. Archive-name: torek-boyer-moore/27-Aug-90
  8. Original-posting-by: chris@mimsy.umd.edu (Chris Torek)
  9. Original-subject: Re: strstr sources: a summary of responses
  10. Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
  11.  
  12. [Reposted from comp.lang.c.
  13. Comments on this service to emv@math.lsa.umich.edu (Edward Vielmetti).]
  14.  
  15. In article <1158@umvlsi.ecs.umass.edu> srivasta@umvlsi.ecs.umass.edu
  16. (Manoj Srivastava) posts a Boyer-Moore based strstr() by John Lacey.
  17.  
  18. >And finally, an implementation of the Boyer-Moore algorithm. I
  19. >am not sure offhand, but while the worst case complexity remains
  20. >O(N+M), the avg case behaviour is O(N/M) ???
  21.  
  22. (where N is the length of the string being searched and M is the length
  23. of the substring, aka pattern).  Yes, it is N/M.
  24.  
  25. Next, the code:
  26.  
  27. >/* strstr, Copyright (c) 1990 by John Lacey.  -*- C -*-
  28.  [some stuff deleted]
  29. >int ch, d[SCHAR_MAX + 1];
  30.  [more stuff deleted]
  31. >      i += d[text[i]];
  32.  [still more deleted]
  33.  
  34. If `char' is signed, and a string containing a negative character value
  35. is passed to strstr(), thid code can attempt to fetch, e.g., d[-40].  I
  36. found the code overy difficult to read, so I rewrote it.  I also wrote
  37. a long comment describing the algorithm.  This has been only lightly
  38. tested, but is simple enough that it should work.  Note that this
  39. version handles strings with embedded NUL characters as well.
  40.  
  41. (A real B-M search routine should take the deltas table as an argument,
  42. and have a separate routine to set it up, so that the same pattern can
  43. be applied to multiple texts.  E.g., a `Boyer-Moore grep' would read a
  44. line at a time and apply this search to each line.  See comment.)
  45.  
  46. #include <limits.h>
  47. #include <stddef.h>
  48. typedef void *PTR;        /* `char *' for old compilers */
  49.  
  50. /*
  51.  * Boyer-Moore search: input is `text' (a string) and its length,
  52.  * and a `pattern' (another string) and its length.
  53.  *
  54.  * The linear setup cost of this function is approximately 256 + patlen.
  55.  * Afterwards, however, the average cost is O(textlen/patlen), and the
  56.  * worst case is O(textlen+patlen).
  57.  *
  58.  * The Boyer-Moore algorithm works by observing that, for each position
  59.  * in the text, if the character there does *not* occur somewhere in the
  60.  * search pattern, no comparisons including that character will match.
  61.  * That is, given the text "hello world..." and the pattern "goodbye", the
  62.  * `w' in `world' means that none of `hello w', `ello wo', `llo wor',
  63.  * `lo worl', `o world', ` world.', and `world..' can match.  In fact,
  64.  * exactly patlen strings are certain not to match.  We can discover this
  65.  * simply by looking at the patlen'th character.  Furthermore, even if
  66.  * the text character does occur, it may be that it rules out some number
  67.  * of other matches.  Again, we can discover this by doing the match
  68.  * `backwards'.
  69.  *
  70.  * We set up a table of deltas for each possible character, with
  71.  * delta[character] being patlen for characters not in the pattern,
  72.  * less for characters in the pattern, growing progressively smaller
  73.  * as we near the end of the pattern.  Matching then works as follows:
  74.  *
  75.  *     0         1         2         3
  76.  *     01234567890123456789012345678901234567
  77.  *    "Here is the string being searched into"    (text)
  78.  *     ------                        (pos = [0..5])
  79.  *    "string"                    (pat)
  80.  *    654321-                        (deltas)
  81.  *
  82.  * (the delta for `-' will be derived below).
  83.  *
  84.  * Positions 0..5 end with `i', which is not the `g' we want.  `i' does
  85.  * appear in `string', but two characters before the end.  We skip
  86.  * forward so as to make the `i's match up:
  87.  *
  88.  *    "Here is the string being searched into"    (text)
  89.  *      "string"                    (pos = [2..7])
  90.  *
  91.  * Next we find that ` ' and `g' do not match.  Since ` ' does not appear
  92.  * in the pattern at all, we can skip forward 6:
  93.  *
  94.  *    "Here is the string being searched into"    (text)
  95.  *        "string"                (pos = [8..13])
  96.  *
  97.  * Comparing `t' vs `g', we again find no match, and so we obtain the
  98.  * delta for `t', which is 4.  We skip to position 17:
  99.  *
  100.  *    "Here is the string being searched into"    (text)
  101.  *            "string"                (pos = [12..17])
  102.  *
  103.  * It thus takes only four steps to move the search point forward to the
  104.  * match, in this case.
  105.  *
  106.  * If the pattern has a recurring character, we must set the delta for
  107.  * that character to the distance of the one closest to the end:
  108.  *
  109.  *     "befuddle the cat"    (text)
  110.  *    "fuddle"        (pos = [0..5])
  111.  *    654321-            (delta)
  112.  *
  113.  * We want the next search to line the `d's up like this:
  114.  *
  115.  *     "befuddle the cat"    (text)
  116.  *      "fuddle"        (pos = [2..7])
  117.  *
  118.  * and not like this:
  119.  *
  120.  *     "befuddle the cat"    (text)
  121.  *       "fuddle"        (pos = [3..8])
  122.  *
  123.  * so we take the smaller delta for d, i.e., 2.
  124.  *
  125.  * The last task is computing the delta we have noted above as `-':
  126.  *
  127.  *    "candlesticks"        (text)
  128.  *    "hand"            (pos = [0..3])
  129.  *    4321-            (delta)
  130.  *
  131.  * Here the `d' in `hand' matches the `d' in `candlesticks', but the
  132.  * strings differ.  Since there are no other `d's in `hand', we know
  133.  * that none of (cand,andl,ndle,dles) can match, and thus we want this
  134.  * delta to be 4 (the length of the pattern).  But if we had, e.g.:
  135.  *
  136.  *    "candlesticks"        (text)
  137.  *    "deed"            (pos = [0..3])
  138.  *    4321-            (delta)
  139.  *
  140.  * then we should advance to line up the other `d':
  141.  *
  142.  *    "candlesticks"        (text)
  143.  *       "deed"        (pos = [3..6])
  144.  *
  145.  * As this suggestes, the delta should be that for the `d' nearest the
  146.  * end, but not including the end.  This is easily managed by setting up
  147.  * a delta table as follows:
  148.  *
  149.  *    for int:c in [0..255] { delta[c] = patlen; };
  150.  *    for int:x in [0..patlen-1) { delta[pat[x]] = patlen - (x + 1); };
  151.  *
  152.  * delta[pat[patlen-1]] is never written, so the last letter inherits the
  153.  * delta from an earlier iteration or from the previous loop.
  154.  *
  155.  * NB: the nonsense with `deltaspace' below exists merely because gcc
  156.  * does a horrible job of common subexpression elimination (it does not
  157.  * notice that the array is at a constant stack address).
  158.  */
  159. char *
  160. boyer_moore_search(text, textlen, pat, patlen)
  161.     char *text;
  162.     size_t textlen;
  163.     char *pat;
  164.     size_t patlen;
  165. {
  166.     register unsigned char *p, *t;
  167.     register size_t i, p1, j, *delta;
  168.     size_t deltaspace[UCHAR_MAX + 1];
  169.  
  170.     /* algorithm fails if pattern is empty */
  171.     if ((p1 = patlen) == 0)
  172.         return (text);
  173.  
  174.     /* code below fails (whenever i is unsigned) if pattern too long */
  175.     if (p1 > textlen)
  176.         return (NULL);
  177.  
  178.     /* set up deltas */
  179.     delta = deltaspace;
  180.     for (i = 0; i <= UCHAR_MAX; i++)
  181.         delta[i] = p1;
  182.     for (p = (unsigned char *)pat, i = p1; --i > 0;)
  183.         delta[*p++] = i;
  184.  
  185.     /*
  186.      * From now on, we want patlen - 1.
  187.      * In the loop below, p points to the end of the pattern,
  188.      * t points to the end of the text to be tested against the
  189.      * pattern, and i counts the amount of text remaining, not
  190.      * including the part to be tested.
  191.      */
  192.     p1--;
  193.     p = (unsigned char *)pat + p1;
  194.     t = (unsigned char *)text + p1;
  195.     i = textlen - patlen;
  196.     for (;;) {
  197.         if (*p == *t && memcmp((PTR)(p - p1), (PTR)(t - p1), p1) == 0)
  198.             return ((char *)t - p1);
  199.         j = delta[*t];
  200.         if (i < j)
  201.             break;
  202.         i -= j;
  203.         t += j;
  204.     }
  205.     return (NULL);
  206. }
  207. -- 
  208. In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
  209. Domain:    chris@cs.umd.edu    Path:    uunet!mimsy!chris
  210.