Repository files navigation

ahocorasick_rs allows you to search for multiple substrings ("patterns") in a given string ("haystack") using variations of theAho-Corasick algorithm.

In particular, it's implemented as a wrapper of the Rustaho-corasick library, and provides a faster alternative to thepyahocorasick library.

Found any problems or have any questions?File an issue on the GitHub project.

• Quickstart
• Choosing the matching algorithm
• Additional configuration: speed and memory usage tradeoffs
• Implementation details
• Benchmarks

Theahocorasick_rs library allows you to search for multiple strings ("patterns") within a haystack, or alternatively search multiple bytes.For example, let's install the library:

$ pip install ahocorasick-rs

We can construct aAhoCorasick object:

>>>importahocorasick_rs>>>patterns= ["hello","world","fish"]>>>haystack="this is my first hello world. hello!">>>ac=ahocorasick_rs.AhoCorasick(patterns)

You can construct aAhoCorasick object from any iterable (including generators), not just lists:

>>>ac=ahocorasick_rs.AhoCorasick((p.lower()forpinpatterns))

AhoCorasick.find_matches_as_indexes() returns a list of tuples, each tuple being:

1. The index of the found pattern inside the list of patterns.
2. The start index of the pattern inside the haystack.
3. The end index of the pattern inside the haystack.

>>>ac.find_matches_as_indexes(haystack)[(0,17,22), (1,23,28), (0,30,35)]>>>patterns[0],patterns[1],patterns[0]('hello','world','hello')>>>haystack[17:22],haystack[23:28],haystack[30:35]('hello','world','hello')

find_matches_as_strings() returns a list of found patterns:

>>>ac.find_matches_as_strings(haystack)['hello','world','hello']

You can also searchbytes,bytearray,memoryview, and other objects supporting the Python buffer API.

>>>patterns= [b"hello",b"world"]>>>ac=ahocorasick_rs.BytesAhoCorasick(patterns)>>>haystack=b"hello world">>>ac.find_matches_as_indexes(b"hello world")[(0,0,5), (1,6,11)]>>>patterns[0],patterns[1](b'hello',b'world')>>>haystack[0:5],haystack[6:11](b'hello',b'world')

Thefind_matches_as_strings() API is not supported byBytesAhoCorasick.

There are three ways you can configure matching in cases where multiple patterns overlap, supported by bothAhoCorasick andBytesAhoCorasick objects.For a more in-depth explanation, see theunderlying Rust library's documentation of matching.

Assume we have this starting point:

>>>fromahocorasick_rsimportAhoCorasick,MatchKind

This returns the pattern that matches first, semantically-speaking.This is the default matching pattern.

>>>acAhoCorasick(["disco","disc","discontent"])>>>ac.find_matches_as_strings("discontent")['disc']>>>ac=AhoCorasick(["b","abcd"])>>>ac.find_matches_as_strings("abcdef")['b']

In this casedisc will match beforedisco ordiscontent.

Similarly,b will match beforeabcd because it ends earlier in the haystack thanabcd does:

>>>ac=AhoCorasick(["b","abcd"])>>>ac.find_matches_as_strings("abcdef")['b']

This returns the leftmost-in-the-haystack matching pattern that appears first inthe list of given patterns.That means the order of patterns makes a difference:

>>>ac=AhoCorasick(["disco","disc"],matchkind=MatchKind.LeftmostFirst)>>>ac.find_matches_as_strings("discontent")['disco']>>>ac=AhoCorasick(["disc","disco"],matchkind=MatchKind.LeftmostFirst)['disc']

Here we seeabcd matched first, because it starts beforeb:

>>>ac=AhoCorasick(["b","abcd"],matchkind=MatchKind.LeftmostFirst)>>>ac.find_matches_as_strings("abcdef")['abcd']

This returns the leftmost-in-the-haystack matching pattern that is longest:

>>>ac=AhoCorasick(["disco","disc","discontent"],matchkind=MatchKind.LeftmostLongest)>>>ac.find_matches_as_strings("discontent")['discontent']

You can get all overlapping matches, instead of just one of them, but only if you stick to the default matchkind,MatchKind.Standard.Again, this is supported by bothAhoCorasick andBytesAhoCorasick.

>>>fromahocorasick_rsimportAhoCorasick>>>patterns= ["winter","onte","disco","discontent"]>>>ac=AhoCorasick(patterns)>>>ac.find_matches_as_strings("discontent",overlapping=True)['disco','onte','discontent']

You can choose the type of underlying automaton to use, with different performance tradeoffs.The short version: if you want maximum matching speed, and you don't have too many patterns, try theImplementation.DFA implementation and see if it helps.

The underlying Rust library supportsfour choices, which are exposed as follows:

• None uses a heuristic to choose the "best" Aho-Corasick implementation for the given patterns, balancing construction time, memory usage, and matching speed.This is the default.
• Implementation.NoncontiguousNFA: A noncontiguous NFA is the fastest to be built, has moderate memory usage and is typically the slowest to execute a search.
• Implementation.ContiguousNFA: A contiguous NFA is a little slower to build than a noncontiguous NFA, has excellent memory usage and is typically a little slower than a DFA for a search.
• Implementation.DFA: A DFA is very slow to build, uses exorbitant amounts of memory, but will typically execute searches the fastest.

>>>fromahocorasick_rsimportAhoCorasick,Implementation>>>ac=AhoCorasick(["disco","disc"],implementation=Implementation.DFA)

If you usefind_matches_as_strings(), there are two ways strings can be constructed: from the haystack, or by caching the patterns on the object.The former takes more work, the latter uses more memory if the patterns would otherwise have been garbage-collected.You can control the behavior by using thestore_patterns keyword argument toAhoCorasick().

• AhoCorasick(..., store_patterns=None): The default.Use a heuristic (currently, whether the total of pattern string lengths is less than 4096 characters) to decide whether to store patterns or not.
• AhoCorasick(..., store_patterns=True): Keep references to the patterns, potentially speeding upfind_matches_as_strings() at the cost of using more memory.If this uses large amounts of memory this might actually slow things down due to pressure on the CPU memory cache, and/or the performance benefit might be overwhelmed by the algorithm's search time.
• AhoCorasick(..., store_patterns=False): Don't keep references to the patterns, saving some memory but potentially slowing downfind_matches_as_strings(), especially when there are only a small number of patterns and you are searching a small haystack.

• Matching on strings releases the GIL, to enable concurrency.Matching on bytes does not currently release the GIL for memory-safety reasons, unless the haystack type isbytes.
• Not all features from the underlying library are exposed; if you would like additional features, pleasefile an issue or submit a PR.

As with any benchmark, real-world results will differ based on your particular situation.If performance is important to your application, measure the alternatives yourself!

That being said, I've seenahocorasick_rs run 1.5× to 7× as fast aspyahocorasick, depending on the options used.You can run the included benchmarks, if you want, to see some comparative results locally.Clone the repository, then:

pip install pytest-benchmark ahocorasick_rs pyahocorasickpytest benchmarks/