This post was originally published on Coding Glamour.

Momenteel nog aan het werk aan een project waar ik al eerder helemaal los op ging, alwaar ik vandaag aankwam op de mogelijkheid van typfouten.

Levenshtein distance
De levenshtein distance is het minimale aantal bewerkingen dat nodig is om van het ene woord naar het andere woord te komen. 

1: Amsterdam
2: Amsteldam

A m s t e r d a m
          ^
A m s t e   d a m

In bovenstaand geval dus één mutatie. Netjes van wikipedia gejat is dit voorbeeld, van kitten -> sitting: 

1. kitten -> sitten (substitution of 'k' with 's')
2. sitten -> sittin (substitution of 'e' with 'i')
3. sittin -> sitting (insert 'g' at the end).


Waar is het goed voor?
We kunnen veel met Soundex en alternatieve woorden, maar fuzzy matching is daarmee niet mogelijk. Door alle plaatsen / straten / etc. te vinden die een afstand van één hebben tot de zoekterm kan je vrij eenvoudig een lijst met alternatieven geven (natuurlijk samen met Soundex). Snelheid
Mijn eerste, naieve implementatie van dit algoritme voor een afstand van 1 was ongeveer: 

string query = "amsterdam";
foreach(var key in eenIndex) {
     // Levenshtein distance is altijd minimaal het verschil in lengte
     if(Math.Abs(key.Length - query.Length) > 1) continue;
     if(Levenshtein.Compute(key, query) <= 1) {
          // doe iets
     }
}

Over een half miljoen strings doet dit stuk alleen 500 ms. wat veel te veel is, dus optimalisatietijd.

Burkhard-Keller trees
Specifiek voor dit probleem is er de BK-tree (leestip!) waarbij woorden in afstand ten opzichte van elkaar worden opgeslagen in een boomstructuur. Zou het querien een stuk sneller moeten maken. Wordt ongetwijfeld vervolgd.