bk-tree

Burkhard-Keller Trees or bk-trees, a datastructure commonly used for fuzzy string matching, spell checking or similar, comes with a levenshtein distance metric for
measuring similarity.

Further reading for those interested:
* http://en.wikipedia.org/wiki/BK-tree
* http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
* http://en.wikipedia.org/wiki/Edit_distance
* http://en.wikipedia.org/wiki/Levenshtein_distance

Source Repository: https://github.com/profan/lua-bk-tree