haskell

A BK-Tree is a really cool data structure for building a "dictionary" of similar words. It can be used to guess that you meant “cat” when you wrote “cta”. It works by building a tree with words from a dictionary by using the first word as a root node and then attaching subsequent words ...

A BK-Tree is a really cool data structure for building a “dictionary” of similar words. It can be used to guess that you meant “cat” when you wrote “cta”. It works by building a tree with words from a dictionary by using the first word as a root node and then attaching subsequent words with a branch of length d(root_word, new_word) where d is a function for finding the “distance” between two words. This is usually the Levenshtein distance, i.e. the minimum number of edits needed to transform one string into the other.

If the branch is “taken”, i.e. there is already another word connected along a branch of length d(root_word, new_word), the insert operation is done on this word instead. That is the whole algorithm for constructing the BK-tree.

So if we have the following list of words: ["cat", "cut", "hat", "man", "hit"], we will start by creating a “cat” node with no children. To add “cut” we calculate the Levensteinh distance to be one and insert it under the “cat” node.

1) Cut is inserted under cat with a branch of length one

2) The Levensteinh distance between “cat” and “man” is two, so “man” is connected with a branch of length two

3) d(“hat”,“cat”) = 1, so the insertion operation is done on the “cut” node, and “hat” is connected to “cut” with a branch of length two (d(“cut”,“hat”)=2)

4) d(“cat”,“man”) = 2, so the insertion operation is done on the “man” node, and “hit” is connected to “man” with a branch of length three (d(“man”,“hit”)=3)

The lookup algorithm is also quite simple: We find the distance from the query word to the root node and then find all the child nodes in the range [(d-n),(d+n)] where d is the distance and n is the maximum distance we will allow. We then recursively query the nodes that matched. The result is a list of words satisfying d(query_word, word) ≤ n.

The following code is a Haskell implementation of BK-Trees.

It even works! Here are a few examples where I used a dictionary of ~5800 words:

λ> query 1 "thie" bk_tree
["tie","the","this","thief"]
λ> query 1 "catt" bk_tree
["cat","cart"]