pybktree 1.1

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）。