About cl-string-match:
no documentation string found
Other functions in cl-string-match
Function build-suffix-tree-simple (str)
Details:
Build a Suffix tree for the given string STR using naive (brute-force) algorithm.
Naive algorithm takes O(m²) time to build a suffix tree where m is the given string length.
Essentially it operates as follows:
while suffices remain: add next shortest suffix to the tree
Algorithm first ads a suffix Str[1..m] (entire string) to thetree. Then it proceeds adding suffices Str[i..m] (i=2..m) to the tree.
Naive algorithm takes O(m²) time to build a suffix tree where m is the given string length.
Essentially it operates as follows:
while suffices remain: add next shortest suffix to the tree
Algorithm first ads a suffix Str[1..m] (entire string) to thetree. Then it proceeds adding suffices Str[i..m] (i=2..m) to the tree.
Function build-suffix-tree-ukkonen (str)
Details:
Build a Suffix tree for the given string STR using Ukkonen's
algorithm.
Ukkonen's algorithm takes O(m) time to build a suffix tree where m is the given string length.
Ukkonen's algorithm is an on-line algorithm and can operate on astream of characters, adding one character at a time.
Ukkonen's algorithm takes O(m) time to build a suffix tree where m is the given string length.
Ukkonen's algorithm is an on-line algorithm and can operate on astream of characters, adding one character at a time.
Function empty-trie ()
Details:
Creates a new instance and returns an empty trie.
Function initialize-ac (patterns)
Details:
Returns a Trie that is used to look for the given patterns in thetext. It can deal either with a single pattern or a list of patterns.
Function initialize-bm (pat)
No documentation string. Possibly unimplemented or incomplete.
Function initialize-bmh (pat)
Details:
Preprocess.Initialize the table to default value.
Function initialize-kmp (pat)
No documentation string. Possibly unimplemented or incomplete.
Function initialize-rk (pat)
No documentation string. Possibly unimplemented or incomplete.
Function make-suffix-tree (&key ((str dum0) ) ((root dum1) nil) ((nodes-count dum2) 0))
No documentation string. Possibly unimplemented or incomplete.
Function make-ukk-node (&key ((start dum911) 0) ((end dum912) 0) ((parent dum913) nil) ((children dum914) nil) ((id dum915) 0) ((suffix dum916) nil))
No documentation string. Possibly unimplemented or incomplete.
Function search-ac (trie txt)
Details:
Looks for patterns that are indexed in the given trie and returns two values:start position of the first matching pattern and its index.
Function search-bm (bm txt)
Details:
Search for pattern bm in txt.
Function search-bmh (bmh txt)
Details:
Search for pattern bm in txt.
Function search-kmp (idx txt)
No documentation string. Possibly unimplemented or incomplete.
Function search-rk (idx txt-s)
Details:
Implementation of the Rabin-Karp substring search algorithm.
Function string-contains-ac (pat txt)
Details:
Looks for the given pattern in the text and returns index of thefirst occurence.
Function string-contains-bm (pat txt)
No documentation string. Possibly unimplemented or incomplete.
Function string-contains-bmh (pat txt)
No documentation string. Possibly unimplemented or incomplete.
Function string-contains-brute (pat txt &key (start1 0) end1 (start2 0) end2)
Details:
A Brute-force substring search implementation.
Brute-force substring search requires O(N x M) character compares to search for a pattern of length M in a text of length N, in the worst case.
Algorithm described in: Chapter 5, p. 760 in 'Algorithms', Robert Sedgewick and Kevin Wayne. 4th
Brute-force substring search requires O(N x M) character compares to search for a pattern of length M in a text of length N, in the worst case.
Algorithm described in: Chapter 5, p. 760 in 'Algorithms', Robert Sedgewick and Kevin Wayne. 4th
Function string-contains-kmp (pat txt)
No documentation string. Possibly unimplemented or incomplete.
Function string-contains-rk (pat txt)
No documentation string. Possibly unimplemented or incomplete.
Function suffix-node.add-child (tree node start end)
Details:
Adds a child node to the given NODE. Depending on the type of the
given node creates either Ukkonens suffix tree or simple suffix treenode.
Function suffix-node.children (instance)
Function suffix-node.end (instance)
Function suffix-node.equals (node-a node-b)
No documentation string. Possibly unimplemented or incomplete.
Function suffix-node.leafp (node)
Details:
Retruns T is the given node is a leaf (has no children), return NILotherwise.
Function suffix-node.map-over-children (node function)
Details:
Applies the given function to every child of the given node.
Function suffix-node.start (instance)
Function suffix-node.str (tree node)
Details:
Returns the string that corresponds to the edge pointing to thisnode.
Function suffix-tree.build-from-sexp (str sexp)
Details:
Build the suffix tree from the given sexp representation. Sexp isin form (begin end (children)).
Function suffix-tree.char (tree i)
Details:
Return the char that is located in the string at index i.
Function suffix-tree.equals (tree-a tree-b)
Details:
Checks all the nodes in the given trees and returns T if trees are equal or NIL otherwise.
Function suffix-tree.root (instance)
Function suffix-tree.str (instance)
Function suffix-tree.walk (tree function)
Details:
Applies the given FUNCTION to every node in the given TREE.
Function trie-add-keyword (trie kw idx)
No documentation string. Possibly unimplemented or incomplete.
Function trie-build (patterns)
Details:
Builds a Trie based on the given list of patterns.
Function trie-contains (trie s)
Details:
Returns T if the given Trie contains the given string.
Function trie-traverse (trie &optional (padding 0) stream)
Details:
Traverse the given trie and pretty-print it to the given stream.
Other classes in cl-string-match
Class suffix-node
Superclasses:
common-lisp:structure-object, sb-pcl::slot-object, common-lisp:t
Documented Subclasses:
Details:
Documentation
Class suffix-tree
Superclasses:
common-lisp:structure-object, sb-pcl::slot-object, common-lisp:t
Documented Subclasses:
None
Details:
ROOT is a SUFFIX-NODE with default values. It is intended to keep
references to its children. ROOT is just a simple placeholder for theactual nodes as its children.
Class trie-node
Superclasses:
common-lisp:structure-object, sb-pcl::slot-object, common-lisp:t
Documented Subclasses:
None
Details:
Each node of a trie contains a list of child nodes, a label (theletter) and a mark (some value attributed to the matching string).
Class ukk-node
Superclasses:
suffix-node, common-lisp:structure-object, sb-pcl::slot-object, common-lisp:t
Documented Subclasses:
None
Details:
Ukkonen's algorithm relies on the suffix link technique. Some other
algorithms might also rely on it but the naive suffix tree algorithm
does not require it.
This structure extends the standard suffix tree node structure with the suffix link slot.
This structure extends the standard suffix tree node structure with the suffix link slot.
Other variables in cl-string-match
Variable +infinity+
No documentation string. Possibly unimplemented or incomplete.
Index of exported symbols
| cl-string-match: | +infinity+, variable (undocumented) |
| cl-string-match: | build-suffix-tree-simple, function |
| cl-string-match: | build-suffix-tree-ukkonen, function |
| cl-string-match: | empty-trie, function |
| cl-string-match: | initialize-ac, function |
| cl-string-match: | initialize-bm, function (undocumented) |
| cl-string-match: | initialize-bmh, function |
| cl-string-match: | initialize-kmp, function (undocumented) |
| cl-string-match: | initialize-rk, function (undocumented) |
| cl-string-match: | make-suffix-tree, function (undocumented) |
| cl-string-match: | make-ukk-node, function (undocumented) |
| cl-string-match: | search-ac, function |
| cl-string-match: | search-bm, function |
| cl-string-match: | search-bmh, function |
| cl-string-match: | search-kmp, function (undocumented) |
| cl-string-match: | search-rk, function |
| cl-string-match: | string-contains-ac, function |
| cl-string-match: | string-contains-bm, function (undocumented) |
| cl-string-match: | string-contains-bmh, function (undocumented) |
| cl-string-match: | string-contains-brute, function |
| cl-string-match: | string-contains-kmp, function (undocumented) |
| cl-string-match: | string-contains-rk, function (undocumented) |
| cl-string-match: | suffix-node, class |
| cl-string-match: | suffix-node.add-child, function |
| cl-string-match: | suffix-node.children, function |
| cl-string-match: | suffix-node.end, function |
| cl-string-match: | suffix-node.equals, function (undocumented) |
| cl-string-match: | suffix-node.leafp, function |
| cl-string-match: | suffix-node.map-over-children, function |
| cl-string-match: | suffix-node.start, function |
| cl-string-match: | suffix-node.str, function |
| cl-string-match: | suffix-tree, class |
| cl-string-match: | suffix-tree.build-from-sexp, function |
| cl-string-match: | suffix-tree.char, function |
| cl-string-match: | suffix-tree.equals, function |
| cl-string-match: | suffix-tree.root, function |
| cl-string-match: | suffix-tree.str, function |
| cl-string-match: | suffix-tree.walk, function |
| cl-string-match: | trie-add-keyword, function (undocumented) |
| cl-string-match: | trie-build, function |
| cl-string-match: | trie-contains, function |
| cl-string-match: | trie-node, class |
| cl-string-match: | trie-traverse, function |
| cl-string-match: | ukk-node, class |