The textbook implementation of edit distance takes O(n²) work. The PHP standard library can compute a greedy approximation in Ω(n³).
php.net/similar_text
php.netPosted May 31, 2012, 4:56 AM UTC
308
php.netExtra WTF: they also have a pretty generic edit distance function called levenshtein which is indeed O(mn).
12
Oh dear God, is there any part of this language that does NOT have another WTF hidden inside it?!
First of all, it works on bytes, so you can only use it for ASCII. Even then, it silently fails if your input string is longer than 256 bytes, and returns... Minus one. Not infinity. Not NaN. Not an exception. Minus one. This, uhm, slightly important fact is only mentioned in the "RETURN VALUE" section of the "best documentation on the web".
Bonus WTF:
/* {{{ custom_levdist
*/
static int custom_levdist(char *str1, char *str2, char *callback_name TSRMLS_DC)
{
php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");
/* not there yet */
return -1;
}
/* }}} */
11
PHP has never understood how to do errors. There's NULL, false, 0, -1, exceptions and complete silence.
I'm not saying Haskell programmers have it easier (there are now roughly 10 ways to report errors in Haskell), but at least it's documented and a lot of research is being done to improve it.
5
Ooh, I missed this part of the documentation:
A second variant will take three additional parameters that define the cost of insert, replace and delete operations. This is more general and adaptive than variant one, but not as efficient.
Guess which version is actually implemented by calling which version with the fixed parameters 1, 1, 1...
5
Extra WTF: the description that says it does not use a stack, when it fact it does use a stack, in the form of the call stack.
-6
There is a difference between solving a problem iteratively with a stack, then recursively using a call stack. The description is alluding to this, which isn't that misleading.
5
[deleted]
1
I can only assume the source is cited as
Oliver [1993]because that's how they've seen other people cite things, completely failing to understand that it's supposed to be a reference to the full citation at the end of the paper.Some poor soul on StackOverflow managed to find the book. From the blurb: "Less mathematical and more practical in approach than other volumes, it helps programmers save research and programming time and enables them to quickly and easily generate efficient structured code in solving such problems."
They cited a copybook.
Here it is: http://www.amazon.com/Programming-Classics-Implementing-Worlds-Algorithms/dp/0131004131