Alfred–Margaret is a fast implementation of the Aho–Corasick string searching algorithm in Haskell. It powers many string-related operations in Channable.
The library is designed to work with the text package. It matches
directly on the internal UTF-16 representation of Text for efficiency. See the
announcement blog post for a deeper dive into Aho–Corasick, and the
optimizations that make this library fast.
Alfred–Margaret is named after Alfred Aho and Margaret Corasick.
Running time to count all matches, in a real-world data set, comparing a Java implementation and a Rust implementation against Alfred–Margaret, and against memcopy to establish a lower bound:
For the full details of this benchmark, see our announcement blog post, which includes more details about the data set, the benchmark setup, and a few things to keep in mind when interpreting this graph.
Check if a string contains one of the needles:
import qualified Data.Text.AhoCorasick.Searcher as Searcher
searcher = Searcher.build ["tshirt", "shirts", "shorts"]
Searcher.containsAny searcher "short tshirts"
> True
Searcher.containsAny searcher "long shirt"
> False
Searcher.containsAny searcher "Short TSHIRTS"
> False
Searcher.containsAnyIgnoreCase searcher "Short TSHIRTS"
> TrueSequentially replace many needles:
import Data.Text.AhoCorasick.Automaton (CaseSensitivity (..))
import qualified Data.Text.AhoCorasick.Replacer as Replacer
replacer = Replacer.build CaseSensitive [("tshirt", "banana"), ("shirt", "pear")]
Replacer.run replacer "tshirts for sale"
> "bananas for sale"
Replacer.run replacer "tshirts and shirts for sale"
> "bananas and pears for sale"
Replacer.run replacer "sweatshirts and shirtshirts"
> "sweabananas and shirbananas"
Replacer.run replacer "sweatshirts and shirttshirts"
> "sweabananas and pearbananas"Get all matches, possibly overlapping:
import qualified Data.Text.AhoCorasick.Automaton as Aho
pairNeedleWithSelf text = (Aho.unpackUtf16 text, text)
automaton = Aho.build $ fmap pairNeedleWithSelf ["tshirt", "shirts", "shorts"]
allMatches = Aho.runText [] (\matches match -> Aho.Step (match : matches))
allMatches automaton "short tshirts"
> [ Match {matchPos = CodeUnitIndex 13, matchValue = "shirts"}
> , Match {matchPos = CodeUnitIndex 12, matchValue = "tshirt"}
> ]
allMatches automaton "sweatshirts and shirtshirts"
> [ Match {matchPos = CodeUnitIndex 27, matchValue = "shirts"}
> , Match {matchPos = CodeUnitIndex 26, matchValue = "tshirt"}
> , Match {matchPos = CodeUnitIndex 22, matchValue = "shirts"}
> , Match {matchPos = CodeUnitIndex 11, matchValue = "shirts"}
> , Match {matchPos = CodeUnitIndex 10, matchValue = "tshirt"}
> ]Alfred–Margaret is licensed under the 3-clause BSD license.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent