Members

kind [readonly]

One of values:

EMPTY

There are no words saved in automaton.

TRIE

There are some words, but methods related to Aho-Corasick algorithm (find_all, iter) won't work.

AHOCORASICK

Aho-Corasick automaton has been constructed, full functionality is available for user.

Kind is maintained internally by Automaton object. Some methods are not available when automaton kind is EMPTY or isn't an AHOCORASICK. When called then exception is raised, however testing this property could be better (faster, more elegant).

store [readonly]

Type of values stored in trie. By default STORE_ANY is used, thus any python object could be used. When STORE_INTS or STORE_LENGTH is used then values are 32-bit integers and do not occupy additional memory. See add_word description for details.

Constructor

Constructor accepts just one argument, a type of values, one of constants:

STORE_ANY

Any Python object (default).

STORE_LENGTH

Length of string.

STORE_INTS

32-bit integers.

Dictionary methods

get(word[, default])

Returns value associated with word. Raises KeyError or returns default value if word isn't present in dictionary.

keys([prefix, [wildchar, [how]]]) => yield strings

Returns iterator that iterate through words.

If prefix (a string) is given, then only words sharing this prefix are yielded.

If wildchar (single character) is given, then prefix is treated as a simple pattern with selected wildchar. Optional parameter how controls which strings are matched:

MATCH_EXACT_LENGTH [default]

Only strings with the same length as a pattern's length are yielded. In other words, literally match a pattern.

MATCH_AT_LEAST_PREFIX

Strings that have length greater or equal to a pattern's length are yielded.

MATCH_AT_MOST_PREFIX

Strings that have length less or equal to a pattern's length are yielded.

See Example 2.

values([prefix, [wildchar, [how]]]) => yield object

Return iterator that iterate through values associated with words. Words are matched as in keys method.

items([prefix, [wildchar, [how]]]) => yield tuple (string, object)

Return iterator that iterate through words and associated values. Words are matched as in keys method.

iter() protocol

Equivalent to obj.keys()

len() protocol

Returns number of distinct words.

Trie

add_word(word, [value]) => bool

Add new word, a key, to dictionary and associate with value. Returns True if word didn't exists earlier in dictionary.

If store == STORE_LENGTH then value is not allowed --- len(word) is saved.

If store == STORE_INTS then value is optional. If present, then have to be an integer, otherwise defaults to len(automaton).

If store == STORE_ANY then value is required and could be any object.

This method invalidates all iterators only if new word was added (i.e. method returned True).

clear() => None

Removes all words from dictionary.

This method invalidates all iterators.

exists(word) => bool or word in ...

Returns if word is present in dictionary.

match(word) => bool

Returns if there is a prefix (or word) equal to word. For example if word "example" is present in dictionary, then all match("e"), match("ex"), ..., match("exampl"), match("example") are True. But exists() is True just for the last word.

longest_prefix(word) => integer

Returns length of the longest prefix of word that exists in a dictionary.

Aho-Corasick

make_automaton()

Creates Aho-Corasick automaton based on trie. This doesn't require additional memory. After successful creation kind become AHOCORASICK.

This method invalidates all iterators.

find_all(string, callback, [start, [end]])

Perform Aho-Corsick on string; start/end can be used to reduce string range. Callback is called with two arguments:

• index of end of matched string
• value associated with that string

(Method called with start/end does similar job as find_all(string[start:end], callback), except index values).

iter(string, [start, [end]])

Returns iterator (object of class AutomatonSearchIter) that does the same thing as find_all, yielding tuples instead of calling a user function.

find_all method could be expressed as:

def find_all(self, string, callback):
        for index, value in self.iter(string):
                callback(index, value)

Other

dump() => (list of nodes, list of edges, list of fail links)

Returns 3 lists describing a graph:

• nodes: each item is a pair (node id, end of word marker)
• edges: each item is a triple (node id, label char, child node id)
• fail: each item is a pair (source node id, node if connected by fail node)

ID is a unique number and a label is a single byte.

Module package contains also program dump2dot.py that shows how to convert dump results to input file for graphviz tools.

get_stats() => dict

Returns dictionary containing some statistics about underlaying trie:

• nodes_count — total number of nodes
• words_count — same as len(automaton)
• longest_word — length of the longest word
• links_count — number of edges
• sizeof_node — size of single node in bytes
• total_size — total size of trie in bytes (about nodes_count * size_of node + links_count * size of pointer). The real size occupied by structure could be larger, because of internal memory fragmentation occurred in memory manager.