mikrocontroller.net

Forum: PC-Programmierung Adresseabgleich - gute Vorgehensweise gesucht


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Frank L. (Firma: Flk Consulting UG) (flk)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
1 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.