Property

state [read-only integer]

Following values are possible:

• pydawg.EMPTY — no words in a set;
• pydawg.ACTIVE — there is at least one word in a set, and adding new words is possible (see add_word & add_word_unchecked);
• pydawg.CLOSED — there is at least one word in a set, but adding new words is not allowed (see close/freeze).

Basic mathods

add_word(word) => bool

Add word, returns True if word didn't exists in a set. Procedure checks if word is greater then previously added word (in lexicography order).

add_word_unchecked(word) => bool

Does the same thing as add_word but do not check word order. Method should be used if one is sure, that input data satisfy algorithm requirements, i.e. words order is valid.

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

Check if word is in set.

match(word) => bool

Check if word or any of its prefix is in a set.

longest_prefix(word) => int

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

len() protocol

Returns number of distinct words.

words() => list

Returns list of all words.

find_all([word, [wildchar, [how]]]) => iterator

Returns iterator that match words depending on word argument.

find_all()

does the same job as iter()

find_all(prefix)

Yields words that share a prefix

find_all(pattern, wildchar, [how])

Yields words that match a pattern with given wildchar (wildchar matches any char). Parameter how controls which words are matched:

MATCH_EXACT_LENGTH

words with the same length as a pattern

MATCH_AT_LEAST_PREFIX

words of length not less then pattern

MATCH_AT_MOST_PREFIX

words of length no greater then pattern

clear()

Erase all words from set.

close() or freeze()

Don't allow to add any new words, state value become pydawg.CLOSED. Also free memory occupied by a hash table used to perform incremental algorithm (see also get_hash_stats()).

Can be reverted only by clear().

Iterator

Class supports iter protocol, i.e. iter(DAWGobject) returns iterator, a lazy version of words() method.

Minimal perfect hashing

Minimal perfect hashing (MPH) allows to find unique number representing any word from DAWG, and also find word with given number. Numbers are in always in range 1 ... len(DAWG).

Finally, this feature makes possible to perform fast lookups as in a regular dictionary.

Algorithm used for MPH is described in Applications of Finite Automata Representing Large Vocabularies, Claudio Lucchiesi and Tomasz Kowaltowski, Software Practice and Experience, 23(1), pp. 15--30, Jan. 1993.

MPH feature is enabled during compilation time if preprocessor definition DAWG_PERFECT_HASHING exists. Module member perfect_hashing reflects this setting.

word2index(word) => index

Returns index of word, or None if word is not present in a DAWG.

index2word(index) => word

Returns words associated with index, or None if index isn't valid.

D = pydawg.DAWG()

# fill DAWG with keys
for key in sorted(dict):
        D.add_word_unchecked(key)

# prepare values array
V = [None] * len(D)

for key, value in dict.items():
        index = D.word2index(key)
        assert index is not None

        V[index - 1] = value


# lookups are possible now
for word in user_input:
        index = D.word2index(word)
        if index is not None:
                print(word, "=>", V[index - 1])

Other

dump() => (set of nodes, set of edges)

Returns sets describing DAWG, elements are tuples.

Node tuple:

• unique id of node (number)
• end of word marker

Edge tuple:

• source node id
• edge label — letter
• destination node id

Distribution contains program dump2dot.py that shows how to convert output of this function to graphviz DOT language.

bindump() => bytes

Returns binary DAWG data.

binload(bytes)

Restore DAWG from binary data. Example:

import pydawg

A = pydawg.DAWG()
with open('dump', 'wb') as f:
        f.write(A.bindump())

B = pydawg.DAWG()
with open('dump', 'rb') as f:
        B.binload(f.read())

get_stats() => dict

Returns dictionary containing some statistics about underlaying data structure:

• words_count — number of distinct words (same as len(dawg))
• longest_word — length of the longest word
• nodes_count — number of nodes
• edges_count — number of edges
• sizeof_node — size of single node (in bytes)
• sizeof_edge — size of single node (in bytes)
• graph_size — size of whole graph (in bytes); it's about nodes_count * sizeof_node + edges_count * sizeof_edge

get_hash_stats() => dict

Returns some statistics about hash table used by DAWG.

• table_size — number of table's elements
• element_size — size of single table item
• items_count — number of items saved in a table
• item_size — size of single item

Approx memory occupied by hash table is table_size * element_size + items_count * item_size.