datrie 0.8.2

datrie

超级快速、高效存储的 Python Trie (2.x 和 3.x)。使用 libdatrie。

安装

pip install datrie

用法

创建一个能够存储具有小写 ascii 键的项的新 trie

>>> import string
>>> import datrie
>>> trie = datrie.Trie(string.ascii_lowercase)

trie 变量是一个类似于字典的对象，它可以具有特定范围内的 Unicode 键和 Python 对象作为值。

除了实现映射接口之外，tries还简化了查找给定前缀的项，反之亦然，查找键为给定字符串前缀的项。作为常见的特殊情况，也支持查找最长的前缀项。

向其中添加一些值（datrie的键必须是unicode；以下示例针对Python 2.x）

>>> trie[u'foo'] = 5
>>> trie[u'foobar'] = 10
>>> trie[u'bar'] = 'bar value'
>>> trie.setdefault(u'foobar', 15)
10

检查u'foo'是否在trie中

>>> u'foo' in trie
True

获取一个值

>>> trie[u'foo']
5

查找一个单词的所有前缀

>>> trie.prefixes(u'foobarbaz')
[u'foo', u'foobar']

>>> trie.prefix_items(u'foobarbaz')
[(u'foo', 5), (u'foobar', 10)]

>>> trie.iter_prefixes(u'foobarbaz')
<generator object ...>

>>> trie.iter_prefix_items(u'foobarbaz')
<generator object ...>

查找一个单词的最长前缀

>>> trie.longest_prefix(u'foo')
u'foo'

>>> trie.longest_prefix(u'foobarbaz')
u'foobar'

>>> trie.longest_prefix(u'gaz')
KeyError: u'gaz'

>>> trie.longest_prefix(u'gaz', default=u'vasia')
u'vasia'

>>> trie.longest_prefix_item(u'foobarbaz')
(u'foobar', 10)

检查trie是否有具有给定前缀的键

>>> trie.has_keys_with_prefix(u'fo')
True

>>> trie.has_keys_with_prefix(u'FO')
False

从trie中获取具有给定前缀的所有项

>>> trie.keys(u'fo')
[u'foo', u'foobar']

>>> trie.items(u'ba')
[(u'bar', 'bar value')]

>>> trie.values(u'foob')
[10]

从trie中获取以给定前缀开始的特定单词的所有后缀

>>> trie.suffixes()
[u'pro', u'producer', u'producers', u'product', u'production', u'productivity', u'prof']
>>> trie.suffixes(u'prod')
[u'ucer', u'ucers', u'uct', u'uction', u'uctivity']

保存和加载一个trie（值必须是可序列化的）

>>> trie.save('my.trie')
>>> trie2 = datrie.Trie.load('my.trie')

Trie和BaseTrie

在datrie包中有两个Trie类： datrie.Trie 和 datrie.BaseTrie。 datrie.BaseTrie略快，内存使用也更少，但它只能存储整数，范围是-2147483648 <= x <= 2147483647。 datrie.Trie稍慢，但可以存储任何Python对象作为值。

如果您不需要值或整数值是可以接受的，则使用datrie.BaseTrie

import datrie
import string
trie = datrie.BaseTrie(string.ascii_lowercase)

自定义迭代

如果内置的trie方法不适合您，则可以使用 datrie.State 和 datrie.Iterator 来实现自定义遍历。

例如，让我们为我们的trie查找所有以'fo'结尾的后缀并获取值

>>> state = datrie.State(trie)
>>> state.walk(u'foo')
>>> it = datrie.Iterator(state)
>>> while it.next():
...     print(it.key())
...     print(it.data))
o
5
obar
10

性能

性能是在与Python字典比较的情况下测量的，其中字典有100k个唯一的unicode单词（英语和俄语）作为键，'1'作为值。

datrie.Trie大约使用5M内存来存储100k个单词；根据我的非科学的测试，Python字典大约使用22M。

这个trie实现比python的dict在__getitem__上的速度慢2-6倍；基准测试结果（macbook air i5 1.8GHz，“1.000M ops/sec” == “1 000 000 operations per second”）

Python 2.6:
dict __getitem__: 7.107M ops/sec
trie __getitem__: 2.478M ops/sec

Python 2.7:
dict __getitem__: 6.550M ops/sec
trie __getitem__: 2.474M ops/sec

Python 3.2:
dict __getitem__: 8.185M ops/sec
trie __getitem__: 2.684M ops/sec

Python 3.3:
dict __getitem__: 7.050M ops/sec
trie __getitem__: 2.755M ops/sec

