2 ms·

is Levenshtein distance a "metric" in the sense of "metric spaces"? For example, the TaxiCab metric. https://en.wikipedia.org/wiki/Taxicab_geometry https://en

• jvanderbot 7y ago
  Yes, it is a metric. The following is BS "proof by restatement of requirements". 1. Always >= 0 (what is a negative character edit?) 2. It satisfies identiy in that if no edits are required to make them equal, metric distance is 0 and they are equal (applies to either ordering of strings A->B and B->A) 3. It is symmetric (run the edits backwards to get B->A instead of A->B) 4. It satisfies triangle inequality. exercise left to reader, but intuitive since the edit distance is always the "shortest path" through character changes between two strings A and B, and deviating to visit an intermediate string C would not decrease number of edits from A->C->B vs original path A->B I'm sleep deprived due to "offspring induced insomnia" so take this with a grain of salt.