跳转到主要内容

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 HoytJetsetter 编写,并使用宽松的 MIT 许可证(见 LICENSE.txt)。

项目详情


下载文件

下载适用于您的平台的文件。如果您不确定选择哪个,请了解更多关于 安装包 的信息。

源代码分发

pybktree-1.1.tar.gz (4.5 kB 查看哈希值

上传时间 源代码

由以下支持