Some applications of Levenshtein, such as spell checking and google suggest, seem like game physics in that they are consumed by humans, and gross approximations are good enough - even with occasional glitches. Speed trumps accuracy.

Unless there're clever compilation algorithms to calculate edit distance really fast, that fall apart without a metric...?