levenshtein

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 :

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