Implementing a simple Trie for efficient Levenshtein Distance calculation - Java

I've implemented the algo described on "Fast and Easy Levenshtein distance using a Trie" article in C++ and it is really fast. If you want (understand C++ better than Python), I can past the code in somewhere.

Edit: I posted it on my blog.

Here is an example of Levenshtein Automata in Java (EDIT: moved to github).These will probably also be helpful:

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/test/org/apache/lucene/util/automaton/

EDIT: The above links seem to have moved to github:

https://github.com/apache/lucene-solr/tree/master/lucene/core/src/java/org/apache/lucene/util/automaton https://github.com/apache/lucene-solr/tree/master/lucene/core/src/test/org/apache/lucene/util/automaton

It looks like the experimental Lucene code is based off of the dk.brics.automaton package.

Usage appears to be something similar to below:

LevenshteinAutomata builder = new LevenshteinAutomata(s);
Automaton automata = builder.toAutomaton(n);
boolean result1 = BasicOperations.run(automata, "foo");
boolean result2 = BasicOperations.run(automata, "bar");

From what I can tell you don't need to improve the efficiency of Levenshtein Distance, you need to store your strings in a structure that stops you needing to run distance computations so many times i.e by pruning the search space.

Since Levenshtein distance is a metric, you can use any of the metric spaces indices which take advantage of triangle inequality - you mentioned BK-Trees, but there are others eg. Vantage Point Trees, Fixed-Queries Trees, Bisector Trees, Spatial Approximation Trees. Here are their descriptions:

Burkhard-Keller Tree

Nodes are inserted into the tree as follows: For the root node pick an arbitary element from the space; add unique edge-labeled children such that the value of each edge is the distance from the pivot to that element; apply recursively, selecting the child as the pivot when an edge already exists.

Fixed-Queries Tree

As with BKTs except: Elements are stored at leaves; Each leaf has multiple elements; For each level of the tree the same pivot is used.

Bisector Tree

Each node contains two pivot elements with their covering radius (maximum distance between the centre element and any of its subtree elements); Filter into two sets those elements which are closest to the first pivot and those closest to the second, and recursively build two subtrees from these sets.

Spatial Approximation Tree

Initially all elements are in a bag; Choose an arbitrary element to be the pivot; Build a collection of nearest neighbours within range of the pivot; Put each remaining element into the bag of the nearest element to it from collection just built; Recursively form a subtree from each element of this collection.

Vantage Point Tree

Choose a pivot from the set abitrarily; Calculate the median distance between this pivot and each element of the remaining set; Filter elements from the set into left and right recursive subtrees such that those with distances less than or equal to the median form the left and those greater form the right.