ahocorapy 1.7.0

ahocorapy - Pure python ahocorasick implementation

ahocorapy - Fast Many-Keyword Search in Pure Python

ahocorapy is a pure python implementation of the Aho-Corasick Algorithm. Given a list of keywords one can check if at least one of the keywords exist in a given text in linear time.

Comparison:

Why another Aho-Corasick implementation?

We started working on this in the beginning of 2016. Our requirements included unicode support combined with python2.7. That was impossible with C-extension based libraries (like pyahocorasick). Pure python libraries were very slow or unusable due to memory explosion. Since then another pure python library was released py-aho-corasick. The repository also contains some discussion about different implementations. There is also acora, but it includes the note ('current construction algorithm is not suitable for really large sets of keywords') which really was the case the last time I tested, because RAM ran out quickly.

Differences

• Compared to pyahocorasick our library supports unicode in python 2.7 just like py-aho-corasick. We don't use any C-Extension so the library is not platform dependant.

• On top of the standard Aho-Corasick longest suffix search, we also perform a shortcutting routine in the end, so that our lookup is fast while, the setup takes longer. During set up we go through the states and directly add transitions that are "offered" by the longest suffix or their longest suffixes. This leads to faster lookup times, because in the end we only have to follow simple transitions and don't have to perform any additional suffix lookup. It also leads to a bigger memory footprint, because the number of transitions is higher, because they are all included explicitely and not implicitely hidden by suffix pointers.

• We added a small tool that helps you visualize the resulting graph. This may help understanding the algorithm, if you'd like. See below.

• Fully pickleable (pythons built-in de-/serialization). ahocorapy uses a non-recursive custom implementation for de-/serialization so that even huge keyword trees can be pickled.

Performance

I compared the two libraries mentioned above with ahocorapy. We used 50,000 keywords long list and an input text of 34,199 characters. In the text only one keyword of the list is contained. The setup process was run once per library and the search process was run 100 times. The following results are in seconds (not averaged for the lookup).

You can perform this test yourself using python tests/ahocorapy_performance_test.py. (Except for the pyahocorasick_py results. These were taken by importing the pure python version of the code of pyahocorasick. It's not available through pypi as stated in the code.)

I also added measurements for the pure python libraries with run with pypy.

These are the results:

Library (Variant)	Setup (1x)	Search (100x)
ahocorapy*	0.30s	0.29s
ahocorapy (run with pypy)*	0.37s	0.10s
pyahocorasick*	0.04s	0.04s
pyahocorasick (run with pypy)*	0.10s	0.05s
pyahocorasick (pure python variant in github repo)**	0.50s	1.68s
py_aho_corasick*	0.72s	4,60s
py_aho_corasick (run with pypy)*	0.83s	2.02s

As expected the C-Extension shatters the pure python implementations. Even though there is probably still room for optimization in ahocorapy we are not going to get to the mark that pyahocorasick sets. ahocorapy's lookups are faster than py_aho_corasick. When run with pypy ahocorapy is almost as fast as pyahocorasick, at least when it comes to searching. The setup overhead is higher due to the suffix shortcutting mechanism used.

* Specs

CPU: AMD Ryzen 2700X

Linux Kernel: 6.0.6

CPython: 3.11.0

pypy: PyPy 7.3.9 (Python 3.9.12) with GCC 10.2.1 20210130

Date tested: 2022-11-22

** Old measurement with different specs

Basic Usage:

Installation

pip install ahocorapy

Creation of the Search Tree

from ahocorapy.keywordtree import KeywordTree
kwtree = KeywordTree(case_insensitive=True)
kwtree.add('malaga')
kwtree.add('lacrosse')
kwtree.add('mallorca')
kwtree.add('mallorca bella')
kwtree.add('orca')
kwtree.finalize()

Searching

result = kwtree.search('My favorite islands are malaga and sylt.')
print(result)

Prints :

('malaga', 24)

The search_all method returns a generator for all keywords found, or None if there is none.

results = kwtree.search_all('malheur on mallorca bellacrosse')
for result in results:
    print(result)

Prints :

('mallorca', 11)
('orca', 15)
('mallorca bella', 11)
('lacrosse', 23)

Arbitrary Sequences of Arbitrary Symbols

ahocorapy is not limited to strings. Keywords and search input can be any sequence of hashable symbols. Internally the tree never assumes anything about the symbols beyond that they can be used as dictionary keys, so it works with tuples of integers, byte values, lists of tokens and more.

The only requirements are:

• Each symbol (an element of the sequence) must be hashable.
• Each keyword and the search input must be an iterable that also supports len() (needed to compute match start indices). Strings, tuples, lists and bytes all qualify.

For example, using tuples of integers as keywords:

from ahocorapy.keywordtree import KeywordTree
kwtree = KeywordTree()
kwtree.add((1, 2, 3))
kwtree.add((2, 3, 4))
kwtree.finalize()

result = kwtree.search((9, 1, 2, 3, 4, 8))
print(result)

Prints:

((1, 2, 3), 1)

Using lists of string tokens enables word-level (instead of character-level) matching:

kwtree = KeywordTree()
kwtree.add(['hello', 'world'])
kwtree.finalize()

result = kwtree.search(['say', 'hello', 'world', 'now'])
print(result)

Prints:

(['hello', 'world'], 1)

A note on bytes: in Python 3 iterating over a bytes object yields integers, whereas in Python 2 bytes is an alias for str and yields 1-character strings. Matching works in both cases, but the symbol type differs between the two Python versions.

The case_insensitive=True option is string-specific (it calls .lower() on keywords and input) and therefore only applies when your symbols are strings.

Thread Safety

The construction of the tree is currently NOT thread safe. That means adding shouldn't be called multiple times concurrently. Behavior is undefined.

After finalize is called you can use the search functionality on the same tree from multiple threads at the same time. So that part is thread safe.

Drawing Graph

You can print the underlying graph with the Visualizer class. This feature requires a working pygraphviz library installed.

from ahocorapy_visualizer.visualizer import Visualizer
visualizer = Visualizer()
visualizer.draw('readme_example.png', kwtree)

The resulting .png of the graph looks like this: