Pragmatic Edition Distance<br>- The Dark Side
Image source
06 Jul 2026 -
The Dark Side
Pragmatic Edition Distance
I deal with multilingual environments, for which I am<br>pretty fond of phonetic<br>indexing, it is a nice way<br>to go from what you think you have heard to the actual name of a thing. However<br>sometimes the collisions are retrieving more data than you would like.
After matching (getting items that are relevant for a query), you need a form<br>of scoring where you put the best ones first. Common use cases are<br>search results or autocomplete suggestions. Scoring processes less<br>entries so it can afford to be slower than matching.
Small note here: this algorithm has a high complexity, it will scale poorly with<br>big chunks of text. On top of it some caching and optimizations are possible.
To frame the problem:
# All the code here is in PHP
$input = 'rue Evy';
$rawMatches = [ # Addresses<br>'4 Rue de Houffalize, 1737 Luxembourg',<br>'9 Rue Jean l\'Aveugle, 1148 Luxembourg',<br>'310 rue Evy Friedrich, 1552 Luxembourg',<br>'10 Rue Edouard Oster, 2272 Howald',<br>];
Edition distances
PHP comes with a pretty standard and configurable edition distance function:<br>levenshtein. This<br>function accepts custom costs for adding, replacing or removing a character. In<br>this specific case, we rather mostly trust the user input: if something needs<br>to be removed it is rather a bad sign and needs to be penalized.
function getEditionDistance(string $source, string $target): int {<br># 2 cost on replace and 3 cost on deletion to penalize changing the input<br>return levenshtein($source, $target, 1, 1, 2);
$distancesInfo = array_map(<br>fn($m) => $m . ': ' . getEditionDistance($input, $m),<br>$rawMatches<br>);
'4 Rue de Houffalize, 1737 Luxembourg: 33',<br>'9 Rue Jean l\'Aveugle, 1148 Luxembourg: 33',<br>'310 rue Evy Friedrich, 1552 Luxembourg: 31', # Lowest cost ⬇️<br>'10 Rue Edouard Oster, 2272 Howald: 29',
The third entry which seems the obvious match does not have the lowest score.
Normalizing string length
One of the reason for the above behavior, is that the edition distance<br>penalizes adding characters, so<br>a shorter target string gets a boost that can be disproportionate.<br>The obvious solution is to normalize with<br>the string length: a simple way to give more “proportion”.
function getEditionDistance(string $source, string $target): float {<br>$distance = levenshtein($source, $target, 1, 1, 2);<br>$normalizationFactor = strlen($target) + 1; // no 0 division<br>return $distance / $normalizationFactor;
$distancesInfo = array_map(<br>fn($m) => $m . ': ' . round(getEditionDistance($input, $m), 4),<br>$rawMatches<br>);
Now we have something better:
'4 Rue de Houffalize, 1737 Luxembourg: 0.8919',<br>'9 Rue Jean l\'Aveugle, 1148 Luxembourg: 0.8684',<br>'310 rue Evy Friedrich, 1552 Luxembourg: 0.7949', # lowest cost 👌<br>'10 Rue Edouard Oster, 2272 Howald: 0.8529',
Normalizing for exoticism
Let’s change our problem a bit.
$input = '4 rue Evy'; // Note the number
$rawMatches = [<br>'4 avenue d\'evý, 1737 Luxembourg',<br>'310 rue Evy Friedrich, 1552 Luxembourg',<br>];
A bunch of topics here:
Casing
Diacritics
Common names, I will expand later on “rue” and “avenue”
Numbers
English has strong points as a lingua franca (simple grammar mostly), it also<br>has some weakness as the<br>de-facto standard for software: it is so simple that it leads us to ignore a lot<br>of edge cases. From a Latin European point of view the most obvious ones are<br>diacritics (fancy name for accents) that makes a lot of letters look similar to<br>the reader but being written with a different character it simply two different<br>symbols for the computer ; or often more…
Fortunately PHP has a Transliterator to handle this.<br>I have no deep understanding of the $rules but someone on the internet said it<br>works.
function removeDiacritics(string $input): string {<br>$input = strtolower($input); # case removal
$rules = ':: Any-Latin; :: Latin-ASCII; :: NFD; :: ' .<br>'[:Nonspacing Mark:] Remove;';
# you can also strtolower post facto<br>$rules .= ' :: Lower();';
$rules .= ' :: NFC;';<br>$transliterator = \Transliterator::createFromRules(<br>$rules, \Transliterator::FORWARD);
return $transliterator->transliterate($input);
removeDiacritics($rawMatches[0]);<br># From<br>'4 avenue d\'evý, 1737 Luxembourg'
# To<br>'4 avenue d\'evy, 1737 luxembourg'
Another one might be the German “ß”, that could be substituted with “ss” (not<br>handled by the code above).
Normalizing for bloat
Then comes the very poorly named “stop words”, which describe “small words<br>conveying little meaning in a language”. English could have “of”, “the”, “a”, …<br>French “du”, “d’”, “la”, “des”, … German “der”, “die”, “das”, …
Those small grammatical markers are rarely important for a meaning and are<br>subjects<br>to a lot of errors in international contexts. Plus those small markers, will be<br>disproportionately penalized based on their length mistaking “de” and “du” will<br>cost less that “the” and “a”.
$stopWords = [<br>// english<br>'of', 'the', 'a', // ...
// french<br>'le', 'la', 'de', 'd\'', //...