Skip to main content

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 install the library:

$ pip install ahocorasick-rs

Then, we can construct a AhoCorasick object:

>>> import ahocorasick_rs
>>> patterns = ["hello", "world", "fish"]
>>> 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:

  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']

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

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!

Longer strings and many patterns

This benchmark matches ~4,000 patterns against lines of text that are ~700 characters long. Each line matches either zero (90%) or one pattern (10%).

Higher is better; ahocorasick_rs is much faster in both cases.

find_matches_as_strings or equivalent Operations per second
ahocorasick_rs longest matching 436,000
pyahocorasick longest matching 65,000
ahocorasick_rs overlapping matching 329,000
pyahocorasick overlapping matching 76,000

Shorter strings and few patterns

This benchmarks matches ~10 patterns against lines of text that are ~70 characters long. Each line matches ~5 patterns.

Higher is better; ahocorasick_rs is faster for longest match, slightly slower for overlapping matches.

find_matches_as_strings or equivalent Operations per second
ahocorasick_rs longest matching 1,730,000
pyahocorasick longest matching 1,120,000
ahocorasick_rs overlapping matching 790,000
pyahocorasick overlapping matching 880,000

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distributions

No source distribution files available for this release.See tutorial on generating distribution archives.

Built Distributions

ahocorasick_rs-0.10.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.whl (522.9 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.5+ x86-64

ahocorasick_rs-0.10.0-cp39-none-win_amd64.whl (170.0 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

ahocorasick_rs-0.10.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl (522.9 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.5+ x86-64

ahocorasick_rs-0.10.0-cp39-cp39-macosx_10_7_x86_64.whl (260.3 kB view hashes)

Uploaded CPython 3.9 macOS 10.7+ x86-64

ahocorasick_rs-0.10.0-cp38-none-win_amd64.whl (170.0 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

ahocorasick_rs-0.10.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl (523.3 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.5+ x86-64

ahocorasick_rs-0.10.0-cp38-cp38-macosx_10_7_x86_64.whl (261.0 kB view hashes)

Uploaded CPython 3.8 macOS 10.7+ x86-64

ahocorasick_rs-0.10.0-cp37-none-win_amd64.whl (169.7 kB view hashes)

Uploaded CPython 3.7 Windows x86-64

ahocorasick_rs-0.10.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl (523.8 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.5+ x86-64

ahocorasick_rs-0.10.0-cp37-cp37m-macosx_10_7_x86_64.whl (260.4 kB view hashes)

Uploaded CPython 3.7m macOS 10.7+ x86-64

ahocorasick_rs-0.10.0-cp36-none-win_amd64.whl (169.7 kB view hashes)

Uploaded CPython 3.6 Windows x86-64

ahocorasick_rs-0.10.0-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl (523.9 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.5+ x86-64

ahocorasick_rs-0.10.0-cp36-cp36m-macosx_10_7_x86_64.whl (260.5 kB view hashes)

Uploaded CPython 3.6m macOS 10.7+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page