查找给定单词的前缀几乎和__getitem__一样快（结果针对Python 3.3）

trie.iter_prefix_items (hits):      0.461M ops/sec
trie.prefix_items (hits):           0.743M ops/sec
trie.prefix_items loop (hits):      0.629M ops/sec
trie.iter_prefixes (hits):          0.759M ops/sec
trie.iter_prefixes (misses):        1.538M ops/sec
trie.iter_prefixes (mixed):         1.359M ops/sec
trie.has_keys_with_prefix (hits):   1.896M ops/sec
trie.has_keys_with_prefix (misses): 2.590M ops/sec
trie.longest_prefix (hits):         1.710M ops/sec
trie.longest_prefix (misses):       1.506M ops/sec
trie.longest_prefix (mixed):        1.520M ops/sec
trie.longest_prefix_item (hits):    1.276M ops/sec
trie.longest_prefix_item (misses):  1.292M ops/sec
trie.longest_prefix_item (mixed):   1.379M ops/sec

查找以给定前缀开始的单词主要受总结果计数限制（这可以在未来得到改善，因为大量的时间被花在将utf_32_le字符串解码为Python的unicode上）

trie.items(prefix="xxx"), avg_len(res)==415:        0.609K ops/sec
trie.keys(prefix="xxx"), avg_len(res)==415:         0.642K ops/sec
trie.values(prefix="xxx"), avg_len(res)==415:       4.974K ops/sec
trie.items(prefix="xxxxx"), avg_len(res)==17:       14.781K ops/sec
trie.keys(prefix="xxxxx"), avg_len(res)==17:        15.766K ops/sec
trie.values(prefix="xxxxx"), avg_len(res)==17:      96.456K ops/sec
trie.items(prefix="xxxxxxxx"), avg_len(res)==3:     75.165K ops/sec
trie.keys(prefix="xxxxxxxx"), avg_len(res)==3:      77.225K ops/sec
trie.values(prefix="xxxxxxxx"), avg_len(res)==3:    320.755K ops/sec
trie.items(prefix="xxxxx..xx"), avg_len(res)==1.4:  173.591K ops/sec
trie.keys(prefix="xxxxx..xx"), avg_len(res)==1.4:   180.678K ops/sec
trie.values(prefix="xxxxx..xx"), avg_len(res)==1.4: 503.392K ops/sec
trie.items(prefix="xxx"), NON_EXISTING:             2023.647K ops/sec
trie.keys(prefix="xxx"), NON_EXISTING:              1976.928K ops/sec
trie.values(prefix="xxx"), NON_EXISTING:            2060.372K ops/sec

与dict相比，随机插入时间非常慢，这是双数组tries的限制；更新相当快。如果您想构建一个trie，请考虑在插入之前对键进行排序

dict __setitem__ (updates):            6.497M ops/sec
trie __setitem__ (updates):            2.633M ops/sec
dict __setitem__ (inserts, random):    5.808M ops/sec
trie __setitem__ (inserts, random):    0.053M ops/sec
dict __setitem__ (inserts, sorted):    5.749M ops/sec
trie __setitem__ (inserts, sorted):    0.624M ops/sec
dict setdefault (updates):             3.455M ops/sec
trie setdefault (updates):             1.910M ops/sec
dict setdefault (inserts):             3.466M ops/sec
trie setdefault (inserts):             0.053M ops/sec

其他结果（注意，len(trie)当前是通过trie遍历实现的）

dict __contains__ (hits):    6.801M ops/sec
trie __contains__ (hits):    2.816M ops/sec
dict __contains__ (misses):  5.470M ops/sec
trie __contains__ (misses):  4.224M ops/sec
dict __len__:                334336.269 ops/sec
trie __len__:                22.900 ops/sec
dict values():               406.507 ops/sec
trie values():               20.864 ops/sec
dict keys():                 189.298 ops/sec
trie keys():                 2.773 ops/sec
dict items():                48.734 ops/sec
trie items():                2.611 ops/sec

请将这些基准测试结果视为仅供参考；这是一个非常简单的基准测试，可能无法覆盖您的用例。

当前限制

• 键必须是unicode（Python 2.x下，字节字符串没有隐式转换，抱歉）；

• 没有键/值/项的迭代器版本（这尚未实现）；

• 在pypy下，它非常慢，可能还有bug；

• 库未针对窄Python构建进行测试。

贡献

开发发生在github上：https://github.com/pytries/datrie。

请随时提交想法、错误报告和pull请求。

$ tox

$ tox -c tox-bench.ini

$ update_c.sh

许可

根据LGPL v2.1授权。CHANGES =======