repository·master·Indexed 22 days ago
https://github.com/wojciechmula/pyahocorasickA fast, memory-efficient C-extension for Python that implements the Aho-Corasick algorithm for multi-pattern string searching. It provides the ahocorasick.Automaton class to build a Trie of patterns and convert it into an automaton for single-pass searching of multiple needles within a haystack. Features include support for different value types (STORE_ANY, STORE_INTS, STORE_LENGTH), key types (KEY_STRING, KEY_SEQUENCE), and various search methods such as iter(), iter_long(), and find_all().
The etc/py directory contains a simpler, pure Python implementation of the Aho-Corasick algorithm. This version is designed for compatibility with both Python 2 and Python 3.
Note: This module has a slightly different API compared to the main C extension and may encounter issues when pickling objects with very long keys.
The Automaton accepts either unicode or bytes depending on how the library was compiled (controlled by the AHOCORASICK_UNICODE preprocessor definition in setup.py).
On Python 3, unicode is the default. You can check the library's configuration using the Automaton.unicode attribute.
Note on memory: When built with unicode support, the automaton stores 2 or 4 bytes per letter (depending on your Python installation). When built for bytes, it only requires one byte per letter.
To use the Aho-Corasick algorithm, you must first call make_automaton() after adding all words.
Search Methods:
iter(string, [start, [end]]): Returns an iterator of (end_index, value) tuples for all matches found in the input string.iter_long(string, [start, [end]]): Returns an iterator for the longest, non-overlapping matches.Continuous Searching with AutomatonSearchIter:
If you are processing a stream of data in chunks, use the iterator returned by iter() and call its .set(new_string, [reset]) method to continue searching without losing state.
Note: make_automaton() finalizes the structure. Once called, the automaton is optimized for searching but is no longer a simple trie.
import ahocorasick
A = ahocorasick.Automaton()
for index, word in enumerate('he her hers she'.split()):
A.add_word(word, (index, word))
# CRITICAL: Must call this before searching
A.make_automaton()
for end_index, value in A.iter('_hershe_'):
print(f'Found {value} at index {end_index}')You can persist an Automaton to disk to avoid rebuilding large indices. There are two ways:
pickle (Convenient)Since Automaton implements __reduce__, it is natively pickle-able.
save() and load() (Memory Efficient)This method is preferred for large automata. If using STORE_ANY, you must provide a serializer/deserializer (like pickle.dumps/loads) to handle the associated Python objects.
Warning: Neither format is inherently safe against malicious data; perform sanity checks on loaded files.
import ahocorasick
import pickle
A = ahocorasick.Automaton()
# ... add words and make_automaton()
# Method A: Pickle
with open('automaton.pkl', 'wb') as f:
pickle.dump(A, f)
with open('automaton.pkl', 'rb') as f:
B = pickle.load(f)
# Method B: Custom save/load (Better for memory)
A.save('automaton.dat', pickle.dumps)
B = ahocorasick.load('automaton.dat', pickle.loads)The ahocorasick.Automaton class can be used as a dict-like Trie to store string keys and associated values. After populating the Trie, you must call make_automaton() to convert it into an Aho-Corasick automaton for efficient multi-pattern searching.
import ahocorasick
# 1. Initialize the Automaton
automaton = ahocorasick.Automaton()
# 2. Add words and associated values (Trie mode)
for idx, key in enumerate('he her hers she'.split()):
automaton.add_word(key, (idx, key))
# 3. Convert to Aho-Corasick automaton
automaton.make_automaton()
# 4. Search for all occurrences in a haystack
haystack = 'he her hers she'
for end_index, (insert_order, original_value) in automaton.iter(haystack):
start_index = end_index - len(original_value) + 1
print((start_index, end_index, (insert_order, original_value)))To install the CPython C-based extension, you need a C compiler installed on your system. You can install it via pip:
pip install pyahocorasickYou can save a large, constructed automaton to disk using pickle and reload it later to avoid the overhead of rebuilding the Trie and the automaton.
import pickle
import ahocorasick
automaton = ahocorasick.Automaton()
automaton.add_word('test', 1)
automaton.make_automaton()
# Serialize
pickled = pickle.dumps(automaton)
# Reload
B = pickle.loads(pickled)
print(B.get('test')) # 1To determine if a specific key is present in the ahocorasick.Automaton trie, you can use either the exists(key) method or the Python in operator. Both approaches return a boolean value: True if the key is present, and False otherwise.
import ahocorasick
A = ahocorasick.Automaton()
A.add_word("cat", 1)
# Using exists()
print(A.exists("cat")) # Output: True
print(A.exists("dog")) # Output: False
# Using the 'in' keyword
print("cat" in A) # Output: True
print("elephant" in A) # Output: FalseAutomaton, call the .iter() method. This returns an instance of AutomatonSearchIter, which is an iterator designed to traverse the matches found within the automaton. You can manipulate the iteration process using the .set() method on the iterator instance.The keys(), values(), and items() methods support wildcard searching. A wildcard character (like ? or .) matches any single character.
Arguments for keys(prefix, [wildcard, [how]]):
prefix: The string to match against.wildcard: The character to treat as a wildcard (e.g., '?').how: Match mode:ahocorasick.MATCH_EXACT_LENGTH: Matches only keys of the exact same length as the prefix.ahocorasick.MATCH_AT_MOST_PREFIX: Matches keys that start with the pattern.ahocorasick.MATCH_AT_LEAST_PREFIX: Matches keys that have the pattern as a prefix.import ahocorasick
A = ahocorasick.Automaton()
for word in 'cat catastropha rat rate bat'.split():
A.add_word(word, word)
# Match 'cat' or 'rat' or 'bat' using wildcard
print(list(A.keys('?at', '?', ahocorasick.MATCH_EXACT_LENGTH)))
# Output: ['bat', 'cat', 'rat']The dump() method returns a three-tuple of lists that provides a complete graph representation of the Aho-Corasick Automaton. This is useful for debugging, visualizing the state machine, or serializing the internal structure.
The method returns a tuple containing three lists:
(node_id, end_of_word_marker). The end_of_word_marker indicates if a node represents the end of a pattern.(node_id, label_char, child_node_id). This defines the transitions between states.(source_node_id, fail_node_id). This defines the failure transitions used when a character match fails.Note that node_id and label_char are represented as unique integers.
# Example of the structure returned by dump()
# nodes: [(node_id, end_of_word_marker), ...]
# edges: [(node_id, label_char, child_node_id), ...]
# failure_links: [(source_node_id, fail_node_id), ...]
nodes, edges, failure_links = automaton.dump()