Forum: PC-Programmierung Adresseabgleich - gute Vorgehensweise gesucht


von Frank L. (Firma: Flk Consulting UG) (flk)


Lesenswert?

Hallo Zusammen,

ich habe hier gerade das Problem, dass ich Adressdaten per XML in mein 
System einlesen muss. In den XML-Daten befindet sich pro Adresssatz kein 
eindeutiges Merkmal das ich als Referenz verwenden kann.

Hintergund: Es handelt sich um eine SharePoint 2016 Liste. Die 
Verarbeitung erfolgt über eine Metasprache im Hintergrund auf dem 
Server. Der Sprachumfang der Metasprache ist gegenüber C# stark 
eingeschränkt.

Als identifiziere Merkmale werden:

1. Vorname
2. Nachname
3. PLZ
4. Ort
5. Straße
6. Hausnummer

übergeben und auch gespeichert. Es gibt noch weitere Merkmale die nicht 
zur Identifikation herangezogen werden können bei einem Update aber 
geändert werden müssen.

Bei der initialen Befüllung der Liste bilde ich über alle 6 Merkmale 
einen MD5HASH. Mit diesem versuche ich zuerst den Datensatz in meiner 
Liste zu finden.

Finde ich den Datensatz nicht, will ich im nächsten Schritt die Menge 
soweit wie möglich eingrenzen um anschließend die resultierende 
Treffermenge mit einem Damerau-Levenshtein-Distance-Algorithm zu 
bewerten und je nach Bewertung einer manuellen Zuordnung zuzuordnen.

Die Frage ist also, in welcher Reihenfolge würdet Ihr welche Attribute 
gegen die Liste prüfen um möglichst schnell möglichst wenig erste 
Treffer für die Bewertung mit Damerau-Levenshtein-Distance-Algorithm zu 
bekommen?

Wichtig: Im Prinzip, dass jedes Merkmal zum Original verändert sein.

Gruß
Frank

: Bearbeitet durch User
von O(n²) (Gast)


Lesenswert?

Wieviele Datensätze sind es, wie oft läuft der Vergleich, lohnt der 
Aufwand überhaupt?

xx Stunden Programmieraufwand gegen 5 Minuten Laufzeitersparnis?

Kannst du zusätzliche Indices anlegen, Trigramme?

von Oliver S. (oliverso)


Lesenswert?

Frank L. schrieb:
> Wichtig: Im Prinzip, dass jedes Merkmal zum Original verändert sein.

Der Satz scheint für das ganze Problem eminent wichtig zu sein. Nur, was 
soll er uns sagen?

Oliver

von Oliver S. (oliverso)


Lesenswert?

Wenn da jedes Merkmal gegenüber dem Original verändert sein kann, was 
bedeutet das?
Tippfehler, oder Heinz Müller ist umgezogen (damit änder sich alle 
Adressmerkmale) und hat dazu geheiratet und heisst jetzt Heinz Meier? Da 
wirds dann schwierig...

Oliver

von O(n²) (Gast)


Lesenswert?

Oliver S. schrieb:
> Der Satz scheint für das ganze Problem eminent wichtig zu sein. Nur, was
> soll er uns sagen?

Dass er nicht einfach alle Datensätze mit Stadt="Hamburg" zum Vergleich 
ziehen kann, weil auch "Habmurg" drinnen stehen könnte.

er sucht, soweit ich verstanden habe, einen möglichst effizienten 
Vor-Filter, damit er seine Edit-Distance nur für möglichst wenige 
Datensätze berechnen muss.

Dazu kann man z.B. die Wörter in Trigramme/Trigraphen zerlegen 
("Hamburg" -> "H","HA","HAM","AMB","MBU","BUR","URG","RG","G")

Dann für alle vorkommenden (Unicode/sonderzeichen vorher wegfiltern/auf 
Sonder-Symbol mappen) Bitlisten/Indices anlegen, abspeichern.

Für das Suchwort "Habmurg" genau so -> Bitlisten vergleichen.

Hätte im Beispiel dann 6 von 9 möglichen Treffern -> Wäre ein Kandidat 
zum weiteren vergleichen.

ist allerdings eine etwas andere Metrik als die Edit-Distance. Vgl. 
"Hammburg" z.B.

von Frank L. (Firma: Flk Consulting UG) (flk)


Lesenswert?

Hallo Zusammen,
ich war leider unterwegs und konnte den Thread nicht direkt 
mitverfolgen.

Sorry, wenn ich mich unklar ausgedrückt habe. Ja, ich suche einen 
Vorfilter mit dem ich den Abgleich verkürzen kann.

Wir reden insgesamt über ca. 10.000 Listitem in einer SharePoint Liste.
Als Abfragesprache steht mir nur die Interation über alle ListItem oder 
eine CAML Abfrage zur Verfügung um eine erste Einschränkung vorzunehmen.

Bitmuster entfallen komplett, da ich keine Möglichkeit in der mir zur 
Verfügung stehen Metasprache diese zu erstellen.

Ich kann also nur durch Kombinationen der Merkmale verschiedene Suchen 
über eine CAML Query absetzen und die Ergebnisse in einer JSON Struktur 
sammeln und später vergleichen.

Ziel ist es mit möglichst wenig CAML Abfragen eine möglichst kleine 
Treffermenge zu erhalten, die anschließend durch den 
Damerau-Levenshtein-Distance-Algorithm gejagt werden um die Treffermenge 
weiter zu reduzieren.

Alle die mit einer Distanz von 1 und 2 und nur einmal vorkommen, können 
ohne weitere Sichtung direkt geändert werden. Bei mehrfachen Vorkommen 
einer 1 oder 2 bzw. ab einer Distanz von drei, muss der Anwender manuell 
im Nachgang eine Zuordnung vornehmen. Hier bei werden Ihm die möglichen 
Kandidaten vorgeschlagen.

Das Problem ist also die Treffermenge des Vorfilters so genau und so 
klein wie möglich zu halten.

Gruß
Frank

von Dick Boutsos (Gast)


Lesenswert?

Wieso importierst du das nicht in eine sql-db?
Dann kannst du bequem suchen und musst nicht mit so Krücken wie 
Leveinsteindistanz, MD5-Hashes rumorgeln oder warum geht das nicht?

von Sheeva P. (sheevaplug)


Lesenswert?

Dick Boutsos schrieb:
> Wieso importierst du das nicht in eine sql-db?

Guter Ansatz, aber leider sind die Scoringfunktionen aller mir bekannten 
SQL-Datenbanken ziemlich schlecht. Warum dann nicht gleich in eine 
Datenbank, die speziell für sowas gemacht ist, nämlich eine Suchmaschine 
wie Elasticsearch? Das kann Damerau-Levenshtein, Phonetik und n-Gramme, 
mit Synonymersetzungen etc., bietet ein ordentliches Scoring und sind 
dank seines internen Columnar Stores auch schneller als jede 
SQL-Datenbank. Klar, das kostet Einarbeitung, aber sicher weniger als 
Eigenbau-Lösung -- und die Ergebnisse werden besser sein als bei einer 
SQL-DB.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.