Since I didn't made the control versioning system available to
everyone yet, here's the patch which fixes the bug

moman-57f5dc9dd0e7.diff 4K Download

all of our tests pass (n=1,2,3), thanks so much for the quick fix!

On Tue, Mar 2, 2010 at 4:30 PM, Jean-Philippe Barette-LaPierre <

On Mar 2, 2010 5:04pm, Robert Muir <rcm...@gmail.com> wrote:

for each n, i try to test strings to exercise every char vector... i *think*
the tests do that, but I'm not sure.

i do this by using a small language of {0,1}, with integer bits, and
converting to a string, this is how i got the "1001" versus "111".

for each of these strings, i build a DFA with the algorithm, and then try to
confirm the DFA is correct based on the below methods.

for n=1 this is trivial, as i can build a "naive" DFA, and then ensure the
naive DFA accepts the same language as the schulz&mihov DFA.

for n>1, its not so elegant. instead i create all strings in my small {0,1}
language that are no longer than the input word's length + n + 1, and
brute-force compare the results of each possible string with the real
levenshtein algorithm.

i also have some additional sanity checks that aren't very important.
attached is the java file with the junit tests.

if you have an idea for better tests, I'd be interested, as I just started
developing these.

TestLevenshteinAutomata.java 11K Download