Weblogs

Fuzzy matching van tekst

Periodiek publiceren wij inhoudelijke verhalen van onze Tech Consultants op onze website. Wat speelt er binnen hun vakgebied? Vandaag een verhaal van RIG Data Engineer Thomas Brinkman over ‘Fuzzy matching van tekst’!

We kennen allemaal het probleem dat adressen, namen, etc. op verschillende manieren worden geschreven. Het ene systeem heeft het bijvoorbeeld over de ‘Hoofdstraat’, het andere over ‘Hoofdstr.’

VOORNAAM ACHTERNAAM STRAAT HUISNR
Jan Jansen Hoofdstraat 6
Jan Jansen Hoofdstr. 6
Thomas Brinkman

Over het algemeen hebben mensen hier geen probleem mee. Wij weten dat “str” in een adres een afkorting is van straat en zien wel dat het hier om dezelfde persoon gaat. Maar hoe kunnen we dit eenvoudig matchen in een database?

Vooral in situaties waar we data uit verschillende systemen krijgen (zoals datawarehousing) lopen we tegen dit probleem aan. Is dit hetzelfde adres? Een postcode kan hier vaak een uitkomst bieden, maar ook op andere datavelden kunnen we dit probleem tegenkomen. Zijn bijvoorbeeld de volgende personen dezelfde personen of misschien toch twee personen op hetzelfde adres?:

VOORNAAM ACHTERNAAM STRAAT HUISNR
Jozua Jansen Hoofdstraat 6
Yozua Jansen Hoofdstraat 6

Het is erg waarschijnlijk dat het dezelfde persoon is. En weer hebben mensen hier geen probleem mee. Maar hoe is dit eenvoudig te matchen?

Er zijn veel voorbeelden waar bijna identieke data voor de mens geen probleem oplevert maar het voor een computer wel een probleem is. Hoe kan dit gematcht worden? En wanneer wordt de onzekerheid te groot?

Sounds like…

Het is geen nieuw probleem alhoewel het binnen veel data-projecten wel regelmatig de kop op steekt. Er zijn complexe en minder complexe oplossingen voor gemaakt in diverse talen, maar gelukkig zijn er ook standaard componenten binnen databases aanwezig die dit probleem wellicht kunnen oplossen.

De meest generieke oplossing is soundex. Soundex is een functie die in bijna elke database wel geïmplementeerd is, o.a. in DB2, Oracle, MSSQL, PostreSQL, mySQL/MariaDB en SQLite. Wikipedia omschrijft het als volgt: “Soundex is een fonetisch algoritme voor het indexeren van namen of woorden naar hun uitspraak in de Engelse taal. Namen die gelijk klinken, maar mogelijk niet gelijk geschreven worden, krijgen eenzelfde soundexcode.“

De basis van soundex is ontwikkeld in 1917 voor kaartenbaksystemen. Na de introductie van computers begon het aan populariteit te winnen en later is het verder ontwikkeld. Het huidige systeem bestaat uit een code bestaande uit een letter en 3 cijfers, bijv. S123.

VOORNAAM ACHTERNAAM STRAAT SOUNDEX (STRAAT)
Jan Jansen Hoofdstraat H132
Jan Jansen Hoofstr. H132

Het grote voordeel is de eenvoud en de snelheid van dit systeem en de doeltreffendheid er van. Het nadeel is dat het voornamelijk gebaseerd is op (Engelse) uitspraak en daardoor erg afhankelijk is van het eerste karakter. Hierdoor gaat het niet goed in het voorbeeld van de voornaam.

VOORNAAM SOUNDEX (VOORNAAM)
Jozua J200
Yozua Y200

Voor veel toepassingen is soundex een doeltreffende methode om een groot deel van de data te matchen maar er moet wel rekening worden gehouden met de tekortkomingen van deze methode. De ene schrijffout heeft een grotere impact op de klank van een woord dan een andere schrijffout, het is echt “sounds like…”.

Edit-distance

Een andere manier is niet het analyseren op de klank maar hoeveel “gelijk” zijn twee velden, hoeveel “edits” moet ik maken aan string-1 om tot string-2 te komen?

Waar soundex één parameter nodig heeft om een soundexcode voor een woord te bepalen is het bij een edit-distance nodig om beide waarden te vergelijken en voor die situatie te bepalen hoeveel edits er nodig zijn om van 1 naar 2 te komen. Dit betekent ook een veel hogere belasting voor het systeem, elke vergelijking moet namelijk opnieuw bepaald worden.

Er zijn diverse methoden om een edit-distance tussen twee strings te berekenen, in dit voorbeeld nemen we de functies die in Oracle beschikbaar zijn: Levenshtein en Jaro-Winkler.

Vladimir Levenshtein

De Levenshtein-methode is in 1965 ontwikkeld door de Russische wetenschapper Vladimir Levenshtein. Het is kort samengevat het aantal toevoegingen / verwijderingen / vervangingen op string-1 om op string-2 uit te komen.

select S1, S2, utl_match.edit_distance(S1,S2) as levenshtein

