Similarly, I don't think graph databases have that much in common with RDF. Yes, both are graphs, but they're quite different, really.
122 karma · joined September 10, 2008
Similarly, I don't think graph databases have that much in common with RDF. Yes, both are graphs, but they're quite different, really.
This whole dialogue is utterly wrong-headed, and I don't for a second believe that that economist is a real economist.
So this whole "discussion" is totally wrong-headed.
Secondly, it is possible to do better than the Wagner-Fischer algorithm in certain cases. I figured this out myself and was about to write a paper on it when I realized that other researchers had beat me to it by a couple of decades.
If the two strings are equal you can establish that the edit distance is 0 in linear time, obviously. If you consider how the algorithm fills out the square down the diagonal you'll see that if there's only a one-letter difference you only actually need to fill out small parts of the grid around that difference.
This is generalizable, so the complexity actually depends on the distance between the strings.