4 ms·
If you look closely, you'll notice that for each character, I square the difference. This is to to put extra emphasis on larger differences. If we don't do this
by jessedhillon 15y ago
If you look closely, you'll notice that for each character, I square the difference. This is to to put extra emphasis on larger differences. If we don't do this, the string "Hannp" would have a fitness of 0. You see, the difference between 'e' and 'a' is -5, between 'l' and 'n' is +2 (which we have twice) and between 'o' and 'p' is +1. Adding these up yields a fitness of 0, but it's not the string we want at all.
Squaring is a dumb way to avoid that problem. You can still have false positives: for example if a string differs from the target by two letters, who distances are +1 and -1, then squaring will not mitigate the issue.
EDIT: I realize now that -1^2 is a positive number...
I'm very surprised that the author doesn't know about the Levenshtein distance metric http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance
That seems like it would be the perfect utility function for this case.
- sparky 15y agoErr.. I would argue that (+1)^2+(-1)^2 would not yield a false positive. You are right that the explanation is incomplete, though. The squaring provides an 'absolute value' effect as well as disproportionately weighting larger alphabetical distances.
- mahcuz 15y agoRegarding the squaring - would it be enough to take the absolute value of the distance? (abs -5) + (abs 5) = 10.
- jessedhillon 15y agoIt's still a problematic way to quantify distance between strings. It says that "Rello World" is as close to the target as "Ifmkn Vpqkc" Levenshtein would quantify those differently, and I'd argue, more correctly. It would say the first is much closer than the second.