Namensabgleich

Java-Forum Allgemeine Themen
1

Hallo zusammen,

ich stehe gerade vor der Herausforderung, Namen automatisiert auf Veränderung abgleichen zu müssen. Hintergrund ist, dass wir in einer Software einen Namen bereits hinterlegt haben und diesen mit einem neuen Wert abgleichen. Die Namen sollen, um fortfahren zu können, einander entsprechen. Kleiner Änderungen sollen aber erlaubt sein. Fokus liegt hier auf Buchstabendrehen, ausschreiben von Umlauten, Accents und andere Sprachspezifische Buchstaben. Einige Beispiele:

Müller == Müller
Mueller == Müller
Maier == Meier
Åkesson == Akesson
Schmitt =! Müller
Ling != Wong
Lucius =! Lukas
…

Im ersten Moment tendieren wir in Richtung, die Distanz mit Damerau-Levenshtein oder einem ähnlichen Vergleich zu ermitteln. Diese Distanz müsste man dann noch prozentual auf die Länge des Wortes umrechnen, um die Änderungen bei sehr langen oder sehr kurzen Namen ins Verhältnis zu setzen. Das würde aber dann auch bedeuten, dass ein Herr Wu, der eigentlich Wù heisst, 50% seines Namens geändert hätte…

Ich würde mal vermuten, dass wir nicht so einfach davon kommen sondern uns eine Lösung basteln müssen, die wir mit Buchstaben und Sequenzen füttern die wir für ähnlich halten, (also Å == A, ä == a == ae). Hat jemand schon mal sowas gemacht, oder kennt vielleicht eine elegante Lösung?

2

Da gibt’s sicher schon einiges, vielleicht auch vorgefertigt, und besser als alles, was man selbst so “naiv” hinschreiben würde. Aber … da du vermutlich selbst Googlen könntest, mache ich das jetzt mal ganz bewußt NICHT, sondern “brainstorme” etwas, und erwähne, dass man Bei Levenshtein zwar “klassisch” den Abstand um 1 erhöht, wenn eine Ersetzung/Einfügung/Löschung vorliegt, man das ja aber durchaus feiner ausdifferenzieren könnte:

  • Einfügung und Löschung: +1.0
  • “u” zu “x” vielleicht +0.9
  • “u” zu “ü” vielleicht nur +0.1
    …
3

wenn ‚Mueller == Müller‘ gleich sein soll, dann wäre allgemeines ‚Einfügen/ Löschen +1‘ ja nicht verwendbar,
u und ü sollen zudem nicht unbedingt gleich sein, nur ue und ü?

je nachdem, wie genau die Anforderungen auf einzelne Fälle eingrenzbar sind,
halte ich hier (auch nur laienhaft 10 sec. überlegt) nur das Prüfen dieser einzelnen manuell gewählten Gleichheiten für den richtigen Weg,

als Vorgehen zum Vergleich könnte man dabei Strings in Objekte zerlegen:


'Ödnisgärtner'   = Enum-Ö,groß  + 'dnisg'+ Enum-ä,klein + 'rtner'
'Oednisgaertner' = Enum-Ö,groß  + 'dnisg'+ Enum-ä,klein + 'rtner', also exakt gleicher Inhalt

zu jedem Enum sind die möglichen Varianten aufgezählt, falls eine davon im String gefunden wird, wird der Enum herausgezogen,
für groß/klein-Unterscheidung entweder simpel alles doppelt definieren, getrennte Enum-Werte, oder geschicktere Tricks und groß/klein nur ein boolean-Attribut jeweils

falls mal irgendwo ‚ue‘ nicht als ü gemeint sondern normal im Wort vorkommt, etwas ‚Mr. DasTueIchNicht‘,
dann wäre falsche Umwandlung nur zum Vergleich wohl verschmerzbar:
entweder andere Schreibweisen genauso, genauso umgewandelt, oder es liegt eben ein Unterschied vor,

Vergleich der geparsten Objekte ist dann Schauen nach Gleichheit aller Bestandteile hintereinander weg

