I was just talking to a colleague about edit distance because it came up in a project we’re working on.
Technically, we were discussing Levenshtein distance. It sounds more impressive to say Levenshtein distance, but it’s basically how much editing effort it would take to turn one block of text into another.
Edit distance is a fairly simple idea, and very useful. For example, the Morse code practice site LCWO [1] reports the Levenshtein distance between what you transcribe and the correct response. This better matches your intuitive idea of how well you did than some more direct ways of measuring accuracy. For example, transposing two characters is less of an error that typing two unrelated characters.
The LCWO site is unusual in that it explicitly reports Levenshtein distance. It’s far more common for the algorithm to be used behind the scenes and never mentioned by name.
Related posts
[1] Why “LCWO”? It stands for “learn CW online.” In the ham radio community, Morse code is usually called CW for historical reasons. CW stands for “continuous wave.” In principle you’re always transmitting at the same frequency, turning a carrier wave on and off, not modulating it. The details are a bit more interesting, as I write about here.
The post Edit distance first appeared on John D. Cook.