Burkard Keller Trees

I was reading through the blog “Damn Cool Algorithms, Part 1: BK-Trees” by Nick Johnson and I was intrigued about burkard keller tree structure.

BK-Trees, or Burkhard-Keller Trees are a tree-based data structure engineered for quickly finding near-matches to a string, for example, as used by a spelling checker, or when doing a ‘fuzzy’ search for a term. The aim is to return, for example, “seek” and “peek” if I search for “aeek”.

It allows you to quickly search a tree of words (or other Objects) to find matches within a specified amount of “closeness”. It is a much more efficient way of searching a dictionary of related words used in a spell checker or search term suggester application. I decided to implement the algorithm myself in Java and posted the result to google code:

https://github.com/joshclemm/java-bk-tree/