Pragmatic Edition Distance

I deal with multilingual environments, for which I am pretty fond of phonetic indexing, it is a nice way to go from what you think you have heard to the actual name of a thing. However 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 of scoring where you put the best ones first. Common use cases are search results or autocomplete suggestions. Scoring processes less entries so it can afford to be slower than matching.

Small note here: this algorithm has a high complexity, it will scale poorly with 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
    '4 Rue de Houffalize, 1737 Luxembourg',
    '9 Rue Jean l\'Aveugle, 1148 Luxembourg',
    '310 rue Evy Friedrich, 1552 Luxembourg',
    '10 Rue Edouard Oster, 2272 Howald',
];

Edition distances

PHP comes with a pretty standard and configurable edition distance function: levenshtein. This function accepts custom costs for adding, replacing or removing a character. In this specific case, we rather mostly trust the user input: if something needs to be removed it is rather a bad sign and needs to be penalized.

function getEditionDistance(string $source, string $target): int {
    # 2 cost on replace and 3 cost on deletion to penalize changing the input
    return levenshtein($source, $target, 1, 1, 2);
}

$distancesInfo = array_map(
    fn($m) => $m . ': ' . getEditionDistance($input, $m),
    $rawMatches
);

[
  '4 Rue de Houffalize, 1737 Luxembourg: 33',
  '9 Rue Jean l\'Aveugle, 1148 Luxembourg: 33',
  '310 rue Evy Friedrich, 1552 Luxembourg: 31', # Lowest cost ⬇️
  '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 penalizes adding characters, so a shorter target string gets a boost that can be disproportionate. The obvious solution is to normalize with the string length: a simple way to give more “proportion”.

function getEditionDistance(string $source, string $target): float {
    $distance = levenshtein($source, $target, 1, 1, 2);
    $normalizationFactor = strlen($target) + 1; // no 0 division
    return $distance / $normalizationFactor;
}

$distancesInfo = array_map(
    fn($m) => $m . ': ' . round(getEditionDistance($input, $m), 4),
    $rawMatches
);

Now we have something better:

[
  '4 Rue de Houffalize, 1737 Luxembourg: 0.8919',
  '9 Rue Jean l\'Aveugle, 1148 Luxembourg: 0.8684',
  '310 rue Evy Friedrich, 1552 Luxembourg: 0.7949', # lowest cost 👌
  '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 = [
    '4 avenue d\'evý, 1737 Luxembourg',
    '310 rue Evy Friedrich, 1552 Luxembourg',
];

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 has some weakness as the de-facto standard for software: it is so simple that it leads us to ignore a lot of edge cases. From a Latin European point of view the most obvious ones are diacritics (fancy name for accents) that makes a lot of letters look similar to the reader but being written with a different character it simply two different symbols for the computer ; or often more…

Fortunately PHP has a Transliterator to handle this. I have no deep understanding of the $rules but someone on the internet said it works.

function removeDiacritics(string $input): string {
    $input = strtolower($input); # case removal
    
    $rules = ':: Any-Latin; :: Latin-ASCII; :: NFD; :: ' .
                '[:Nonspacing Mark:] Remove;';

    # you can also strtolower post facto
    $rules .= ' :: Lower();';
    
    $rules .= ' :: NFC;';
    $transliterator = \Transliterator::createFromRules(
        $rules, \Transliterator::FORWARD);
  
    return $transliterator->transliterate($input);
}

removeDiacritics($rawMatches[0]);
# From
'4 avenue d\'evý, 1737 Luxembourg'

# To
'4 avenue d\'evy, 1737 luxembourg'

Another one might be the German “ß”, that could be substituted with “ss” (not handled by the code above).

Normalizing for bloat

Then comes the very poorly named “stop words”, which describe “small words conveying little meaning in a language”. English could have “of”, “the”, “a”, … French “du”, “d’”, “la”, “des”, … German “der”, “die”, “das”, …

Those small grammatical markers are rarely important for a meaning and are subjects to a lot of errors in international contexts. Plus those small markers, will be disproportionately penalized based on their length mistaking “de” and “du” will cost less that “the” and “a”.

$stopWords = [
    // english
    'of', 'the', 'a', // ...
    
    // french
    'le', 'la', 'de', 'd\'', // ...
    
    // german
    'der', 'die', 'das', // ... 
];

function replaceStopWords(string $input): string {
    global $stopWords;
    foreach ($stopWords as $stopWord) {
        $input = preg_replace("/\b$stopWord\b/", '_', $input);
    }
    
    return $input;
}

replaceStopWords('le prince de sang mele');
'_ prince _ sang mele';

Normalizing inputs for domain knowledge

Similar to stop words for a language, I am dealing with addresses here, so “boulevard” and “blvd” should be the same, and “rue” (“street” in french), should not be too far from it.

$domainSubstitutions = [
    // Normalize wording
    'blvd' => 'boulevard',
    
    // reduce cost of edition
    'boulevard' => 'b_',
    'avenue' => 'a_',
    'rue' => 'r_',
];

function substituteForDomain(string $input, bool $keepNumbers=false): string {
    global $domainSubstitutions;
    $substitutions = $domainSubstitutions;   
    if (!$keepNumbers) {
        $substitutions['\d+'] = '';
        $substitutions['\s+'] = ' '; // redundant spaces
    }
    
    foreach ($substitutions as $pattern => $newValue) {
        $input = preg_replace("/\b$pattern\b/", $newValue, $input);
    } 
    
    return trim($input);   
}

var_export(substituteForDomain('4 avenue   d\'evy'));
'a_ d\'evy';

var_export(substituteForDomain('31 rue evy'));
'rue evy';

Normalizing inputs for edge cases

In some countries, streets can have multiple names (Luxembourg’s has three on the bad days) ; sometimes just translations, sometimes fully different, sometimes people mix them.

I will leave it unimplemented but mappings like this might be relevant:

$commonMismatches = [
    'Jean' => 'John',
    'Jan' => 'John',
    'Giovanni' => 'John'
];

Final version

function preprocess(string $string, bool $keepNumbers): string {
    $string = replaceStopWords(removeDiacritics($string)); 
    return substituteForDomain($string, $keepNumbers);
}

function getFinalEditionDistance(string $source, string $target): float {
    $hasDigits = preg_match('/\d/', $string) === 1;
    $source = preprocess($source, $hasDigits);
    $target = preprocess($target, $hasDigits);

    $distance = levenshtein($source, $target, 1, 1, 2);
    $normalizationFactor = strlen($target) + 1;
    return $distance / $normalizationFactor;
}

$input = '4 rue Evy';

$rawMatches = [
    '4 avenue d\'evý, 1737 Luxembourg',
    '9 Rue Jean l\'Aveugle, 1148 Luxembourg',
    '310 rue Evy Friedrich, 1552 Luxembourg',
    '10 Rue Edouard Oster, 2272 Howald',
];

$distancesInfo = array_map(
    fn($m) => $m . ': ' . round(getFinalEditionDistance($input, $m), 4),
    $rawMatches
);

[
    '4 avenue d\'evý, 1737 Luxembourg: 0.7143', # lowest cost 👌
    '9 Rue Jean l\'Aveugle, 1148 Luxembourg: 0.8065',
    '310 rue Evy Friedrich, 1552 Luxembourg: 0.7667', # second lowest cost 🫶
    '10 Rue Edouard Oster, 2272 Howald: 0.8077',
];

The matching street number in the input gives a bonus to the first line, even if “rue” and “avenue” are a lot different it stays first.

Conclusion

This workflow is not perfect. It is even hackish to be honest, too many _ around, and if you can use a FULLTEXT field search in your database, you probably should. However, I think it is important to keep in mind, as shown in this piece, that a lot of things might require ad-hoc fine-tuning or configuration, as language and domain have a non-negligible impact.

This approach also totally neglects writing systems that are syllabic, redundant or logographic as I have zero experience on them. For sure addressing similar topics in Chinese scripts or in a combination of Japanese Hiragana and Katakana must be a pretty interesting topic.