patrix 0.2.1

A python package that uses a compressed prefix tree (radix tree) to store a dictionary of known words and suggests completions for partial entries.

Patrix

Patrix provides a radix tree class (aka trie, compressed prefix tree, or compact prefix tree) that behaves mostly like a python dictionary 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.

Radix tree example

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

Display suggestions on how to continue a given query prefix

>>> r.completions("c")
{'comput'}
>>> r.completions("comput")
{'compute', 'computing'}
>>> r.completions("compute") # The word 'compute' here is both a stem and a final word
{'compute', 'computer'}
>>> r.completions("p")
set()

RadixTree behaves like a python dictionary:

>>> r["computer"] = 1
>>> r["compute"] = 2
>>> r["computing"] = 3
>>> r.pop("compute")
2
>>> "computing" in r
True
>>> r["computing"]
3

Compression rate

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