Burkhard-Keller (BK) Trees In Python

I recently came across a description of an interesting data structure called a Burkhard-Keller tree (BK tree). BK trees provide efficient lookup of the set of words that lie within a certain distance of a query word. For example, this could used to suggest corrections in a spell checker.

To play around with this I’ve written up a Python implementation of the tree. For example:

>>> tree = BKTree(levenshtein, dictionary_words)
>>> tree.query("ricohet", 2)
[(1, 'ricochet'), (2, 'richer'), (2, 'riches'), 
 (2, 'richest'), (2, 'ricochets')]
>>>

In the above example ‘levenshtein’ is a function that implements the Levenshtein Distance. This is commonly used to determine the distance between a word and its misspellings.

How much faster is a bk-tree than the brute force approach? Here are a few example queries compared with the brute-force time:

You can see the BK tree is much faster for small distances. As the query distance increases the BK tree query time approaches that of the brute force method.

Of course, there’s no free lunch. Creating this tree of 57,024 words takes 94s on my system.

The source for this module is available here. Enjoy!