(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)
levenshtein -- Berekent de Levenshtein afstand tussen twee stringsDeze functie geeft de Levenshtein-afstand tussen de twee argument strings of -1 weer, als een van de argumenten is langer dan de grens van 255 karakters (255 zou meer dan genoeg moeten zijn voor naam of dictionary vergelijking, en een serieus persoon zou geen genetische analyses gaan doen met PHP).
De Levenshtein afstand is gedefnieerd als het minimum aantal
karakters die vervangen, ingevoegd of verwijderd moeten worden
om str1
naar str2
te transformeren.
De complexiteit van het algoritme is O(m*n),
waar n en m de lengte zijn
van str1
en str2
(vrij goed vergeleken met similar_text(), wat
O(max(n,m)**3) is, maar nog vrij kostbaar).
In haar meest simpele vorm neemt de functie alleen de twee
strings als parameter en zal het alleen het aantal invoeg- vervang-
en verwijderbewerkingen berekenen die nodig zijn voor het transformeren
van str1
in str2
.
Een tweede variant neemt 3 parameters die de kosten van de invoeg- vervang- en verwijderbewerkingen definieren. Dit is meer algemeen en aanpasbaar dan de eerste variant, maar minder efficient.
De derde variant (welke nog niet geimplementeerd is) zal de meest algemene en aanpasbare, maar ook het meest trage alternatief worden. Deze zal een user-voorziene functie aanspreken die zal bepalen wat de kost zal zijn voor elke mogelijke bewerking.
De uservoorziene functie zal worden aangesproken met de volgende argumenten:
uit te voeren bewerking: 'I', 'R' or 'D'
betreffende karakter in string 1
betreffende karakter in string 2
positie in string 1
positie in string 2
overblijvende karakters in string 1
overblijvende karakters in string 2
De user-voorziene functie aanpak biedt de mogelijkheid om op te nemen de relevantie van en/of de mogelijkheid tot het opnemen van verschil tussen bepaalde symbolen (karakters) of zelfs de context waarin deze symbolen verschijnen om de kost van de invoeg- vervang- en verwijderbewerkingen te bepalen, maar tegen de kost van het verliezen van alle optimalisatie de gedaan wordt met betrekking tot cpu register utilisatie en cache missingen die in de andere varianten opgenomen zijn.
Zie ook soundex(), similar_text() en metaphone().