7 ms·

I.. have a hard time believing this. Unless you're talking about a very simplified case (N=1 or something, maybe even for a specific word)? On the other hand:

I.. have a hard time believing this. Unless you're talking about a very simplified case (N=1 or something, maybe even for a specific word)? On the other hand: Maybe the Lucene guys and me are just bad. :/

jules 11y ago
It was for the general case. The reason that I was able to do this is because I was less persistent than them. I tried to understand the paper but after 5 minutes I realized that even understanding the paper was going to take WAY more time than ignoring the paper and implementing it my own way. Here's how I did it. If we are looking for string = "banana" Then we can represent the state of the automaton as the last row of the matrix that you get when you compute the Levenshtein distance between two fixed strings. The initial state is (in Python): def init(): return range(len(string)+1) Then to take a step in the automaton: def step(state, char): newstate = [0 for x in state] newstate[0] = state[0]+1 for i in range(len(state)-1): if i < len(string) and string[i] == char: newstate[i+1] = state[i] else: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1]) return newstate We step like this: s0 = init() s1 = step(s0, 'c') s2 = step(s1, 'a') s3 = step(s2, 'b') s4 = step(s3, 'a') s5 = step(s4, 'n') s6 = step(s5, 'a') Now we can compute the lowerbound of the Levenshtein distance by doing min(s6). In this case it's 2. This means that whatever comes after "cabana", it will always have at least distance 2 to "banana". With this info we can prune away a search path in the full text index if that value is larger than our maximum edit distance. Those handful of lines of code is all you need to do fuzzy string search in practice. This represents the automaton as a step procedure. If you want you can also generate a DFA from this (though it's probably not necessary in practice). If your maximum edit distance is n then if one of the numbers in the state is greater than n it doesn't matter what it is. In the above example s6 = [6, 5, 4, 3, 2, 3, 2]. If n = 3 then s6 = [4, 4, 4, 3, 2, 3, 2] is equivalent, because in the end it only matters whether a number is >3 or not. So you might as well keep the numbers on 4. Replace: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1]) with: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1],n+1) where n is the maximum edit distance. Now the state space of the automaton is finite, and you can generate a DFA from it by just exploring all the states with the step() function. One more optimization is to not generate the DFA for the full alphabet. If your search word is "banana" then for the purposes of the automaton the letter 'x' is equivalent to the letter 'y' because both are not equal to any letter in "banana". So instead of creating a DFA for the full ASCII alphabet (or worse, the full unicode alphabet), you can instead work with the reduced 4 letter alphabet (b,a,n,X). X represents any letter other than b,a,n. You could also do a hybrid where you generate the DFA lazily. I don't know if that made sense, it's a bit difficult to explain in a short HN comment.
- lorenzhs 11y ago
  You implemented an automaton that computes Levenshtein distances. However, Levenshtein automata are quite different from what you describe. Your automaton executes the basic Wagner-Fischer / Needleman-Wunsch / ... algorithm. Btw, see also https://news.ycombinator.com/item?id=9698785 https://news.ycombinator.com/item?id=9698785 for another discussion on basically the same problem.
  - jules 11y ago
    This is not correct. The end result of the step() based automaton is the same: it prunes exactly the same search paths as any Levenshtein automaton would. And the part where I described how to build the DFA gives you exactly a Levenshtein automaton DFA. The approach is different, yes, that's the point: it's much simpler and still does the job.
    - lorenzhs 11y ago
      It's not nearly as efficient though, your step function requires O(len(string)) time no matter how well you prune. Since you have len(query) many steps, that gets you to O(len(string)*len(query)), aka quadratic time if they're roughly the same length. Levenshtein automata can do this in linear time because they spend time building the automaton first (preprocessing). So yes, you implemented an algorithm using automata that computes the same result. But you didn't implement Levenshtein automata.
      - jules 11y ago
        In practice with Lucene, len(string) and len(query) are like 10. So it's totally irrelevant. Furthermore computing the step is extremely fast: you're just doing a handful of min()'s. Even a single cache miss is going to completely dominate that, let alone a disk seek. What matters is that you don't scan a 10 million word index, instead you want to prune your search to hit, say, 50 words in the index. That's just the step() approach. After that I described how to build the DFA, which gets you the same optimal linear time that you want which does not depend on the query string size. Reply to other comment: > 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. Why is it incomplete? You just follow the step() automaton and construct a DFA that does the same. Every time you hit a new state you create a new node in the DFA, and if you hit an old state you just point to a previously constructed DFA node. You can even do the DFA construction lazily. > But you didn't implement Levenshtein automata. A Levenshtein automaton for a word W is a finite state automaton that accepts all words V within edit distance n from W. That's exactly what I built. The point here is that you turn a 30 second search over the whole index into a 0.02 second search by pruning. If you can then optimize that to 0.015 by making the automaton more efficient that's nice but you can hardly claim that what I did is not a Levenshtein automaton because it's a bit slower (and it's not even clear to me that it would be slower).

