Adressenbestand ontdubbelen? Probeer het eens met trigrammen (update).
Ieder bedrijf heeft er last van: Het bedrijfsbestand (relatiebestand, naw gegevens, adresgegevens, mailingbestand, klanten, prospects) groeit en op den duur is het bestand gevuld met relaties die dubbel voorkomen, maar net niet 100% hetzelfde. Een goede opschoonactie is dan soms noodzakelijk, bijvoorbeeld voordat de mailing de deur uitgaat. Ik heb zelf een aantal van dit soort trajecten doorlopen en hier soms software van derden gebruikt (bijvoorbeeld Human Inference). Maar hoe vind je nou die dubbelen zonder dit soort dure software en zonder het gehele bestand handmatig te moeten doorlopen?
Een antwoord kan zijn: met trigrammen.
Een trigram, wat is dat?
Vaak is de kwaliteit (juistheid, volledigheid en tijdigheid) van het adres- of de postcode-veld niet het probleem. Anders is het met de naam. Het gebeurt zelden dat de naam exact dubbel in het bestand voorkomt. Bijvoorbeeld in het bestand komt het bedrijf Pietje Puk B.V. 3 keer voor, als ‘Pietje Puk’, ‘Puk Pietje’ en ‘Firma Pietje Puk’.
Bij dit voorbeeld volstaat een eenvoudige query niet om deze dubbelen te vinden. Een methode om deze dubbelen mogelijk wel te vinden is het werken met trigrammen. Met trigrammen wordt een tekstveld geknipt in overlappende stukje van 3 letters.
Bedrijfsnaam 1: ‘Pietje puk’ wordt dan
pie|iet|etj|tje|je |e p| pu|puk|uk |k p| pi
Bedrijfsnaam 2: ‘Firma pietje puk’ wordt dan
fir|irm|rma|ma |a p| pi|pie|iet|etj|tje|je |
e p| pu|puk|uk |k f| fi
Bedrijfsnaam 3: ‘puk pietje’ wordt dan
puk|uk |k p| pi|pie|iet|etj|tje|je |e p| pu
In dit voorbeeld komen al 10 van de 11 trigrammen van de naam ‘pietje puk’ overeen met de naam ‘firma pietje puk’. Dit geeft aan dat er grote overeenkomst is tussen de namen. In dit geval zou je ook de vergelijking andersom nog moeten maken: 10 van de 17 trigrammen komen overeen. Dit laatste kan inhouden dat de naam ‘Firma pietje puk’ nog extra identificerende kenmerken heeft.
11 van de 11 trigrammen van de namen ‘pietje puk’ en ‘puk pietje’ komen overeen. Dit is dus een match!
10 van de 11 trigrammen van de namen ‘puk pietje’ en ‘firma pietje puk’ komen overeen. Andersom bekeken 10 van de 17. Hier is waarschijnlijk dus sprake van een overeenkomst, echter heeft 1 van de namen extra identificerende kenmerken.
Het gebruiken van trigrammen is wellicht niet DE oplossing maar zoals je kunt lezen brengt een oplossing al een heel stuk dichterbij. Eventueel heb ik voorbeelden in Excel, C# en VB.NET. Stuur maar even een mailtje.
januari 17th, 2009 at 17:05
Nog nooit van gehoord. Erg goed idee. Hoe kan ik deze methode implementeren?
januari 17th, 2009 at 17:44
@mike:
Er zijn natuurlijk heel veel methoden, maar je zou bijvoorbeeld in een aparte tabel een vingerafruk van een naam kunnen maken (1 record per trigram).
Een vingerafdruk van de naam bestaat dan uit meerdere records in deze aparte tabel.
Daarna is het een kwestie van de records in deze losse tabel met elkaar vergelijken en de overeenkomsten tellen. Het zou best kunnen dat dit in een een heleboel vergelijkingen gaat resulteren zodra het adressenbestand groot is, maar je komt wellicht al een stuk verder.
Ik zal daar binnenkort eens een stukje aan wagen.
oktober 22nd, 2009 at 17:16
Interessante optie, moeten wij ook eens proberen. Wij hebben nog wel wat aanvullende complicaties omdat we analyseren op KvK, BTW en Bankrekeningnummer. Soms wil je bijv Officenet maar met 1 adres voor heel Nederland vastleggen en soms heb je elke vestiging afzonder nodig in de administratie.
Het herkennen van dezelfde namen doen wij oa op basis van een SOUNDEX query. Heb je enige ervaring hoe dit zich verhoudt tot de trigrammen methode?
Arco @ YUKI.nl
februari 9th, 2010 at 19:24
[...] Tri-grammen kunnen voor verschillende doeleinden worden gebruikt. Al eerder schreef ik over het gebruiken van Tri-grammen bij het ontdubbelen van een relatiebestand. Tri-grammen kunnen ook worden gebruikt bij het bepalen van de taal van een stuk [...]
april 27th, 2010 at 19:41
Ik heb voorbeelden in Excel en in C# / VB.NET.
juni 7th, 2010 at 14:39
Ha Xander, dit lijkt me een reuze effectieve manier van ontdubbelen. Is het mogelijk dat u een voorbeeld van de werking ervan in excel ter beschikking kunt stellen?