Forum und email
Strings
PHP Manual

levenshtein

(PHP 4 >= 4.0.1, PHP 5)

levenshtein — Berekent de Levenshtein afstand tussen twee strings

Beschrijving

int levenshtein ( string $str1 , string $str2 )
int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )
int levenshtein ( string $str1 , string $str2 , function $cost )

Deze 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 moet een positieve integer teruggeven, die de kost voor deze bewerking beschrijft, maar het mag alleen maar sommige van de meegegeven argumenten gebruiken.

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().

Strings
PHP Manual