jules 11y ago

It was for the general case. The reason that I was able to do this is because I was less persistent than them. I tried to understand the paper but after 5 minutes I realized that even understanding the paper was going to take WAY more time than ignoring the paper and implementing it my own way. Here's how I did it. If we are looking for string = "banana" Then we can represent the state of the automaton as the last row of the matrix that you get when you compute the Levenshtein distance between two fixed strings. The initial state is (in Python): def init(): return range(len(string)+1) Then to take a step in the automaton: def step(state, char): newstate = [0 for x in state] newstate[0] = state[0]+1 for i in range(len(state)-1): if i < len(string) and string[i] == char: newstate[i+1] = state[i] else: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1]) return newstate We step like this: s0 = init() s1 = step(s0, 'c') s2 = step(s1, 'a') s3 = step(s2, 'b') s4 = step(s3, 'a') s5 = step(s4, 'n') s6 = step(s5, 'a') Now we can compute the lowerbound of the Levenshtein distance by doing min(s6). In this case it's 2. This means that whatever comes after "cabana", it will always have at least distance 2 to "banana". With this info we can prune away a search path in the full text index if that value is larger than our maximum edit distance. Those handful of lines of code is all you need to do fuzzy string search in practice. This represents the automaton as a step procedure. If you want you can also generate a DFA from this (though it's probably not necessary in practice). If your maximum edit distance is n then if one of the numbers in the state is greater than n it doesn't matter what it is. In the above example s6 = [6, 5, 4, 3, 2, 3, 2]. If n = 3 then s6 = [4, 4, 4, 3, 2, 3, 2] is equivalent, because in the end it only matters whether a number is >3 or not. So you might as well keep the numbers on 4. Replace: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1]) with: newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1],n+1) where n is the maximum edit distance. Now the state space of the automaton is finite, and you can generate a DFA from it by just exploring all the states with the step() function. One more optimization is to not generate the DFA for the full alphabet. If your search word is "banana" then for the purposes of the automaton the letter 'x' is equivalent to the letter 'y' because both are not equal to any letter in "banana". So instead of creating a DFA for the full ASCII alphabet (or worse, the full unicode alphabet), you can instead work with the reduced 4 letter alphabet (b,a,n,X). X represents any letter other than b,a,n. You could also do a hybrid where you generate the DFA lazily. I don't know if that made sense, it's a bit difficult to explain in a short HN comment.

lorenzhs 11y ago
You implemented an automaton that computes Levenshtein distances. However, Levenshtein automata are quite different from what you describe. Your automaton executes the basic Wagner-Fischer / Needleman-Wunsch / ... algorithm. Btw, see also https://news.ycombinator.com/item?id=9698785 https://news.ycombinator.com/item?id=9698785 for another discussion on basically the same problem.
- jules 11y ago
  This is not correct. The end result of the step() based automaton is the same: it prunes exactly the same search paths as any Levenshtein automaton would. And the part where I described how to build the DFA gives you exactly a Levenshtein automaton DFA. The approach is different, yes, that's the point: it's much simpler and still does the job.
  - lorenzhs 11y ago
    It's not nearly as efficient though, your step function requires O(len(string)) time no matter how well you prune. Since you have len(query) many steps, that gets you to O(len(string)*len(query)), aka quadratic time if they're roughly the same length. Levenshtein automata can do this in linear time because they spend time building the automaton first (preprocessing). So yes, you implemented an algorithm using automata that computes the same result. But you didn't implement Levenshtein automata.
    - jules 11y ago
      In practice with Lucene, len(string) and len(query) are like 10. So it's totally irrelevant. Furthermore computing the step is extremely fast: you're just doing a handful of min()'s. Even a single cache miss is going to completely dominate that, let alone a disk seek. What matters is that you don't scan a 10 million word index, instead you want to prune your search to hit, say, 50 words in the index. That's just the step() approach. After that I described how to build the DFA, which gets you the same optimal linear time that you want which does not depend on the query string size. Reply to other comment: > 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. Why is it incomplete? You just follow the step() automaton and construct a DFA that does the same. Every time you hit a new state you create a new node in the DFA, and if you hit an old state you just point to a previously constructed DFA node. You can even do the DFA construction lazily. > But you didn't implement Levenshtein automata. A Levenshtein automaton for a word W is a finite state automaton that accepts all words V within edit distance n from W. That's exactly what I built. The point here is that you turn a 30 second search over the whole index into a 0.02 second search by pruning. If you can then optimize that to 0.015 by making the automaton more efficient that's nice but you can hardly claim that what I did is not a Levenshtein automaton because it's a bit slower (and it's not even clear to me that it would be slower).