Fuzzy match-algoritmer forklaret

Det ovenstående billede har måske givet dig en idé om, hvad dette indlæg handler om.

Dette indlæg dækker nogle af de vigtige fuzzy(ikke nøjagtigt lige, men klumper de samme strenge, siger RajKumar & Raj Kumar) strengmatchningsalgoritmer, som omfatter:

Hamming Distance

Levenstein Distance

Damerau Levenstein Distance

N-Gram baseret string matching

BK Tree

Bitap algoritme

Men vi bør først vide, hvorfor fuzzy matching er vigtigt i betragtning af et virkeligt scenarie. Når en bruger får lov til at indtaste data, kan det gå rigtig galt som i nedenstående tilfælde!

Lad,

Dit navn er ‘Saurav Kumar Agarwal’.
Du har fået et bibliotekskort (med et unikt ID naturligvis), som er gyldigt for alle medlemmer af din familie.
Du går på et bibliotek for at udlevere nogle bøger hver uge. Men for at gøre dette skal du først foretage en registrering i et register ved bibliotekets indgang, hvor du indtaster dit ID & navn.

Nu beslutter biblioteksmyndighederne at analysere data i dette biblioteksregister for at få en idé om unikke læsere, der besøger hver måned. Nu kan dette gøres af mange grunde (f.eks. om man skal gå til udvidelse af arealet eller ej, om antallet af bøger skal øges osv.).

De planlagde at gøre dette ved at tælle (unikke navne, biblioteks-ID) par, der er registreret i en måned. Så hvis vi har

123 Mehul

123 Rajesh

123 Mehul

133 Rajesh

133 Sandesh

Dette skulle give os 4 unikke læsere.

Så langt så godt

De anslog dette antal til at ligge på omkring 10k-10.5k, men tallene steg til ~50k efter analyse ved hjælp af nøjagtig string matching af navne.

wooohhh!!

Smuk skøn må jeg sige!!

Og de overså et trick her?
Hvordan dette kan gøres?
Levenstein Distance/ Edit Distance
Demerau-Levenstein-afstanden
N-Gram
BK Tree
Levenshtein(Child, Query)≤t.
Bitap-algoritme

Og de overså et trick her?

Efter en dybere analyse dukkede der et stort problem op. Husk dit navn, “Saurav Agarwal”. De fandt nogle poster, der førte til 5 forskellige brugere på tværs af dit familiebiblioteks-ID:

Saurav K Aggrawal (bemærk det dobbelte ‘g’, ‘ra-ar’, Kumar bliver til K)
Saurav Kumar Agarwal
Sourav Aggarwal
SK Agarwal
Agarwal

Der findes nogle tvetydigheder, da biblioteksmyndighederne ikke ved

Hvor mange personer besøger biblioteket fra din familie? om disse 5 navne repræsenterer en enkelt læser, 2 eller 3 forskellige læsere. Kald det et uovervåget problem, hvor vi har en streng, der repræsenterer ikke-standardiserede navne, men deres standardiserede navne er ikke kendt (f.eks. Saurav Agarwal: Saurav Kumar Agarwal er ikke kendt)
Bør de alle slås sammen til “Saurav Kumar Agarwal”? Det kan jeg ikke sige, da SK Agarwal kan være Shivam Kumar Agarwal (f.eks. din fars navn). Desuden kan den eneste Agarwal være hvem som helst fra familien.

De sidste 2 tilfælde (SK Agarwal & Agarwal) ville kræve nogle ekstra oplysninger (som køn, fødselsdato, udstedte bøger), som vil blive indlæst i en eller anden ML-algoritme for at bestemme læserens faktiske navn & bør lades tilbage for nu. Men en ting jeg er ret sikker på er, at de 1. 3 navne repræsenterer den samme person & Jeg bør ikke have brug for ekstra oplysninger for at flette dem til en enkelt læser, dvs. ‘Saurav Kumar Agarwal’.

