| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
AhoCorasick
Description
Aho-Corasick algorithm
The Aho-Corasick algorithm builds an automaton from a set of pattern strings, and then uses it to find positions in a search string where each of the pattern strings occur.
This implementation only works on ByteStrings, to keep things fast. If required it can be adapted to work on other sequence types.
A TrieAC a can be constructed from pattern strings with associated values a, which can be then be turned into an ACRoot a. An ACRoot a can then be run on a search string to find matches. Construction and matching are both lazy.
Sources:
- Alfred V. Aho and Margaret J. Corasick, "Efficient string matching: An aid to bibliographic search", 1975 https://dl.acm.org/doi/10.1145/360825.360855
- Stanford CS166 Aho-Corasick lecture slides https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/04/Slides04.pdf
For complexities below, k is the alphabet range (max 256).
Synopsis
- data TrieAC a
- emptyTAC :: TrieAC a
- insertTAC :: ByteString -> a -> TrieAC a -> TrieAC a
- fromListTAC :: [(ByteString, a)] -> TrieAC a
- data ACRoot a
- fromTrieAC :: TrieAC a -> ACRoot a
- matchAC :: ACRoot a -> ByteString -> [[a]]
Documentation
insertTAC :: ByteString -> a -> TrieAC a -> TrieAC a Source #
Inserts a string with an associated value into a trie. O(n log k) where n is the length of the string.
fromListTAC :: [(ByteString, a)] -> TrieAC a Source #
Builds a trie from a list of strings and associated values. O(n log k) where n is total length of the strings.
fromTrieAC :: TrieAC a -> ACRoot a Source #
Builds an Aho-Corasick automaton from a trie. O(n), where n is the number of nodes in the trie. This is not more than the total length of strings the trie was constructed with.
matchAC :: ACRoot a -> ByteString -> [[a]] Source #
Returns a list of length (m + 1) where m is the length of the search string. This list contains a list of pattern matches for every position in the string, including before the first character. A match at a position is present as the associated value of the pattern string found to be ending at that position. O(m log k + z), where m is the length of the string and z is the total number of matches.