Typfouten, Levenshtein en Burkhard-Keller trees
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.
In bovenstaand geval dus één mutatie. Netjes van wikipedia gejat is dit voorbeeld, van kitten -> sitting:
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:
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.
There are 11 comments on this article, read them on Coding Glamour.