Re:Sift4: Fast and accurate string distance algorithm
by patal on Tuesday October 27, 2015 @07:14PM
(#10461855)
> Or if you have a list of 1,000,000 words, then you can use Sift to pare that down to the top 100 closest, then use Levenshtein to get the exact one.
You cannot do that, because, other than performance, Sift gives no guarantees regarding accuracy. The exact one, or rather the closest match, need not be among the 100 closest sift candidates.
A: Of course, they are different algorithms. This is a fuzzy distance calculator, it doesn't give you the exact value. There are still edge cases. But the idea of Sift is to be fast and relatively accurate, rather than very accurate. You need more accuracy, try to combine Sift with Levenshtein for example, computing Levenshtein only where Sift says the strings are above a certain similarity.
In other words, if there are 5000 words, and you need to pick one that's pretty close (or far away) from a target word, but don't care so much about being exact, but do care about performance, then you can use Sift. Or if you have a list of 1,000,000 words, then you can use Sift to pare that down to the top 100 closest, then use Levenshtein to get the exact one.
tl;dr
Exact Algorithm vs Heuristic