Research And Tests
We testten verschillende algoritmen om strings te vergelijken en selecteerden de algoritmen die beter aan onze behoefte zouden voldoen.
we hebben String A en String B vergeleken om metrics te hebben op de verschillende algoritmen.
regels voor gelijkaardigheid van tekenreeksen kunnen van geval tot geval verschillen. Als u wilt overwegen “niche” en “chien” vergelijkbaar, zou je een tekenreeks gelijkenis algoritme dat anagrammen detecteert gebruiken. Niet in ons geval. Een app genaamd ” niche “en een andere genaamd” chien ” zijn zeer waarschijnlijk twee totaal verschillende apps.
na wat brainstormen en onderzoek kwamen we met een aantal algoritme methoden die onze case zouden helpen. Het cosinus-algoritme bleek voor ons irrelevant, omdat het bijvoorbeeld geen rekening lijkt te houden met de lettervolgorde, die leidt tot een index van 1 (vergelijkbare string) op een anagram (“niche” en “chien”).
hier is wat we merkten:
Levenshtein-algoritme
de Levenshtein-afstand is het minimum aantal bewerkingen van één teken dat nodig is om het ene woord in het andere te veranderen, dus het resultaat is een positief geheel getal, gevoelig voor stringlengte . Wat het moeilijker maakt om een patroon te tekenen.
bijvoorbeeld,
- de Levenshtein-afstand tussen” foo “en” bar “is 3
- de Levenshtein-afstand tussen” schoonheden “en”mooi”is ook 3
- voor ons, mensen, lijkt het paar” schoonheden “/”mooi”veel meer op het paar” foo ” / “bar”. Maar de Levenshtein afstand is hetzelfde.
de metriek die we hier gebruiken is de inverse van de Levenshtein afstand ( 1 / levenshtein_distance ) dus het resultaat is een percentage en is gemakkelijker af te lezen door ons. Maar het hierboven genoemde probleem bleef hetzelfde.
waarbij 1 het resultaat is van het vergelijken van identieke strings, hebben “ShazamIphone” en “ShazamAndroid” een gelijkenis van 0,167. “chien” en “niche” hebben een gelijkenis van 0,25.
vanuit het oogpunt van het Levenshtein algoritme lijken Chien/Niche meer op “ShazamIphone” / ” ShazamAndroid “omdat er minder bewerkingen nodig zijn om van” chien “naar” niche “te gaan, dan om van” ShazamIphone “naar”ShazamAndroid” te gaan.
Trigram vergelijking
een trigram algoritme is een geval van n-gram, een aaneengesloten reeks van n (drie, in dit geval) items uit een gegeven Monster. In ons geval is een naam van een toepassing een voorbeeld en een teken is een item.
dus de reeks “martha” heeft 4 trigrammen { mar art rth tha }.
we kunnen de Trigram methode gebruiken om twee strings te vergelijken.
met bijvoorbeeld “martha” en hetzelfde woord met een typo, “marhta”, en we kunnen hun trigrammen berekenen:
trigrammen “martha”: { mar art rth tha }
trigrammen “marhta”: {mar arh rht HTA }
om gelijkenis te meten delen we het aantal overeenkomende trigrammen in beide strings: 1 { mar } door het aantal unieke trigrammen: 7 maart. art.}
The result is 1/7 = 14%
om het nadeel van de buitenste karakters in evenwicht te brengen (enigszins om de gelijkenis van strings te versterken die beginnen en eindigen met dezelfde trigrammen), vullen we de string aan met spaties aan weerszijden, wat resulteert in drie trigrammen “_ma”, “ha_” en “ta_”.
trigrammen “martha”: { _ma mar art rth tha ha_ }
trigrammen “marhta”: { _ma mar arh rht HTA ta_ }
na dat te hebben gedaan, is het aantal overeenkomende trigrammen maximaal: 2 { _ma mar }
het aantal unieke trigrammen: (‘) Zie bijlage.}
The result is now 2/9 = 22%
met behulp van deze methode om “Twitter v1” en “Twitter v2” te vergelijken hebben we:
het aantal overeenkomende trigrammen: 7 { _tw twi wit itt tte ter er_ }
het aantal unieke trigrammen: 11 { Twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
de limiet van de Trigram methode om strings te vergelijken is dat korte strings met één (of twee).. verschillende trigrammen hebben de neiging om een lagere gelijkenis te produceren dan lange trigrammen.
zo krijgen we een 0.2 gelijkenis tussen “ShazamAndroid” en “ShazamIphone”, omdat ze meer verschillende trigrammen.
het aantal overeenkomende trigrammen is: 5 { _sh sha haz aza zam }
het aantal van alle unieke trigrammen: 20
aangezien er een sterke afhankelijkheid is met de lengte van de tekenreeks, levert dit voor ons geen goede vergelijking op.
jaro-Winkler algoritme
“in de informatica en Statistiek is de Jaro-Winkler afstand een string metriek voor het meten van de bewerkingsafstand tussen twee reeksen.
informeel is de Jaroafstand tussen twee woorden het minimum aantal omzettingen van één teken dat nodig is om het ene woord in het andere te veranderen.
de Jaro-Winkler-afstand maakt gebruik van een voorvoegselschaal die gunstigere waarderingen geeft aan tekenreeksen die vanaf het begin overeenkomen met een ingestelde voorvoegsellengte”
Bron: Wikipedia.
het geven van” meer belang ” aan woorden met identieke voorvoegsels maakte de jaro-Winkler afstand zeer interessant voor onze use case.
vanaf het begin met de jaro afstand formule, hier hoe het werkt. Geen paniek, we gaan stap voor stap:
De Jaro Afstand tussen twee sequenties s1 en s2 is gedefinieerd door:
dj is de Jaro afstand
m is het aantal overeenkomende tekens (tekens die worden weergegeven in s1 en s2)
t is de helft van het aantal transposities (vergelijk de i-th karakter van de s1 en de ik-th karakter van s2 gedeeld door 2)
|s1| is de lengte van de eerste string
|s2| is de lengte van de tweede tekenreeks
Met een voorbeeld. Laten we “martha” en “marhta”nemen.
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
gewoon door getallen te vervangen is de formule, krijgen we:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
nu we weten wat de jaro afstand is, springen we naar de jaro-Winkler afstand.
de gelijkenis van Jaro-Winkler maakt gebruik van een voorvoegselschaal p, die gunstigere waarderingen geeft aan tekenreeksen die vanaf het begin overeenkomen met een ingestelde voorvoegsellengte l.
p is een constante schaalfactor voor de mate waarin de score naar boven wordt bijgesteld voor het hebben van gemeenschappelijke voorvoegsels. De standaardwaarde voor deze constante in Winklers werk is p = 0,1.
l is de lengte van het gemeenschappelijke voorvoegsel aan het begin van de tekenreeks (tot maximaal 4 tekens).
dus terug naar het” martha “/” marhta “voorbeeld, laten we een voorvoegsel lengte van l = 3 nemen (wat verwijst naar”mar”). We gaan naar:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
met behulp van de jarowinkler formule gaan we van de jaro afstand op 94% gelijkenis met 96%.
in ons geval beginnen de meeste vergelijkbare apps met hetzelfde voorvoegsel (“twitter v1 “vs” twitter v2 “of” ShazamIphone “vs” ShazamAndroid ” etc. Zie de algoritmen testtabel hierboven). Het is dus een belangrijk criterium om rekening mee te houden.
