Add: Boyer-Moore string search algorithm

[factor.git] / extra / boyer-moore / boyer-moore-docs.factor

diff --git a/extra/boyer-moore/boyer-moore-docs.factor b/extra/boyer-moore/boyer-moore-docs.factor
new file mode 100644 (file)
index 0000000..994971e
--- /dev/null
+++ b/extra/boyer-moore/boyer-moore-docs.factor
@@ -0,0 +1,59 @@
+! Copyright (C) 2010 Dmitry Shubin.
+! See http://factorcode.org/license.txt for BSD license.
+USING: help.markup help.syntax kernel sequences ;
+IN: boyer-moore
+
+HELP: <boyer-moore>
+{ $values
+  { "pat" sequence } { "bm" object }
+}
+{ $description
+  "Given a pattern performs pattern preprocessing and returns "
+  "results as an (opaque) object that is reusable across "
+  "searches in different sequences via " { $link search-from }
+  " generic word."
+} ;
+
+HELP: search-from
+{ $values
+  { "seq" sequence }
+  { "from" "a non-negative integer" }
+  { "obj" object }
+  { "i/f" "the index of first match or " { $link f }  }
+}
+{ $description "Performs an attempt to find the first "
+  "occurence of pattern in " { $snippet "seq" }
+  " starting from " { $snippet "from" } " using "
+  "Boyer-Moore search algorithm. Output is the index "
+  "if the attempt was  succeessful and " { $link f }
+  " otherwise."
+} ;
+
+HELP: search
+{ $values
+  { "seq" sequence }
+  { "obj" object }
+  { "i/f" "the index of first match or " { $link f } }
+}
+{ $description "A simpler variant of " { $link search-from }
+  " that starts searching from the beginning of the sequence."
+} ;
+
+ARTICLE: "boyer-moore" "The Boyer-Moore algorithm"
+{ $heading "Summary" }
+"The " { $vocab-link "boyer-moore" } " vocabulary "
+"implements a Boyer-Moore string search algorithm with "
+"so-called 'strong good suffix shift rule'. Since agorithm is "
+"alphabet-independent it is applicable to searching in any "
+"collection that implements " { $links "sequence-protocol" } "."
+
+{ $heading "Complexity" }
+"Let " { $snippet "n" } " and " { $snippet "m" } " be lengths "
+"of the sequences being searched " { $emphasis "in" } " and "
+{ $emphasis "for" } " respectively. Then searching runs in "
+{ $snippet "O(n)" } " time in it's worst case using additional "
+{ $snippet "O(m)" } " space. Preprocessing phase runs in "
+{ $snippet "O(m)" } " time."
+;
+
+ABOUT: "boyer-moore"