11–17 of 17 posts
Here'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.
Levenshtein (Wiki): 33.11 ± 0.83%
Levenshtein (php.js): 28.01 ± 0.43%
sift4: 1620 ± 1.26%
Levenshtein (fast-levenshtein): 37.58 ± 3.61%
I 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.
d(a, c) One great property of the Levenshtein distance is that it is a metric in the mathematical sense. This means that the following (in)equalities hold (with d being the Levenshtein distance): d(a, c) Many efficient algorithms operating on distances need the distance measure to be metric in this sense, otherwise they don't work (e.g., [1]). There is also a lot of really useful math that can’t be applied if a distance meas…
One great property of the Levenshtein distance is that it is a metric in the mathematical sense. This means that the following (in)equalities hold (with d being the Levenshtein distance): d(a, c) Many efficient algorithms operating on distances need the distance measure to be metric in this sense, otherwise they don't work (e.g., [1]). There is also a lot of really useful math that can’t be applied if a distance meas…
Unless there're clever compilation algorithms to calculate edit distance really fast, that fall apart without a metric...?
One great property of the Levenshtein distance is that it is a metric in the mathematical sense. This means that the following (in)equalities hold (with d being the Levenshtein distance): d(a, c) Many efficient algorithms operating on distances need the distance measure to be metric in this sense, otherwise they don't work (e.g., [1]). There is also a lot of really useful math that can’t be applied if a distance meas…
Could you provide examples of math application - that you mention - in the case of Levenshtein distance? I'm not interested in general topology, functional analysis etc., but what finds its use in computer science, software engineering.
Earlier quoted context omitted.
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.