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   { "pat" sequence } { "bm" 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   " generic word."
  15 } ;
  16
  17 HELP: search-from
  18 { $values
  19   { "seq" sequence }
  20   { "from" "a non-negative integer" }
  21   { "obj" object }
  22   { "i/f" "the index of first match or " { $link f }  }
  23 }
  24 { $description "Performs an attempt to find the first "
  25   "occurence of pattern in " { $snippet "seq" }
  26   " starting from " { $snippet "from" } " using "
  27   "Boyer-Moore search algorithm. Output is the index "
  28   "if the attempt was  succeessful and " { $link f }
  29   " otherwise."
  30 } ;
  31
  32 HELP: search
  33 { $values
  34   { "seq" sequence }
  35   { "obj" object }
  36   { "i/f" "the index of first match or " { $link f } }
  37 }
  38 { $description "A simpler variant of " { $link search-from }
  39   " that starts searching from the beginning of the sequence."
  40 } ;
  41
  42 ARTICLE: "boyer-moore" "The Boyer-Moore algorithm"
  43 { $heading "Summary" }
  44 "The " { $vocab-link "boyer-moore" } " vocabulary "
  45 "implements a Boyer-Moore string search algorithm with "
  46 "so-called 'strong good suffix shift rule'. Since algorithm is "
  47 "alphabet-independent it is applicable to searching in any "
  48 "collection that implements " { $links "sequence-protocol" } "."
  49
  50 { $heading "Complexity" }
  51 "Let " { $snippet "n" } " and " { $snippet "m" } " be lengths "
  52 "of the sequences being searched " { $emphasis "in" } " and "
  53 { $emphasis "for" } " respectively. Then searching runs in "
  54 { $snippet "O(n)" } " time in its worst case using additional "
  55 { $snippet "O(m)" } " space. The preprocessing phase runs in "
  56 { $snippet "O(m)" } " time."
  57 ;
  58
  59 ABOUT: "boyer-moore"