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. :/
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. :/
If we are looking for
string = "banana"
def init():
return range(len(string)+1)
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
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')
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])
newstate[i+1] = 1 + min(newstate[i],state[i],state[i+1],n+1)
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.
Btw, see also https://news.ycombinator.com/item?id=9698785 for another discussion on basically the same problem.
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).
An L1 cache miss, L2 hit costs around 10 cycles, and the L2 cache is more than sufficiently large. Even your initialisation loop takes more than that. The min loop has 11 instructions (branchless) per iteration for the minimum calculations in C++: https://goo.gl/wjhRtb - not taking into account superscalarity.
You have not shown how you prune the search, so I can't say anything about that. Of course that's the entire point of having an index.
Your DFA construction again is massively slower than what is done in the paper. The authors show how to construct the entire automaton in time O(|string|), whereas each step in your implementation takes that much time.
Whether or not you built Levenshtein automata is a pointless discussion. You say you built a DFA for Levenshtein distance (true). I'm saying that you didn't implement the paper. Both are correct.
Look, I'm not claiming you did anything wrong. I'm just pointing out that your implementation, while it was fast to write, is also much much slower than their algorithm, and you shouldn't compare the two as if they were the same.
It's not O(n^2), but I forgot to mention that. You don't need to calculate the full state, only k entries when your maximum edit distance is k, because the other entries are going to be greater than k anyway. So it's actually O(nk), so it's linear in n (that paper assumes that the max edit distance and the alphabet size are fixed, so by their assumption O(nk) = O(n)). But I think you are missing what a Levenshtein automaton is. The point of a Levenshtein automaton is not to calculate the edit distance. In fact a Levenshtein automaton does not need to calculate the edit distance at all. What a Levenshtein automaton with max distance k to a word "banana" does is this: it determines whether given a prefix like "caba", is there a way to extend that prefix such that the distance to "banana" is less than k. The dynamic programming algorithm does not do this. They are two different (but of course related) problems.
> In fact, even for that it's a relatively bad implementation because it constructs a new list in every step, whereas you could just reuse the same two lists (called score in your implementation) all the time.
Of course, it's a proof of concept not a fast implementation. Plus it's not as simple as keeping two lists when you're searching a text index, because from the same state you will need to calculate multiple successor states. If you destroy the state s when stepping you can't step from that same state s with another letter.
> An L1 cache miss, L2 hit costs around 10 cycles, and the L2 cache is more than sufficiently large
A normal full text index does not even fit in L3. Perhaps it does not even fit in memory.
> You have not shown how you prune the search, so I can't say anything about that. Of course that's the entire point of having an index.
Pruning the search works exactly the same way given any implementation of a Levenshtein automaton. It's just intersecting the automaton with the index.
> Whether or not you built Levenshtein automata is a pointless discussion. You say you built a DFA for Levenshtein distance (true). I'm saying that you didn't implement the paper. Both are correct.
I never claimed to implement the algorithm in the paper. Whether or not it's a Levenshtein automaton is not a pointless discussion. Lucene improved their fuzzy text search times by 100x by pruning the search. You can do that with my method too. That's why the goal here is "implement a Levenshtein automaton" not "implement a Levenshtein automaton with the algorithm described in paper XYZ".
> I'm just pointing out that your implementation, while it was fast to write, is also much much slower than their algorithm, and you shouldn't compare the two as if they were the same.
Even if my algorithm for constructing the DFA is 10x slower than theirs (which I HIGHLY doubt), it still wouldn't matter because you can still use it to get their ~100x speedup because it does exactly the same pruning and the cost of the automaton is just noise.
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.
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.