extra/boyer-moore/boyer-moore-docs.factor

   1 ! Copyright (C) 2010 Dmitry Shubin.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: boyer-moore.private help.markup help.syntax kernel sequences ;
   4 IN: boyer-moore
   5
   6 HELP: <boyer-moore>
   7 { $values
   8   { "pattern" sequence } { "boyer-moore" boyer-moore }
   9 }
  10 { $description
  11   "Given a pattern performs pattern preprocessing and returns "
  12   "results as an (opaque) object that is reusable across "
  13   "searches in different sequences via " { $link search-from } "."
  14 } { $examples
  15     { $example
  16         "USING: boyer-moore prettyprint ;"
  17         "\"abc\" <boyer-moore> ."
  18         "T{ boyer-moore
  19     { pattern \"abc\" }
  20     { bad-char-table H{ { 97 0 } { 98 -1 } { 99 -2 } } }
  21     { good-suffix-table { 3 3 1 } }
  22 }"
  23     }
  24 } ;
  25
  26 HELP: search-from
  27 { $values
  28   { "seq" sequence }
  29   { "from" "a non-negative integer" }
  30   { "obj" object }
  31   { "i/f" "the index of first match or " { $link f } }
  32 }
  33 { $contract "Performs an attempt to find the first "
  34   "occurrence of pattern in " { $snippet "seq" }
  35   " starting from " { $snippet "from" } " using "
  36   "Boyer-Moore search algorithm. Output is the index "
  37   "if the attempt was succeessful, or " { $link f }
  38   " otherwise."
  39 } { $examples
  40     { $example
  41         "USING: boyer-moore prettyprint ;"
  42         "{ 1 2 7 10 20 2 7 10 } 3 { 2 7 10 } search-from ."
  43         "5"
  44     }
  45 } ;
  46
  47 HELP: search
  48 { $values
  49   { "seq" sequence }
  50   { "obj" object }
  51   { "i/f" "the index of first match or " { $link f } }
  52 }
  53 { $description "A simpler variant of " { $link search-from }
  54   " that starts searching from the beginning of the sequence."
  55 } { $examples
  56     { $example
  57         "USING: boyer-moore prettyprint ;"
  58         "\"Source string\" \"ce st\" search ."
  59         "4"
  60     }
  61 } ;
  62
  63 ARTICLE: "boyer-moore" "The Boyer-Moore algorithm"
  64 { $heading "Summary" }
  65 "The " { $vocab-link "boyer-moore" } " vocabulary "
  66 "implements a Boyer-Moore string search algorithm with the "
  67 "so-called 'strong good suffix shift rule'. Since the algorithm is "
  68 "alphabet-independent, it is applicable to searching in any "
  69 "collection that implements the " { $links "sequence-protocol" } "."
  70
  71 { $heading "Complexity" }
  72 "Let " { $snippet "n" } " and " { $snippet "m" } " be the lengths "
  73 "of the sequences being searched " { $emphasis "in" } " and "
  74 { $emphasis "for" } " respectively. Then searching runs in "
  75 { $snippet "O(n)" } " time worst-case, using additional "
  76 { $snippet "O(m)" } " space. The preprocessing phase runs in "
  77 { $snippet "O(m)" } " time."
  78 ;
  79
  80 ABOUT: "boyer-moore"