Patrix

Patrix provides a RadixTree class (aka trie, compressed prefix tree, or compact prefix tree) that behaves like a python dictionary (abc.MutableMapping subclass) but provides quick and efficient completion suggestions for partial word entries.

This is useful for building autocomplete systems of long lists of known strings that share common prefixes. This is typical for hierarchical naming systems like file paths, IP addresses, or domain names, but it is not limited to those examples.

Usage

Autocomplete System

from patrix import RadixTree

words = [
    "python",
    "programming",
    "program",
    "project",
    "package",
]
autocomplete = RadixTree(words)

Query for possible completions of a partial word. Each result is a Completion: the completed prefix, whether that prefix is a stored word (is_word), and whether the tree continues past it (does_continue). completions returns None when the query matches no entry.

# Example usage
>>> autocomplete.completions()
{Completion(prefix='p', is_word=False, does_continue=True)}
>>> autocomplete.completions("p")
{Completion(prefix='package', is_word=True, does_continue=False), Completion(prefix='pro', is_word=False, does_continue=True), Completion(prefix='python', is_word=True, does_continue=False)}
>>> autocomplete.completions("pro")
{Completion(prefix='program', is_word=True, does_continue=True), Completion(prefix='project', is_word=True, does_continue=False)}
>>> autocomplete.completions("program")
{Completion(prefix='program', is_word=True, does_continue=False), Completion(prefix='programming', is_word=True, does_continue=False)}
>>> autocomplete.completions("programming")
{Completion(prefix='programming', is_word=True, does_continue=False)}
>>> autocomplete.completions("a") is None
True

Save and load a tree

>>> from patrix import RadixTree
>>> # Entries can be a list of strings or key-value tuples
>>> r = RadixTree(("computer", "compute", ("computing", 1)))
>>> # Save to disk as JSON
>>> r.asdict()
{'comput': {'e': {'': {}, 'r': {}}, 'ing': {"__value__": 1}}}
>>> # Load using from_dict
>>> s = RadixTree.from_dict({'comput': {'e': {'': {}, 'r': {}}, 'ing': {"__value__": 1}}})
>>> s.asdict()
{'comput': {'e': {'': {}, 'r': {}}, 'ing': {"__value__": 1}}}

Compression rate for this tree:

>>> r.total_chars
11
>>> len("computer" + "computing" + "compute")
24
>>> 1 - 11 / 24  # 54% compression rate
0.5416666666666667
>>> r.size  # nodes in the tree
6

Use it like a regular dictionary

RadixTree behaves like a regular python dictionary, but the insertion order is not preserved.

>>> r = RadixTree()
>>> r["computer"] = 1
>>> r["compute"] = 2
>>> "computer" in r
True
>>> r["computer"]
1
>>> r.pop("compute")
2
>>> "compute" in r
False
>>> s = r | {"computing": 3}
>>> "computing" in s
True
>>> "computing" in r
False
>>> del s["computing"]
>>> r == s
True