Search a string for multiple substrings at once
Project description
ahocorasick_rs: Quickly search for multiple substrings at once
ahocorasick_rs
allows you to search for multiple substrings ("patterns") in a given string ("haystack") using variations of the Aho-Corasick algorithm.
In particular, it's implemented as a wrapper of the Rust aho-corasick
library, and provides a (sometimes) faster alternative to the pyahocorasick
library.
The specific use case is searching for large numbers of patterns (in the thousands) where the Rust library's DFA-based state machine allows for faster matching.
Quickstart
The ahocorasick_rs
library allows you to search for multiple strings ("patterns") within a haystack.
For example, let's construct a AhoCorasick
object:
>>> import ahocorasick_rs
>>> patterns = ["hello", "world", "fish"2]
>>> haystack = "this is my first hello world. hello!"
>>> ac = ahocorasick_rs.AhoCorasick(patterns)
AhoCorasick.find_matches_as_indexes()
returns a list of tuples, each tuple being:
- The index of the found pattern inside the list of patterns.
- The start index of the pattern inside the haystack.
- 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']
Additional configuration
Match kind
There are three ways you can configure matching in cases where multiple patterns overlap. Assume we have this starting point:
>>> from ahocorasick_rs import *
>>> patterns = ["disco", "disc", "discontent"]
>>> haystack = "discontent"
MATCHKIND_STANDARD
(the default)
This returns the pattern that matches first, semantically-speaking.
>>> AhoCorasick(patterns).find_matches_as_strings(haystack)
['disc']
>>> ac = AhoCorasick(patterns, matchkind=MATCHKIND_STANDARD)
>>> ac.find_matches_as_strings(haystack)
['disc']
In this case disc
will match before disco
or discontent
.
MATCHKIND_LEFTMOST_FIRST
This returns the leftmost matching pattern that appears first in the list of patterns.
>>> ac = AhoCorasick(patterns, matchkind=MATCHKIND_LEFTMOST_FIRST)
>>> ac.find_matches_as_strings(haystack)
['disco']
disco
is returned because it precedes disc
in the list of patterns.
MATCHKIND_LEFTMOST_LONGEST
This returns the leftmost matching pattern that is longest:
>>> ac = AhoCorasick(patterns, matchkind=MATCHKIND_LEFTMOST_LONGEST)
>>> ac.find_matches_as_strings(haystack)
['discontent']
Overlapping matches
You can get all overlapping matches, instead of just one of them, but only if you stick to the default matchkind, MATCHKIND_STANDARD
:
>>> from ahocorasick_rs import AhoCorasick
>>> patterns = ["winter", "onte", "disco", "discontent"]
>>> ac = AhoCorasick(patterns)
>>> ac.find_matches_as_strings("discontent", overlapping=True)
['disco', 'onte', 'discontent']
Implementation details
- The underlying Rust library supports two implementations, one oriented towards reducing memory usage and construction time (NFA), the latter towards faster matching (DFA). The Python wrapper only exposes the DFA version, since expensive setup compensated by fast batch operations is the standard Python tradeoff.
- Matching releases the GIL, to enable concurrency.
- Not all features from the underlying library are exposed; if you would like additional features, please file an issue or submit a PR.
Benchmarks
Based on benchmarks/test_comparison.py
, the benchmark matches ~1,000 patterns against 10,000 lines of text, with (some of?) the benchmarking overhead subtracted.
Lower is better: for longest matching pattern, ahocorasick_rs
is faster.
For overlapping matches, pyahocorasick
is faster.
find_matches_as_strings or equivalent |
milliseconds per 10K |
---|---|
ahocorasick_rs standard matching |
6.12 |
ahocorasick_rs longest matching |
6.89 |
pyahocorasick longest matching |
8.97 |
ahocorasick_rs overlapping matching |
14.96 |
pyahocorasick overlapping matching |
11.38 |
Important: 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!
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for ahocorasick_rs-0.9.0-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 958aa4040ceef9522e6894c192b42359f58ab5be80f5ef7f357ad62e4c1da5c8 |
|
MD5 | 30168de843774eb40833c9bc37706dca |
|
BLAKE2b-256 | d66a94f0a7fae024abcf0039e7dfd62b0f16c9800b5311c8ce85717b723d4331 |
Hashes for ahocorasick_rs-0.9.0-cp39-cp39-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e6877bbc91b3c7796ff19cf0ab7074a0bf8c1d2341716e612aa283c9522d757 |
|
MD5 | dbb3faddd7487f4a970eb3ccaac56bb7 |
|
BLAKE2b-256 | b789ba62e39480511ac28f7ff544bb6b7c001ce224bc1da043c87524bd493a80 |
Hashes for ahocorasick_rs-0.9.0-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3952b03d89b80c1ee252d903eb2853b07d6b37f55db372301c0fc2551dc6d735 |
|
MD5 | 970bbd663ea9f2a89d3d076055ea4885 |
|
BLAKE2b-256 | 032aed4434148f55ec4a3edc9163edd5d5b14c26f273d1092af94695c33393a6 |
Hashes for ahocorasick_rs-0.9.0-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2ef2d48dc82de061d4b9ee486ef2151e285392ce8fd7f098b3ddc45023c6977f |
|
MD5 | 2db634ef0f9cd9a5f71f21a27e293d32 |
|
BLAKE2b-256 | 6604dbfb335d7727cc373504efa9e21d07c1e2dfc3ec02a8bd4d073da5f531b8 |
Hashes for ahocorasick_rs-0.9.0-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3927916ec81283ce6de989afdfd83cf157645afbca19780a1fde93f583935180 |
|
MD5 | cb86c0476a8fe38687d8676857ead23f |
|
BLAKE2b-256 | 858d862c2ebe43d18477bec9deae65246d82c9c427da380842efc65a75703dff |
Hashes for ahocorasick_rs-0.9.0-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a4cfe9a1edb48363bb431606364a853b473b589d7602e9f9b2a159cda30b2f9 |
|
MD5 | cc1af81650b0eded9d194f3e6b06d1d3 |
|
BLAKE2b-256 | 4c65485b20adccc0025dc1b7624e46f437379defa439afce7c5e945cec36cc29 |
Hashes for ahocorasick_rs-0.9.0-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 72743678f41c65299f96bea205f9fa9a1cad0cc237928e8ac41e34edcc558b09 |
|
MD5 | 627775a694b2a855626a97f86e7205b8 |
|
BLAKE2b-256 | f8b5f231b2075f80aa86790f282b95788dd8578ede0f1682643fd44fc4743dd9 |
Hashes for ahocorasick_rs-0.9.0-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b36a5ffc28fe21aace74374779ce3861b8ef73c33a462e512ffc905cabb438e |
|
MD5 | 74c75e5ba0d6e6718c734405374379f7 |
|
BLAKE2b-256 | 8d22c5369345eb4f99572b22c8d561c62eb34f552f52d05a2c462ace535dd6cb |
Hashes for ahocorasick_rs-0.9.0-cp37-cp37m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8487ec12830053ed35a57fa4f9abcfacd008391e3d00d78d114a992818ca6788 |
|
MD5 | e8bd63ac22b4a8bd40726cafc21fb4f1 |
|
BLAKE2b-256 | 5d6630056079cdd39ab34d0b71365569f276d1d24e67dbdb887b3b7b1906ba7f |
Hashes for ahocorasick_rs-0.9.0-cp36-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 95acd076683be5f4d8349a41784c021e278b576d8fab37d1fb760ee389a22d25 |
|
MD5 | 96835e0262089ba4acd4727c62594bd7 |
|
BLAKE2b-256 | 3f724f70329d91fb91f8b644b1850d826063db2f1ab31633ca48fbf6854d1198 |
Hashes for ahocorasick_rs-0.9.0-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ba206fad34c4789aca87d5a33d93968d6931945c0881a12ea89ac716dbbaac2 |
|
MD5 | 5bb7ca0ac33b50b2f05e8036c8db2921 |
|
BLAKE2b-256 | 815eafae03fb11360a9413d9338f0b579eb4b9dcf594fd9ee1543014dbf7602e |
Hashes for ahocorasick_rs-0.9.0-cp36-cp36m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 63169c284fa46196121828d7e4085d283969ed651af75d3963faf9c440952afc |
|
MD5 | 621144b6136c9064a5abf479263731f6 |
|
BLAKE2b-256 | 7b1274498c05b8b385c6a7c35ab20db97f1f27bcd0600e172a67c338fc48a15e |