edit:

also ‚Winter‘ = ‚Witner‘ zu erkennen und sonstige Schreibfehler wie ausgelassene/ zu viele Buchstaben, das wäre nun nicht mal normal abdeckbar,
und selbst für menschliche Gehirne in Einzelfällen eine Herausforderung, oft nicht eindeutig bewertbar,

wenn noch weitere Informationen wie gleiche Adresse dazu vorliegt, ok, dann kann man eher entscheiden was Dreher, was potentiell ganz unterschiedlich ist,

da bräuchte es dann aber sicher die allgemeinen Mechanismen für Ähnlichkeit von Wörtern,
vielleicht ergänzt um irgendwas, das ‚ue‘ vs. ‚ü‘ weniger dramatisch sieht als andere zusätzliche/ weggelassene Buchstaben usw.

es sollte fertiges geben, aber ich habe nichts zu nennen/ zu empfehlen

4

Bei solchen Phonetiken wird es immer unscharfe Bereiche geben und unschöne Fälle, die fälschlich zusammengeworfen werden und solche, die es nicht werden, bei denen man sich das aber wünscht.

Wir haben auch mal eine solche zusammengebastelt für einen Anwendungsfall. Die kann ich dir aber leider nicht einfach weitergeben. Und es wäre ja auch fraglich, ob sie zu deinem Problem dann passen würde.

5

Schon mal danke für eure Antworten.

Ich habe jetzt letzte Woche ein paar Paper gelesen, und mir hat nicht so wirklich gefallen was ich gefunden habe. Unter dem Strich scheinen phonetische Algorithmen das beste Ergebnis zu liefern, diese konzentrieren sich aber meistens auf eine Sprache. Es gibt welche für Franzosen, welche für Engländer, welche für jüdische Namen… (was ja für SOUNDex Algorithmen niemanden wundern sollte…). Alles was übergreifend ist ist entweder Fehleranfällig oder hat sehr schwache Erkennungsraten.

Buchstabendreher sollte der Damerau-Levenshtein ja eigentlich hinbekommen (dafür wurde er gemacht), alles andere wird wirklich schwierig zuverlässig hinzubekommen. Da werden wir im ersten Schritt mal die Erwartungen unserer Fachseite dämpfen müssen.

Wenn ich etwas konkreteres finde werde ich hier noch mal Feedback geben.

6

Was man noch machen könnte, wenn einigermassen Datenbasis vorhanden ist mit Machine Learning, künstlicher Intelligenz rangehen. Neuronales Netz anlegen und lernen lassen. Wird allerdings wohl den Rahmen sprengen, den die Fachseite für solche Geschichten üblicherweise zur Verfügung stellt.

Allerdings wäre das Ergebnis interessant oder zumindest wäre es interessant zu wissen ob das auch funktioniert und was die besten Metriken dafür sind.

7

Der Gedanke kam uns auch schon, aber deine Vermutung über den finanziellen Rahmen ist korrekt. :wink:

8

Vielleicht https://de.wikipedia.org/wiki/Kölner_Phonetik ?

9

Danke, den kann ich auch mal der Sammlung hinzufügen. Der ist natürlich auch auf Deutschland beschränkt, der Kunde möchte natürlich einen Algorithmus der Europaweit funktioniert… :wink: :expressionless:

Vielleicht werde ich einfach mal ein paar Sprachspezifische (Kölner Phonetix, Soundex, Henry, Daitch-Mokotoff, Metaphone, etc. implementieren und eine Mischung aus Namen mit Mutationen dagegen laufen lassen. Vielleicht kann man es ja auch geschickt kombinieren (Erst Kölner Phonetik, wenn dieser nichts findet → Metaphone, usw.).

Zum Thema noch, was ich gefunden habe:
http://homepages.cs.ncl.ac.uk/brian.randell/Genealogy/NameMatching.pdf
http://waset.org/publications/8664/a-comparison-and-analysis-of-name-matching-algorithms-