4 ms·
The names 'edit distance' and 'levenshtein distance' are a bit unfortunate. When I was trying to match batches of OCR'd strings to known strings, I knew some a
by mrkeen 7y ago
The names 'edit distance' and 'levenshtein distance' are a bit unfortunate.
When I was trying to match batches of OCR'd strings to known strings, I knew some algorithm like this had to exist, but I could not find it. My searches kept turning up Jaccard similarity and Hamming distance again and again.
(Once I found it and began working on an implementation, I started noticing my compiler would find miss-typed variable names and suggest the correctly-spelled variable for me.)
- jointpdf 7y agoThere are a lot of unhelpfully named metrics, algorithms, etc. but I actually think “edit distance” is fairly illustrative as these things go. Another good one is Manhattan distance (or better yet, city block distance) in place of Hamming distance. It gives a nice mental picture of the number of road segments you’d need to travel in a city to get from point A to point B.
- vallismortis 7y agoOne step further (multi-layer Manhattan distance) will also get you optimal DNA, RNA and protein sequence alignment (Myers, Gotoh and others, 1977-1981). The edit path (often discarded) can be repurposed for simulating RNA and protein folding, as well as calculating DNA melting points (used for DNA-DNA hybridization studies).
- johnhenry 7y agoAlso know as the "Taxi Cab" metric... as in how a taxi cab would traverse a city along parallel/perpendicular streets.
- tomglynch 7y agoGoogling distance between two strings has Lev. dist as the top response.