Algorithmus zum Gruppieren Namen

Question

Was diese Liste mit den Namen der Gruppe ein guter Weg ist:

Doctor Watson. 
Dr. John Watson. 
Dr. J Watson. 
Watson. 
J Watson. 
Sherlock. 
Mr. Holmes. 
S Holmes. 
Holmes. 
Sherlock Holmes. 

In einer gruppierten Liste der einzigartigen und vollständigen Namen:

Dr. John Watson. 
Mr. Sherlock Holmes. 

Auch interessant:

Mr Watson 
Watson 
Mrs Watson 
Watson 
John Watson 

Da der Algorithmus keine Rückschlüsse darauf machen muss, ob der erste Watson ein Mr (wahrscheinlich) oder eine Frau ist, sondern nur die Gruppe th Das einzige Problem ist, dass John Watson offensichtlich Mrs und nicht Mrs. Watson gehört. Ohne ein Wörterbuch mit Vornamen für jedes Geschlecht kann dies nicht abgeleitet werden.

Bis jetzt habe ich darüber nachgedacht, durch die Liste zu gehen und jedes Element mit den restlichen Elementen zu überprüfen. Bei jedem Match gruppierst du und beginnst von vorne, und beim ersten Durchgang, wo keine Gruppierung stattfindet, hörst du auf.

Hier ist ein paar grobe (und noch nicht getestete) Python. Sie würden es mit einer Liste von Namen nennen.

def groupedNames(ns): 
    if len(ns) > 1: 
     # First item is query, rest are target names to try matching 
     q = ns[0] 
     # For storing unmatched names, passed on later 
     unmatched = [] 
     for i in range(1,len(ns)): 
      t = ts[i] 
      if areMatchingNames(q,t): 
       # groupNames() groups two names into one, retaining all info 
       return groupedNames([groupNames(q,t)] + unmatched + ns[i+1:]) 
      else: 
       unmatched.append(t) 
    # When matching is finished 
    return ns 

Answer 1

Wenn Ihre Namen immer von der Form [honorific][first name or initial]LastName sind, dann können Sie durch Extrahieren und Sortierung nach dem Nachnamen beginnen. Wenn einige Namen das Format LastName[,[honorific][first name or initial]] haben, können Sie sie analysieren und in das erste Formular konvertieren. Oder Sie möchten vielleicht alles in eine andere Form konvertieren.

In jedem Fall legen Sie die Namen in eine kanonische Form und sortieren dann nach Nachnamen. Ihr Problem ist stark reduziert. Sie können dann nach Vornamen und Ehrentiteln in einer Nachnamengruppe sortieren und dann nacheinander durch sie gehen, um die vollständigen Namen aus den Fragmenten zu extrahieren.

Wie Sie bemerkt haben, gibt es einige Unklarheiten, die Sie lösen müssen. Zum Beispiel könnten Sie haben:

John Watson 
Jane Watson 
Dr. J. Watson 

Es gibt nicht genügend Informationen, um zu sagen, welche der beiden (wenn auch nicht!) Ist der Arzt. Und, wie Sie darauf hingewiesen haben, ohne Informationen über das Geschlecht der Namen, können Sie Mr. J. Watson oder Mrs. J. Watson nicht auflösen.

Answer 2

Ich empfehle die Verwendung von Hashing hier. Definieren Sie eine Hash-Funktion als interpretieren Sie den Namen als Basis 26 Nummer, wobei a = 0 und z = 25 Jetzt nur die einzelnen Wörter Hash. Also

h (Sherlock Holmes) = h (Sherlock) + h (Holmes) = h (Holmes) + h (Sherlock).

diese verwenden Sie können leicht erkennen Namen wie:

John Watson und Watson John

Für Zweideutigkeiten wie Dr. John Watson und Herrn John Watson Sie können den Hash-Wert für Herrn und Dr definieren die sein gleich.

Um Konflikte wie J. Watson und John Watson zu lösen, können Sie nur den ersten Buchstaben und den Nachnamen hashed haben. Sie können die Idee für ähnliche Konflikte erweitern.