3 ms·

Not to bring up our previous discussion again, but your complexity analysis is still misleading. Your "O(length of string) version" takes O(length of string) pe

Not to bring up our previous discussion again, but your complexity analysis is still misleading. Your "O(length of string) version" takes O(length of string) per step, not for the total time. To match an entire word (which you have to do to ensure that you have a match), you have to call step O(length of word) many times, so you're back to quadratic complexity. Also, it would have been nice if you had done your analysis with k as a variable instead of saying linear when you actually mean "O(nk) for a very small k". Furthermore, if you have a maximum edit distance k, you can also implement the dynamic programming approach for a pair of strings in O(nk) time [1]. Still, your description prunes the trie nicely. It's a nice and simple method that's a lot faster than the naive implementation and good enough for nearly all applications. Have you done any benchmarking by any chance? [1] A quite fast C++ implementation I wrote is at https://github.com/xhochy/libfuzzymatch/blob/master/src/libfuzzymatch/levenshteinLimit.cpp https://github.com/xhochy/libfuzzymatch/blob/master/src/libf... - the repo will at some point in the future also contain other, faster methods for calculating Levenshtein distance.

jules 11y ago
Yes, the O(length of string) is per step in the automaton. Sorry if that was unclear, it was not my intention to mislead. Note however that that is for the naive version. The only point of the naive version is as a pedagogical stepping stone to the second version. I put the section on building the DFA after the naive version because it provides a nice logical progression: when you try to build a DFA you want the number of states to be finite, which leads to the idea that you set all entries >k to k+1. Then that leads to the idea of the sparse vector. If you were actually building a DFA though, you would use the fast automaton to generate the transitions rather than the naive one. I tried to stay close to the terminology of the paper. They assume that k is fixed. The complexity of 1 step in the non naive automaton is O(k) where k is the max edit distance (1 or 2 in Lucene). Building the DFA is O(nk) where n is the number of states in the DFA. Note however that while the number of states in the DFA is linear in the size of the string, it's actually exponential in k. This is unavoidable, a Levenshtein DFA simply needs an exponential number of states as a function of k. So if k is large it's not a good idea to build the DFA, it's better to use the step() based automaton directly. In fact I'm pretty sure it's better to do that in any case, because it's unlikely that the initial cost of building the DFA will pay off. If k=2 then you're basically updating an array of 5 numbers at every step. Stepping in a DFA isn't going to be much faster than that. You would need a huge number of steps before it starts to pay off, and the whole point of a Levenshtein automaton is that you search only about 200 positions in the index. > Furthermore, if you have a maximum edit distance k, you can also implement the dynamic programming approach for a pair of strings in O(nk) time I think you can even do that without knowing the maximum distance beforehand. Maintain a priority queue of entries in the matrix, and repeatedly propagate the minimum. That way you avoid computing most of the matrix if the edit distance turns out to be small. If insert/delete/substitute costs are all 1 you don't even need a full priority queue.
adamtj 11y ago
> O(length of string) per step The big win here is not that it's as fast as the optimal algorithm (it's not), but that it's nearly as fast and vastly simpler. You're technically right that the given code is O(n^2), but the optimization discussed later in the article can easily be applied to turn that into O(nk). Further, for the lucene problem, k=2. That's small and effectively constant, making it "basically O(n)". That's still theoretically worse that optimal, but in practice it just doesn't matter. Even with the slightly slower algorithm, Lucene's cost of searching should be dominated by repeatedly _using_ the DFA and not by _building_ it. What's really important is that the O(nk) construction algorithm is much simpler than the optimal version. I don't know what the Lucene guys were originally trying to do, but if they had figured out this method instead, they could have avoided the super complicated implementation of the true O(n) algorithm. > you can also implement the dynamic programming approach for a pair of strings in O(nk) time Yes, but that's for every pair of strings you want to test. A DFA costs exactly as much to build as solving a single problem with DP, but when a large number of pairs all have one string in common (the query string), a pre-built DFA can be used repeatedly in only O(n+k) each time. Of course, whether that's enough to make a practical difference depends on the problem at hand.

jules 11y ago

Yes, the O(length of string) is per step in the automaton. Sorry if that was unclear, it was not my intention to mislead. Note however that that is for the naive version. The only point of the naive version is as a pedagogical stepping stone to the second version. I put the section on building the DFA after the naive version because it provides a nice logical progression: when you try to build a DFA you want the number of states to be finite, which leads to the idea that you set all entries >k to k+1. Then that leads to the idea of the sparse vector. If you were actually building a DFA though, you would use the fast automaton to generate the transitions rather than the naive one. I tried to stay close to the terminology of the paper. They assume that k is fixed. The complexity of 1 step in the non naive automaton is O(k) where k is the max edit distance (1 or 2 in Lucene). Building the DFA is O(nk) where n is the number of states in the DFA. Note however that while the number of states in the DFA is linear in the size of the string, it's actually exponential in k. This is unavoidable, a Levenshtein DFA simply needs an exponential number of states as a function of k. So if k is large it's not a good idea to build the DFA, it's better to use the step() based automaton directly. In fact I'm pretty sure it's better to do that in any case, because it's unlikely that the initial cost of building the DFA will pay off. If k=2 then you're basically updating an array of 5 numbers at every step. Stepping in a DFA isn't going to be much faster than that. You would need a huge number of steps before it starts to pay off, and the whole point of a Levenshtein automaton is that you search only about 200 positions in the index. > Furthermore, if you have a maximum edit distance k, you can also implement the dynamic programming approach for a pair of strings in O(nk) time I think you can even do that without knowing the maximum distance beforehand. Maintain a priority queue of entries in the matrix, and repeatedly propagate the minimum. That way you avoid computing most of the matrix if the edit distance turns out to be small. If insert/delete/substitute costs are all 1 you don't even need a full priority queue.

adamtj 11y ago

> O(length of string) per step The big win here is not that it's as fast as the optimal algorithm (it's not), but that it's nearly as fast and vastly simpler. You're technically right that the given code is O(n^2), but the optimization discussed later in the article can easily be applied to turn that into O(nk). Further, for the lucene problem, k=2. That's small and effectively constant, making it "basically O(n)". That's still theoretically worse that optimal, but in practice it just doesn't matter. Even with the slightly slower algorithm, Lucene's cost of searching should be dominated by repeatedly _using_ the DFA and not by _building_ it. What's really important is that the O(nk) construction algorithm is much simpler than the optimal version. I don't know what the Lucene guys were originally trying to do, but if they had figured out this method instead, they could have avoided the super complicated implementation of the true O(n) algorithm. > you can also implement the dynamic programming approach for a pair of strings in O(nk) time Yes, but that's for every pair of strings you want to test. A DFA costs exactly as much to build as solving a single problem with DP, but when a large number of pairs all have one string in common (the query string), a pre-built DFA can be used repeatedly in only O(n+k) each time. Of course, whether that's enough to make a practical difference depends on the problem at hand.