Personen mit ähnlichen Merkmalen finden

[Oneixee5]

Ich habe eine DB mit etwa 400T Personen je Zeitraum, welche immer eine Zuordnung zu einem oder mehreren Zeiträumen haben. Normalerweise ist es gar nicht so einfach Personen anzulegen oder gar doppelt anzulegen, da die Personen aus anderen Systemen übermittelt werden. Ausnahmen sind z.B.: Migranten oder Einwanderer. Da Sachbearbeiter nicht immer ganz so korrekt oder motiviert vorgehen, kommt es trotzdem vor, das Personen doppelt in einem Zeitraum angelegt werden. In dem System soll nun nach solchen Klonen gesucht werden. Natürlich sollen mögliche Schreibfehler mit in den Vergleich einbezogen werden. Merkmale sind: Name, Geburtsname, Vorname, Geburtsdatum. Ich habe versucht die Angaben nach Ähnlichkeit zu gewichten und benutze dazu die Levenshtein-Distanz. Mit dem Resultat bin ich soweit zufrieden. Das Problem ist, dass ich hier ein Kreuzprodukt benötige und Jeden mit Allem vergleichen muss. Das dauert natürlich sehr lange. Ich komme in einer Oracle Exadata auf über 40 Minuten. Ich suche nach einer schnelleren Möglichkeit, am Besten ohne Kreuzprodukt. Wie kann man da herangehen? Ich bin dabei nicht auf die DB beschränkt, die Technologie ist dabei erst mal zweitrangig.

 

[httpdigest]

Um aus der Komplexitätsklasse n^2 auszubrechen, brauchst du irgendeine Art von Indexierung auf "ähnlichen" Namen, also eine Funktion f(x) die einer Person (oder einem Namen) einen Wert zuordnet, so dass zwei "ähnliche" Namen denselben Wert zuordnet bekommen.
Die Schwierigkeit hierbei liegt im Finden einer solchen Indexierungsfunktion.

Ein Beispiel für solche ein Funktion ist etwa folgende:
Angenommen, du hast die beiden Nachnamen "Mustermann" und "Mostermann". Um beide zu indexieren, können wir zuerst einmal für jeden Buchstaben in dem Wort ein neues Wort bilden, bei dem wir schrittweise immer ein Zeichen durch ein anderes Zeichen ersetzen, welches sonst nicht vorkommt (wir verwenden hier das Zeichen '?'):
"?ustermann", "M?stermann", "Mu?termann", und so weiter. Sowie: "?ostermann", "M?stermann", "Mo?termann", etc.
Wir haben also zwei Gruppen von Namen generiert für unsere Ausgangsnamen.
Für jeden dieser generierten Namen verwenden wir jetzt eine einfache Indexfunktion wie etwa den Hashwert auf Strings.
Es fällt auf, dass die beiden generierten Namen "M?stermann" identisch sind und das könnte erstmal ein Indiz dafür sein, dass hier quasi derselbe Name gemeint waren. Das entspräche in diesem Fall einer Levenshtein-Distanz von 1.

Jetzt bildest du einfach einmal aus allen Namen aller Personen diese Gruppierung und Indexierung und prüfst, welche Gruppen am Ende mehr als einen Eintrag enthalten.

Die Indexfunktion hängt also ganz maßgeblich von der gewünschten Ähnlichkeit der Personen ab, da sie diese quasi implizit abbildet. Du brauchst/musst also nicht mehr tatsächlich die Levenshtein-Distanz jeweils zweier Namen berechnen, sondern baust eine Indexierung, die darauf basiert.

 

[Oneixee5]

Der Ansatz des Index ist nicht schlecht. Ich habe mir das so ähnlich überlegt. Allerdings bildet das nicht die unterschiedliche Längen der Namen ab. Ich habe Zweifel, wenn man beginnt das System jetzt noch auf Buchstabengruppen auszuweiten, dann dürfte ein gigantischer Index entstehen. Die Datenmenge und der Aufwand schrecken mich etwas ab. Ich habe auch noch keine Vorstellung wie lange die Erstellung des Index benötigen würde. Ich fürchte der Indexierungsprozess müsste pausenlos laufen. Es müssen ja auch noch mehrere Zeiträume separat untersucht werden, was den Index noch größer macht.
Ich hatte gehofft, man könnte so etwas wie die Distanz zu einen Standardwert errechnen und damit herausfinden ob ein anderer Name sehr ähnlich ist, weil dieser die (fast) gleiche Distanz erzeugt.

 

[httpdigest]

Was meinst du mit unterschiedliche Längen der Namen? Wenn du z.B. "Musterman" und "Mustermann" hast, dann kannst du natürlich noch so viele künstliche Namen aus "Musterman" machen, dass du ähnliche andere Namen mitnimmst. Also "Musterman" könnte dann noch den Namen "Musterman?" (also ein ? als Suffix) generieren und somit wäre es dann wieder ähnlich zu "Mustermann" als "Musterman?" (letztes 'n' generiert ?).
Und viele Suffixe oder gar Präfixe musst du ja gar nicht generieren. Also "Mann" und "Mustermann" sollen ja nicht wirklich gleich sein.

Aber: Nicht abschrecken lassen, einfach machen und gucken.
In-memory sind 400.000 Einträge gar nichts.

 

[httpdigest]

Hier einmal kurz zusammengeschrieben, was ich meine (hab's mal mit der Liste https://www.usna.edu/Users/cs/roche/courses/s15si335/proj1/files.php?f=names.txt.html ausprobiert):

Spoiler

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Stream;
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.concat;
public class Names {
  private static class Pair {
    final String original;
    final String index;
    Pair(String original, String index) {
      this.original = original;
      this.index = index;
    }
  }
  // "Max" -> ["?ax", "M?x", "Ma?"]
  private static Stream<Pair> replace(String str) {
    return range(0, str.length())
            .mapToObj(i -> new Pair(str, str.substring(0, i) + "?" + str.substring(i + 1)));
  }
  // "Max" -> ["?Max", "M?ax", "Ma?x", "Max?"]
  private static Stream<Pair> intersperse(String str) {
    return range(0, str.length() + 1)
            .mapToObj(i -> new Pair(str, str.substring(0, i) + "?" + str.substring(i)));
  }
  public static void main(String[] args) throws Exception {
    String fileName = "names.txt";
    Map<String, String> names = new HashMap<>();
    try (Stream<String> lines = Files.lines(Paths.get(fileName))) {
      lines.flatMap(line -> concat(replace(line), intersperse(line)))
            .forEach(pair -> {
              String similar = names.put(pair.index, pair.original);
              if (similar != null) {
                System.out.println(pair.original + " is similar to " + similar);
              }
            });
    }
}

 

[LimDul]

Evtl. hilft schon (da du Oracle erwähnt hast): https://docs.oracle.com/cd/B19306_01/server.102/b14200/functions148.htm

 

[Oneixee5]

Evtl. hilft schon (da du Oracle erwähnt hast): https://docs.oracle.com/cd/B19306_01/server.102/b14200/functions148.htm

Soundex funktioniert leider nur für englische Namen gut. Für arabische und asiatische Namen sind die Ergebnisse oft nicht brauchbar. Suchfunktionen mit Soundex hat der Kunde schon vor mehreren Jahren abgelehnt.
In dem Zusammenhang habe ich noch folgendes gefunden: https://github.com/deezaster/germanphonetic