Hvordan dette kan gøres?

Her kommer fuzz string matching, hvilket betyder et næsten nøjagtigt match mellem strenge, der er lidt forskellige fra hinanden (hovedsagelig på grund af forkerte stavemåder) som ‘Agarwal’ & ‘Aggarwal’ & ‘Aggarwal’ & ‘Aggrawal’. Hvis vi får en streng med en acceptabel fejlprocent (f.eks. et bogstav forkert ), vil vi betragte den som et match. Så lad os undersøge →

Hamming-afstanden er den mest oplagte afstand beregnet mellem to strenge af samme længde, som giver en optælling af tegn, der ikke matcher svarende til et givet indeks. For eksempel: ‘Bat’ & ‘Bet’ har hamming afstand 1 som ved indeks 1, ‘a’ er ikke lig med ‘e’

Levenstein Distance/ Edit Distance

Men jeg går ud fra, at du er fortrolig med Levenstein afstand & Rekursion. Hvis ikke, skal du læse dette. Nedenstående forklaring er mere en sammenfattet version af Levensteins afstand.

Lad ‘x’=længde(Str1) & ‘y’=længde(Str2) for hele dette indlæg.

Levenstein Distance beregner det mindste antal redigeringer, der kræves for at konvertere ‘Str1’ til ‘Str2’ ved at udføre enten Tilføjelse, Fjernelse eller Udskiftning af tegn. Derfor har ‘Cat’ & ‘Bat’ en redigeringsafstand på ‘1’ (Udskift ‘C’ med ‘B’), mens den for ‘Ceat’ & ‘Bat’ ville være 2 (Udskift ‘C’ til ‘B’; Slet ‘e’).

Hvis vi taler om algoritmen, har den hovedsageligt 5 trin

