[darklajid]

I'm not sure if I can follow - I'll give it some more thought and time. That said: You're doing something completely different as far I can tell. You build an ~automaton~ based on an input word. That's not what the paper does/what I struggled with. The paper describes a general automaton and creating a 'vector' based on the input word, that you use as steps.

At the moment I don't see how you could handle transpositions either.

I'm not saying that your approach is bad. But I do think that the 'I did it in an hour' comment was a quite a bit misleading, if you basically ignored the paper and did something that is different in most ways.

The tradeoffs are immensely different - the whole point of the paper is that you're precomputing a looot of stuff so that the lookup is fast.

[jules]

Computing the step() is extremely fast. And if that's not fast enough then do the DFA construction as I described. The approach is different, yes, but that's the point.

[lorenzhs]

I commented on your step function in another comment so I'm going to skip that.

Your DFA construction, while a bit incomplete (you don't say how you do the transitions), achieves roughly the same thing as Levenshtein automata do. But you spend significantly more time to construct it. The point of the original paper was not to show that DFAs can be used to compute Levenshtein distance, but to show how to do it quickly and efficiently.

[jules]

I replied to this in the other thread to avoid splitting the conversation in two.