BKTrees.jl

Julia implementation of BKTrees based on the Python implementation found here.

Introduction

For more information on BK-trees check out https://en.wikipedia.org/wiki/BK-tree and https://github.com/Jetsetter/pybktree.

Documentation

This short example illustrates the usage of the B-K trees for approximate string matching:

julia> using Pkg
       Pkg.activate(".")
       using BKTrees
       using Random
       using StringDistances
       
       lev(x,y) = evaluate(Levenshtein(), x, y)
       dictionary = [randstring(10) for _ in 1:100_000]  # random dictionary
       bkt = BKTree(lev, dictionary)  # build tree
       
       target = randstring(10)  # target string
       
       # search for best 3 matches with distance < 10
       found = find(bkt, target, 10, k=3)
       @show target, found

#(target, found) = ("RIqWKU2A38", Tuple{Float64,String}[(7.0, "uIfPK02wH9"), (7.0, "RIqTF8YC6O"), (7.0, "XMqWKG1GHN")])

Installation

The installation can be done through the usual channels (manually by cloning the repository or installing it though the julia REPL).

License

This code has an MIT license and therefore it is free.

Acknowledgments

This work is heavily based on the implementation found here