Sift4: Fast and accurate string distance algorithm
siderite.blogspot.com
Sift4: Fast and accurate string distance algorithm
1–10 of 17 posts
Re: Sift4: Fast and accurate string distance algorithm
#2I like that Sift4 seems to give pretty consistent answers to Levenstein which is nice. Some of Sift3's answers are a little suspect (darn right wrong in some cases). I'd like to see more data on Sift4's performance before I consider using this over Levenstein, but overall looks pretty decent.
Re: Sift4: Fast and accurate string distance algorithm
#3Could someone explain the differences in simple terms?
I thought that Levenstein was the "golden standard" for this, but just curious what makes algorithms different. Is it purely a question of performance in terms of how fast it executes or memory consumption? Or is there a performance difference in terms of accuracy?
Re: Sift4: Fast and accurate string distance algorithm
#4Levenshtein distance is a metric that counts the number of insertions, deletions, and substitutions between strings.
If Sift4 produces different results, what does it count exactly?
Re: Sift4: Fast and accurate string distance algorithm
#5There is no proof that this approximates the Levenshtein distance. Might be interesting to show this is true. (or somehow characterize all the bad cases)
Re: Sift4: Fast and accurate string distance algorithm
#6Levenshtein distance is a metric that counts the number of insertions, deletions, and substitutions between strings. If Sift4 produces different results, what does it count exactly?
Q: I compared Sift4 with another algorithm that is much more exact and there are differences.
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
Re: Sift4: Fast and accurate string distance algorithm
#7Here's a performance test of Levenshtein vs Sift4 using UTF-8 strings for anyone interested:
Re: Sift4: Fast and accurate string distance algorithm
#8Here's a performance test of Levenshtein vs Sift4 using UTF-8 strings for anyone interested: http://jsperf.com/levenshtein-perf
if only i could see the results.
Re: Sift4: Fast and accurate string distance algorithm
#9Levenshtein distance is a metric that counts the number of insertions, deletions, and substitutions between strings. If Sift4 produces different results, what does it count exactly?
Q: I compared Sift4 with another algorithm that is much more exact and there are differences. 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 Levensht…
> 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.