I was informed that the Levenshtein distance is symmetric. When I used Google's diffMatchPatch tool which computes Levenshtein distance (among other things) the results don't imply that the Levenshtein distance is symmetric. That is, Levenshtein(x1, x2) is not equal to Levenshtein(x2, x1). Is the Levenshtein distance not symmetric or is there a problem with that particular implementation?
Just looking at the basic algorithm it definitely is symmetric given the same cost for the operations - the number of additions, deletions and substitutions to get from a word A to a word B is the same as getting from word B to word A.
If there is a different cost on any of the operations there can be a difference though, e.g. if addition has a cost of 2 and deletion a cost of 1 to get from Zombie to Zombies results in a distance of 2, the other way round would be 1 - not symmetric.