blob: 41ca83db94823628901a699fa7e0ab057466629c (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
pygtrie
=======
.. image:: https://readthedocs.org/projects/pygtrie/badge/?version=latest
:target: http://pygtrie.readthedocs.io/en/latest/
:alt: Documentation build status (latest)
.. image:: https://readthedocs.org/projects/pygtrie/badge/?version=stable
:target: http://pygtrie.readthedocs.io/en/stable/
:alt: Documentation build status (stable)
.. image:: https://api.travis-ci.com/mina86/pygtrie.svg
:target: https://travis-ci.com/mina86/pygtrie
:alt: Continuous integration status
pygtrie is a pure Python implementation of a trie data structure
compatible with Python 2.x and Python 3.x.
`Trie data structure <http://en.wikipedia.org/wiki/Trie>`_, also known
as radix or prefix tree, is a tree associating keys to values where
all the descendants of a node have a common prefix (associated with
that node).
The trie module contains ``Trie``, ``CharTrie`` and ``StringTrie``
classes each implementing a mutable mapping interface, i.e. ``dict``
interface. As such, in most circumstances, ``Trie`` could be used as
a drop-in replacement for a ``dict``, but the prefix nature of the
data structure is trie’s real strength.
The module also contains ``PrefixSet`` class which uses a trie to
store a set of prefixes such that a key is contained in the set if it
or its prefix is stored in the set.
Features
--------
- A full mutable mapping implementation.
- Supports iterating over as well as deleting a subtrie.
- Supports prefix checking as well as shortest and longest prefix
look-up.
- Extensible for any kind of user-defined keys.
- A PrefixSet supports “all keys starting with given prefix” logic.
- Can store any value including None.
Installation
------------
To install pygtrie, simply run::
pip install pygtrie
or by adding line such as::
pygtrie == 2.*
to project’s `requirements file
<https://pip.pypa.io/en/latest/user_guide/#requirements-files>`_.
Alternatively, if installation from source is desired, it can be
achieved by executing::
python setup.py install
|