int LevensteinDistance(string str1, string str2, int x, int y){if (x == len(str1)+1) return len(str2)-y+1;if (y == len(str2)+1) return len(str1)-x+1;if (str1 == str2) 
return LevensteinDistance(str1, str2, x+ 1, y+ 1);return 1 + min(LevensteinDistance(str1, str2, x, y+ 1), #insert LevensteinDistance(str1, str2, x+ 1, y), #remove LevensteinDistance(str1, str2, x+ 1, y+ 1) #replace
}
LevenesteinDistance('abcd','abbd',1,1)

Det vi gør er at begynde at læse strenge fra det 1. tegn

Hvis tegnet ved indeks ‘x’ i str1 passer med tegnet ved indeks ‘y’ i str2, ingen redigering nødvendig & beregn redigeringsafstanden ved at kalde

LevensteinDistance(str1,str2)

Hvis de ikke stemmer overens, ved vi, at en redigering er nødvendig. Så vi tilføjer +1 til den aktuelle edit_distance & beregner rekursivt edit_distance for 3 betingelser & tager det mindste ud af de tre:

Levenstein(str1,str2) →indsættelse i str2.

Levenstein(str1,str2) →udslettelse i str2

Levenstein(str1,str2)→erstatning i str2

Hvis en af strengene løber tør for tegn under rekursion, tilføjes længden af de resterende tegn i den anden streng til redigeringsafstanden (de to første if-udsagn)

Demerau-Levenstein-afstanden

Opmærksom ‘abcd’ & ‘acbd’. Hvis vi går efter Levenstein Distance, ville det være (replace ‘b’-‘c’ & ‘c’-‘b’ at index positions 2 & 3 in str2) Men hvis man ser nærmere efter, blev begge tegn byttet om som i str1 & hvis vi indfører en ny operation ‘Swap’ ved siden af ‘addition’, ‘ deletion’ & ‘replace’, kan dette problem løses. Denne indførelse kan hjælpe os med at løse problemer som ‘Agarwal’ & ‘Agrawal’.

Denne operation tilføjes ved nedenstående pseudokode

1 + 
(x - last_matching_index_y - 1 ) +
(y - last_matching_index_x - 1 ) +
LevinsteinDistance(str1, str2)

Lad os køre ovenstående operation for ‘abcd’ & ‘acbd’ hvor antager

initial_x=1 & initial_y=1 (Start af indeksering fra 1 & ikke fra 0 for begge strenge).

aktuel x=3 & y=3 derfor str1 & str2 ved henholdsvis ‘c’ (abcd) & ‘b’ (acbd).

Overste grænser inkluderet i den nedenfor nævnte skiveskæring. Derfor vil “qwerty” betyde “qwer”.

last_matching_index_y vil være det sidste_indeks i str2, der passer til str1, dvs. 2, da “c” i “acbd” (indeks 2)passer til “c” i “abcd”.
last_matching_index_x vil være det sidste_indeks i str1, der passer til str2 i.e 2 som “b” i “abcd” (indeks 2)matchede med “b” i “acbd”.
Som følge af ovenstående pseudokode vil DemarauLevenstein(‘abc’,’acb’)=

1+(4-3-1) + (4-3-1)+ (4-3-1)+LevensteinDistance(‘a’,’a’)=1+0+0+0+0=1. Dette ville have været 2, hvis vi havde fulgt Levenstein Distance

N-Gram

N-gram er dybest set ikke andet end et sæt værdier, der genereres fra en streng ved at parre sekventielt forekommende ‘n’ tegn/ord. For eksempel: n-gram med n=2 for ‘abcd’ vil være ‘ab’,’bc’,’cd’.

Nu kan disse n-grammer genereres for strenge, hvis lighed skal måles & Der kan anvendes forskellige målemetoder til at måle ligheden.

Lad ‘abcd’ & ‘acbd’ være 2 strenge, der skal matches.

n-grammer med n=2 for

‘abcd’=ab,bc,cd

‘acbd’=ac,cb,bd

Komponentmatch (qgrammer)

Tal n-grammer, der matcher nøjagtigt for de to strenge. Her ville det være 0

Cosine Similarity

Beregning af prikproduktet efter konvertering af n-grammer genereret for strenge til vektorer

Komponentmatch (ingen rækkefølge taget i betragtning)

Matching af n-grammernes komponenter uden hensyntagen til rækkefølgen af elementerne i dvs. bc=cb.

Der findes mange andre sådanne metrikker som Jaccard-afstand, Tversky-indeks osv., som ikke er blevet diskuteret her.

BK Tree

BK tree er blandt de hurtigste algoritmer til at finde frem til lignende strenge (fra en pulje af strenge) for en given streng. BK tree bruger en

Levenstein Distance
Triangle inequality (vil dække dette ved slutningen af dette afsnit)

til at finde frem til lignende strenge(& ikke bare én bedste streng).

Et BK tree oprettes ved hjælp af en pulje af ord fra en tilgængelig ordbog. Lad os sige, at vi har en ordbog D={Book, Books, Cake, Cake, Boo, Boon, Cook, Cape, Cart}

Et BK-træ oprettes ved at

Vælg en rodknude (kan være et hvilket som helst ord). Lad det være ‘Books’
Gå igennem hvert ord W i ordbogen D, beregn dets Levenstein-afstand til rodknuden, og gør ordet W til rodknudens barn, hvis der ikke findes noget barn med samme Levenstein-afstand til forælderen. Indsættelse af Bøger & Kage.

Levenstein(Bøger,Bog)=1 & Levenstein(Bøger,Kage)=4. Da der ikke er fundet noget barn med samme afstand for “Book”, skal du lave dem til nye børn for roden.

https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/

Og de overså et trick her?

Hvordan dette kan gøres?

Levenstein Distance/ Edit Distance

Demerau-Levenstein-afstanden

N-Gram

BK Tree

Levenshtein(Child, Query)≤t.

Bitap-algoritme

Skriv et svar Annuller svar