from ( select 'Hoofdstraat' as S1, 'Hoofdstr.' as S2 from dual

       union all

       select 'Jozua' as S1, 'Yozua' as S2 from dual

     ) testdata

S1 S2 LEVENSHTEIN
Hoofstraat Hoofdstr. 3
Jozua Yozua 1

Deze meetwaarde heeft als voordeel dat de klank niet bepalend is voor de “gelijkheid” van twee strings maar geeft ook niet direct de gelijkheid tussen twee strings aan, omdat de lengte van de string ook erg bepalend is voor de gelijkheid. Een tekst van 1000 tekens en een edit-distance van 5 is meer gelijk dan een tekst van 5 tekens en een edit-distance van 4. In ons voorbeeld is de edit_distance tussen de adressen “3” en tussen de voornamen “1”, maar wat zegt deze waarde?

Om deze Levenshtein-waarde om te zetten in een “gelijkheid” is er in Oracle de zogenoemde edit_distance_similarity functie, die de lengte van de string meeneemt in de bepaling van gelijkheid. De output is een waarde tussen de 0 (geen gelijkenis) en 100 (volledig gelijk).

select S1, S2, utl_match.edit_distance_similarity(S1,S2) as levenshtein

from ( select 'Hoofdstraat' as S1, 'Hoofdstr.' as S2 from dual

       union all

       select 'Jozua' as S1, 'Yozua' as S2 from dual

     ) testdata

S1 S2 LEVENSHTEIN
Hoofdstraat Hoofdstr. 73
Jozua Yozua 80

Waar soundex een 100% match had op het adres en geen match had op de naam zien we nu dat het Levenshtein-algoritme de zaken omdraait. De naam is meer gelijk dan het adres en wij moeten bepalen welke mate van zekerheid acceptabel is. De mate van zekerheid is per situatie afhankelijk en moet door middel van experimenteren bepaald worden.

Jaro-Winkler

De laatste, en meest recente, methode die ondersteund wordt door een standaard Oracle systeem is de Jaro-Winkler. Deze methode heeft overeenkomsten met de Levenshtein-methode (in dat het een edit-distance tussen twee waarden is) maar heeft een voorkeur voor waarden die gelijk beginnen.

Waar de Levenshtein-methode als resultaat het aantal “edits” had die nodig zijn om van S1 naar S2 te komen, geeft de Jaro-Winkler een ‘gelijkheid’ tussen de twee waarden weer waarbij de waarde tussen de 0 (geen gelijkheid) en 1 (volledige gelijkheid) ligt. De _similarity toevoeging op deze functie geeft een waarde tussen de 0 (geen gelijkheid) en 100 (volledige gelijkheid). In deze situatie is dit slechts een andere representatie van dezelfde waarde, in tegenstelling tot bij de Levenshtein-methode.

select S1, S2, utl_match.jaro_winkler_similarity(S1,S2) as Jaro_Winkler

from ( select 'Hoofdstraat' as S1, 'Hoofdstr.' as S2 from dual

       union all

       select 'Jozua' as S1, 'Yozua' as S2 from dual

     ) testdata

S1 S2 JARO_WINKLER
Hoofdstraat Hoofdstr. 92
Jozua Yozua 86

Aangezien de Jaro-Winkler een voorkeur heeft voor strings die op dezelfde manier beginnen, heeft het adres nu een hogere gelijkheid. Net als bij het Levenshtein-algoritme moet ook bij het Jaro-Winkler-algoritme bepaald worden welke zekerheid acceptabel is.

Conclusie

We hebben 3 verschillende methoden voor fuzzy-matching bekeken die beschikbaar zijn binnen een Oracle database:

  • Soundex (Sounds Like)
  • Edit-distance : Levenshtein
  • Edit-distance : Jaro-Winkler

Alle drie deze methoden hebben duidelijke voor- en nadelen.

De soundex-waarde kan eenvoudig berekend worden en nieuwe waarden kunnen snel gematcht worden met reeds bestaande waarden, maar is wel erg afhankelijk van de Engelse uitspraak. Voor een eerste inventarisatie is deze methode wel erg handig, maar wees je bewust van de focus op uitspraak.

Als de analyse meer uit gaat naar gelijkheid op basis van karakters, zijn de methodes gebaseerd op een edit-distance een betere oplossing. Hierbij is de Jaro-Winkler methode meer gevoelig voor typefouten/gelijkheid aan het begin van de waarde (handig voor bijvoorbeeld adressen) en de Levenshtein is een meer algemene analyse van gelijkheid.

Voor alle analyses geldt dat er gekeken moet worden naar wat wenselijk is in de situatie en welke gelijkheid / zekerheid minimaal gewenst wordt voor automatisch matchen.

Reactie toevoegen

U kunt hier een reactie plaatsen. Ongepaste reacties worden niet geplaatst. Uw reactie mag maximaal 2000 karakters tellen.

* verplichte velden

Uw reactie mag maximaal 2000 karakters lang zijn.

Reacties

Er zijn nu geen reacties gepubliceerd.