BK-tree数据结构,允许快速查询“接近”的匹配项
项目描述
pybktree是一个通用的纯Python实现的BK-tree数据结构,它允许快速查询“接近”的匹配项(例如,具有小汉明距离或Levenshtein距离的匹配项)。此模块基于Nick Johnson在他的关于BK树的博客文章中的算法。
此库位于Python包索引(PyPI)上,适用于Python 3和Python 2.7。要安装它,打开命令提示符,如果您正在使用虚拟环境,请激活它,然后输入
pip install pybktree
示例用法
>>> tree = pybktree.BKTree(pybktree.hamming_distance, [0, 4, 5, 14])
>>> tree.add(15) # add element 15
>>> sorted(tree) # BKTree instances are iterable
[0, 4, 5, 14, 15]
>>> sorted(tree.find(13, 1)) # find elements at most 1 bit away from element 13
[(1, 5), (1, 15)]
在调用find()时,对于大型树和相对较小的N,使用BKTree要比进行线性搜索快得多。这在您正在去重几十万张照片时尤其有用——使用线性搜索会变得非常慢,O(N²)操作。使用BKTree,它更像是O(N log N)。
有关更多详细信息,请阅读pybktree.py中的代码——它非常小!
在编写此代码时,我在GitHub上找到的其他BK-tree模块
ahupp/bktree:这个相当不错,但它不在PyPI上,并且它是递归的
ryanfox/bktree:这个很难定制,search() 不返回距离,速度较慢,并且有bug(尽管我认为他最近已经修复了)
pybktree 由 Ben Hoyt 为 Jetsetter 编写,并使用宽松的 MIT 许可证(见 LICENSE.txt)。
项目详情
关闭
pybktree-1.1.tar.gz 的哈希值
算法 | 哈希摘要 | |
---|---|---|
SHA256 | eec0037cdd3d7553e6d72435a4379bede64be17c6712f149e485169638154d2b |
|
MD5 | 9c809214fc979391fdd75dae1942cfb2 |
|
BLAKE2b-256 | 6b38a5fba29cf727ca8249d3840016e1f7919896111aa28d2cb96f013eaa480d |