Back to top

Die einzigartigen Herausforderungen bei der Suche nach Namen

Oder: Wie man eine generische Suchmaschine in eine Verzeichnissuche von Weltklasse umwandelt

 

Ich war in letzter Zeit an einigen Projekten beteiligt, in denen mehrere Namenslisten durchsucht werden mussten. Daher habe ich mir einige Gedanken über die besonderen Probleme gemacht, die bei der Suche nach Namen auftreten.

Die Menschen lieben Listen, Listen von Dingen, vor allem Listen von Namen (oder "Verzeichnisse") sind in unserer Gesellschaft sehr verbreitet. Wir haben Listen von Fernsehsendungen, Filmen, Terroristen, Erfindern, Unternehmen und dergleichen mehr. Es ist klar, dass Suchvorgänge in solchen Listen in vielen Anwendungen von kritischer Bedeutung sind, in manchen Fällen haben sie sogar eine kritische Bedeutung für die ganze Gesellschaft.

 

Warum die Suche in Dokumenten anders ist als die Suche nach Namen

Standard-Suchmaschinen sind so entworfen, dass sie Dokumente durchsuchen, nicht Namenslisten. Die beiden Arten der Quellen unterscheiden sich stark. Ich verzweifle oft, wenn Anbieter von Standard-Suchmaschinen anfangen, von Verzeichnisdiensten zu reden.

Zunächst muss man bedenken, dass Dokumente einiges größer sind – und in diesem Fall ist Größe von Bedeutung. In Dokumenten findet man deutlich mehr Informationen, daher sind die TF-IDF-Statistiken (Term Frequency – Inverse Document Frequency, Vorkommenshäufigkeit – inverse Dokumenthäufigkeit, ein verlässliches Rankingkriterium für viele Suchmaschinen) für Dokumente viel zuverlässiger als für Namenslisten.  Weiterhin bietet ein Dokument mehr Möglichkeiten, der Abfrage des Benutzers zu entsprechen als ein Name. So können beispielsweise Tippfehler im Dokument (anders als ein Fehler in der Abfrage, das ist eine andere Sache) vernachlässigt werden, da ein einzelnes Wort im Dokument nur einen kleinen Teil der verfügbaren Daten darstellt.

Bei Namenssuchen ist das ganz anders. Ein einzelner Tippfehler in einer Namensdatenbank kann einen großen Teil des durchsuchbaren Contents verfälschen (wenn nicht sogar den gesamten). Man muss sich nur einmal vorstellen, wenn mehr als die Hälfte der Wörter eines Dokuments falsch geschrieben wären. Wie sollte eine Suchanwendung damit noch klarkommen?

Auf gleiche Art behindert auch die Statistik für Suchmaschinen (die oben genannte TF-IDF) die Namenssuche. Bei Suchen in einem Dokument geht man davon aus, dass sehr häufig auftretende Wörter, wie zum Beispiel das Wort "sehr", eher unwichtig sind, weil sie so oft auf unterschiedliche Art verwendet werden. Bei der Namenssuche ist das natürlich anders. Jedes Wort zählt. Selbst wenn zum Beispiel "Peter" sehr häufig in der Namensdatenbank vorkommt, ist der Name immer noch genauso wichtig wie zum Beispiel "Rajeev", da beide Wörter gleichwertige Wiedergaben von Vornamen sind.

Wir Menschen besprechen die Dinge gerne, und wenn etwas im Gespräch häufig vorkommt, verwenden wir meist Abkürzungen, um die Kommunikation zu erleichtern. Wie lange es wohl gedauert hat, bis aus der "International Business Machines Corporation" einfach nur "IBM" wurde? Oder aus "Federal Express" kurz "FedEx"?  Wahrscheinlich nur eine Stunde oder zwei.  Unsere Vorliebe für Abkürzungen beschränkt sich aber nicht nur auf Unternehmensnamen. Wir kürzen Genres ab (Sitcom, Sci-Fi), Namen von Menschen oder Gruppen ("Hape" Kerkeling, CDU, SPD), und Vornamen werden so oft abgekürzt, dass man die Abkürzungen schon als eigenständige Namen erkennt (Ben, Lisa, Chris, Alex). Wir kürzen Namen von Filmen ab (ST-TNG, LOTR), technische Formate (CD, HD), Fernsehserien (DSDS, HIMYM, GZSZ) und vieles mehr. Namen, die Abkürzungen enthalten, können oft von Suchfunktionen nicht mehr gefunden werden, sofern nicht angemessene Maßnahmen zur Handhabung solcher Ausnahmen in den Systementwurf aufgenommen wurden.

Man sollte auch beachten, dass Namen viel mehr von ihrer Position abhängig sind als Dokumente. In der Regel sind Wörter am Anfang eines normalen Dokuments (ausgenommen dem Titel) etwas wichtiger als Wörter in den hinteren Abschnitten. Der Unterschied ist jedoch nicht sehr groß und hängt oft von der Art der Suche ab. In manchen Situationen können die Wörter am Anfang des Textes sogar weniger bedeutend sein als jene im Rest des Textes.

Bei Namen ist das ganz anders, die Position ist hier sehr wichtig. Vor allem bei Firmennamen ist das erste Wort (FedEx, Staples, Walmart) viel wichtiger als der Zusatz am Ende (Inc., GmbH, Limited usw.). Ebenso verhält es sich bei Personennamen, wenn man den Nachnamen vor dem Vornamen schreibt.

Die Bedeutung der Position erstreckt sich auch auf teilweise Treffer. Die meisten Menschen erinnern sich besser an den Anfang eines Namens als an das Ende. Wenn man zum Beispiel jemand mit Namen "Hammarskjöld" trifft, wird man sich eher an das "Hammar" erinnern als an das "Skjöld".

Und schließlich sind Suchergebnisse, die mehr auf den Anfang eines Namens achten, "sinnvoller" für den Benutzer, als Ergebnisse, die sich auf den ganzen Namen konzentrieren. Wenn ein Benutzer also nach "Star" sucht, hofft er meist eher, Ergebnisse wie "Star Wars", "Star Trek" und "A Star is born" zu finden als Ergebnisse wie "Lone Star", "Pawn Stars" oder "Survivor All Stars".

 

Alchemie:  Wie man eine generische Suchmaschine in eine Verzeichnissuche von Weltklasse umwandelt

Ich finde das Wort "Alchemie" hier sehr passend, weil es schon etwas von Magie hat, eine wirklich gute Verzeichnissuche für Namen zu erschaffen. Dank Google ist die Welt inzwischen an einen gewissen Standard bei Suchergebnissen gewöhnt. Man gibt zum Beispiel einen Namen wie "Gerd Schröder" ein und bekommt auch Ergebnisse für "Gerhard Schröder". Oder man gibt eine scheinbar wahllose Zeichenfolge wie "desp ho" ein und bekommt Suchergebnisse für "Desperate Housewifes". Die erste Reaktion ist meist: “Wow! Wie haben die das bloß hinbekommen?"

Wir bei Search Technologies lieben Transparenz und überlassen die Relevanzbewertung nicht dem Zufall. Damit meine ich, dass wir nicht einfach nur der Suchmaschine Namen füttern und die Fuzzy-Funktion einschalten. Wir lassen lieber die Art der Treffer in Kategorien einordnen und stellen sicher, dass jede Art Dokumente liefert, ehe sie kombiniert werden. Jede Kategorie wird dabei auf Exaktheit geprüft und dann gewichtet und mit anderen Kategorien kombiniert, um die vollständige Suche zu erstellen.

Daher passt der Begriff Alchemie sehr gut – wir mischen die verschiedenen Technologien in unterschiedlichen Konzentrationen und Kombinationen, um die ideale Verzeichnissuche für Namen zu erschaffen. 

 

Vor dem Anfang

Die im Folgenden beschriebenen Techniken erfordern einige Standardfunktionen, die in den meisten modernen Suchmaschinen vorhanden sind. Insbesondere:

  • Gewichtung von Abfragebegriffen:  Hierdurch können Begriffe, Ausdrücke und Begriffsgruppen innerhalb der Abfrage individuell gewichtet werden
  • Zugang zur Indexierungspipeline:  Dieser ist erforderlich, um Namen zu manipulieren und zu "überindexieren", ehe sie an den Indexer weitergeleitet werden. Man kann dies aber auch erreichen, indem man ein externes Framework für die Dokumentverarbeitung verwendet
  • 1 zu N Dokumentindexierung:  Eine Funktion des Indexierens, über die ein einzelnes Input-Dokument zu mehreren Einträgen im Suchindex wird. Auch dies wird meist am besten durch ein externes Framework für die Dokumentverarbeitung erreicht, welches die Daten vor dem Indexieren vorbereitet
  • Field Collapsing:  Wenn eine 1 zu N Dokumentindexierung vorgenommen wird, braucht man die Funktion Field Collapsing, um zu verhindern, dass dem Benutzer mehrere Versionen desselben Namens geliefert werden
  • Gewichtung von Dokumenten und Feldern: Hierdurch kann die Popularität von Dokumenten in den Algorithmus zur Relevanzbewertung einbezogen werden, sodass unklare Suchen die beliebteste Version als erstes Ergebnis liefern

Bietet Ihre Suchmaschine all diese Funktionen? Viele der führenden Suchmaschinen haben alles, was wir brauchen. Aber wissen Sie auch, wie sie sie einsetzen? Fantastisch! Dann kann es ja losgehen.

 

Treffer #1:  Exakte Treffer

Welche Arten von Treffern gibt es also? Als erstes natürlich den exakten Treffer. Wenn der Benutzer den genauen Namen eingibt, sollte der passende Treffer ausgegeben werden. Wenn zum Beispiel "Krieg der Sterne" eingegeben wird, sollte " Krieg der Sterne " ausgegeben werden, erst danach " Krieg der Sterne Retrospektive" oder "Krieg der Planeten, Teil 3: Held der Sterne”. Ebenso ist "Hermann Lara" eine komplett andere Person als "Lara Hermann".

 

Treffer #2:  Verschiedene Kombinationen des gleichen Begriffs

Die nächste Trefferart ist eine Variation der Begriffe, die dem Namen am nächsten kommt. Im Prinzip müssen alle Suchbegriffe im Namen vorkommen, sie dürfen aber in anderer Reihenfolge auftauchen, oder dürfen um weitere Wörter ergänzt sein usw. Diese Art kann weiter unterteilt werden, zum Beispiel bevorzugen wir Namen, deren Präfix zu der Abfrage des Benutzers passt vor anderen Ergebnissen. Ebenso bevorzugen wir Namen mit weniger zusätzlichen Begriffen (dies wird oft von der Suchmaschine automatisch geregelt, durch die Statistik zur Frequenz der Begriffe).

 

Treffer #3:  Substitution gebräuchlicher Synonyme

Die dritte Trefferart erweitert die Namen um angemessene Synonyme. So wird zum Beispiel "Pete" zu "Peter" oder "Co" zu "Company". Für fast alle Namensarten gibt es solche häufigen Abkürzungen, daher kann ein standardmäßiges Synonym-Wörterbuch (entweder während des Indexierens auf das Dokument angewandt, oder als Erweiterung der Abfrage) die Ergebnisse substanziell verbessern.

Man muss allerdings aufpassen, dass der ursprüngliche Begriff wo immer möglich bevorzugt behandelt werden sollte. So ist zum Beispiel der Name "Willy Brandt" so gebräuchlich, dass niemand daran denken würde, ihn "Wilhelm Brandt" zu nennen.

 

Kommentar:  Rechtschreibprüfung

Die meisten Suchmaschinen bieten eine Form der Rechtschreibprüfung, zumindest für die Benutzereingabe. Diese funktioniert meist, indem sie die Frequenz der Verwendung der Abfragebegriffe in der Datenbank überprüft. Wenn der Benutzer einen seltenen Begriff eingegeben hat und ein anderer Begriff mit minimal abweichender Schreibweise beliebt ist, wird das System automatisch den beliebteren Begriff vorschlagen (üblicherweise mit einem "Meinten Sie ...?").

Leider können die Algorithmen zur Rechtschreibprüfung aus mehreren Gründen nicht wirklich bei der Namenssuche weiterhelfen. Als erstes arbeiten diese gegen das Prinzip der Suche nach allen Möglichkeiten. Anders ausgedrückt, manchmal sucht man eben gezielt nach diesen seltenen Fällen, diese können also durchaus wichtig sein – für den Benutzer oder den Anbieter der Datenbank.

Und vielleicht am wichtigsten, die Rechtschreibprüfung der Abfrage hilft nicht bei verschiedenen Schreibweisen im Dokument. Wenn ein Name teilweise falsch geschrieben ist, kann der Name von der Suche nicht mehr erfasst werden. Die Rechtschreibprüfung wird dem Benutzer nie einen falsch geschriebenen Begriff vorschlagen, also können falsch geschriebene Namen auch nicht gefunden werden.

Daher muss die Rechtschreibprüfung beim Indexieren angewandt werden, um sicherzustellen, dass die Informationen in den Dokumenten verfügbar sind. Manchmal kann dies erreicht werden, aber 1) sind diese Algorithmen meist zu langsam, um sie während des Indexierens einzusetzen, und 2) leiden sie unter dem "Fluch des Indexierens in zwei Durchgängen". Anders ausgedrückt, man weiß meist erst, wie ein Wort korrekt geschrieben wird, wenn alle Namen indexiert wurden – und dann ist es schon zu spät, außer, wenn man einen Algorithmus einsetzt, der in zwei Durchgängen indexiert.

 

Treffer #4:  Abgleich von Teiltreffern

Statt einer Rechtschreibprüfung empfehlen wir daher einen Abgleich von Teiltreffern. Diese Technik bezeichnet man auch als "Fuzzy Spelling" oder "N-Gramm-Suche".

Hier nutzen wir die meist eher geringe Größe der Namen aus. Oft ist ein Begriff nur 10 bis 50 Zeichen lang, was im Vergleich zu ganzen Dokumenten wirklich winzig ist. Durch diese geringe Größe können wir Namen leicht in Abschnitte unterteilen und diese indexieren.  Dieses "überindexieren" sollte in der Regel keine zu hohen Anforderungen an die Systemressourcen stellen.

Es gibt eine große Bandbreite kommerziell erhältlicher Algorithmen für N-Gramm oder Fuzzy Spelling, die meisten sind jedoch eher grob und liefern keine besonders guten Ergebnisse. Wir bei Search Technologies nutzen gerne den folgenden Algorithmus:

  • Den Namen in alle möglichen Kombinationen der überlappenden 2-Gramme, 3-Gramme und 4-Gramme aufteilen. Diese in separate Felder des Dokuments indexieren
  • Dasselbe an der Abfrage vornehmen
  • Die N-Gramme der Abfrage wie folgt gewichten:  1. Größere N-Gramme (d.h. die 4-Gramme) sind stärker gewichtet als kleinere (d.h. die 2-Gramme),  2. N-Gramme, die näher am Anfang des Begriffs liegen, sind stärker gewichtet als die am Ende, und 3. N-Gramme direkt am Anfang des Wortes zählen extra.
  • Wenn die Suchmaschine es unterstützt können "N von M" Trefferoperatoren helfen, die Leistung zu verbessern und den allgemeinen Suchbereich für teilweise Treffer zu verringern. So könnte die Abfrage beispielsweise erfordern, dass mindestens 60% der N-Gramme in einem Namen vorkommen müssen, damit er als Treffer gewertet wird.

Der oben genannte Algorithmus liefert sehr gute Ergebnisse, wenn die Suchmaschine kein Fuzzy Spelling unterstützt.

Diese Algorithmen können weiterhin verbessert werden, indem man gleichlautende N-Gramm-Variationen hinzufügt, also zum Beispiel "ph" in allen entsprechenden N-Grammen durch "f" ersetzt, ebenso bei anderen ähnlich klingenden Lauten. Diese Erweiterungen sollten bei der Indexierung vorgenommen werden. Dadurch können die Erweiterungen vorgenommen werden, ohne die Abfragen zu verlangsamen (oder nur minimal). Aus Gründen der Genauigkeit sollte man diese Varianten jedoch in separate Felder indexieren, um sicherzustellen, dass exakte Treffer und Teiltreffer in den Suchergebnissen höher bewertet werden.

Ähnliche Ersetzungen können für Transliterationen von Zeichen in anderen Schriftsätzen vorgenommen werden.

 

Treffer #5:  Indexieren von Aliasen oder anderen Alternativen

Wir haben ja bereits über die Behandlung von Namensalternativen geredet, wie zum Beispiel "IBM" für "International Business Machines" oder "Sci-Fi" für "Science Fiction". Die beste Methode, diese Alternativen in einer echten Verzeichnis-Suchanwendung zu behandeln, ist, jeden Begriff als eigenen Eintrag zu indexieren. Dies hat mehrere Vorteile:

  1. Alle oben genannten Techniken für den Abgleich können auf gleiche Art auf die Alternative angewandt werden wie auch auf das Original. Dadurch wird die höchstmögliche Genauigkeit beim Abgleich mit Alternativen geboten.
  2. Das Indexieren von Alternativen als separate Indexeinträge eliminiert "Crossover", also Situationen, in denen Teile des ursprünglichen Namens und der Alternative versehentlich zusammengefügt werden. "Terry Gene Bollea" ist beispielsweise besser als "Hulk Hogan" bekannt. Wenn man beide Alternativen als separate Indexeinträge indexiert, verhindert man, dass Kombinationen wie "Terry Hogan" oder "Hulk Bollea" als gültige Ergebnisse erkannt werden.
  3. Crossover wird kritischer, wenn auch der Abgleich von Teiltreffern angewandt wird. Wenn die Alternative und der ursprüngliche Begriff beide im gleichen Dokument indexiert werden, würde Crossover bei den 2-Gramm, 3-Gramm und 4-Gramm-Mustern bei den Alternativen den Abgleich nach Teiltreffern sinnlos machen, außer, wenn die Alternativen separat indexiert werden.

Leider bedeutet das separate Indexieren von Alternativen auf diese Art eine zusätzliche Belastung für die Infrastruktur und die Abfragefunktionen. Als erstes muss ein Weg gefunden werden, das Hauptdokument und die Alternativen als separate Einträge zu indexieren (dies kann man durch ein Framework zur Dokumentverarbeitung erreichen, welches die Namen vorbereitet, ehe diese an den Indexer weitergeleitet werden). Als zweites, wenn es Änderungen oder Löschungen bei den Hauptbegriffen gab, müssen diese Änderungen auch bei allen alternativen Begriffen entsprechend nachvollzogen werden. Dadurch wird die Wartung des Index komplexer. Und schließlich müssen die Ergebnisse zur ID des Hauptbegriffs zusammengefasst werden, sodass nur ein Suchergebnis für einen bestimmten Namen abgerufen wird.

 

Treffer #6:  Gewichtung nach Popularität

Abschließend sollten wir noch über den Einfluss der Popularität auf Verzeichnissuchen sprechen. Besonders bei konsumentenorientierten Suchen suchen die meisten Nutzer mehr oder weniger nach den gleichen Sachen. "Die Simpsons" und "Tatort" sind zum Beispiel sehr beliebte Fernsehserien, also werden diese bei Suchen nach Fernsehserien wohl häufiger angefragt werden.

Daher haben Suchmaschinen für Verzeichnisse oft eine Gewichtung nach Popularität in den Algorithmus einbezogen. Zum Glück können die meisten Suchmaschinen dem Index einen "statistischen Boost" oder eine "Dokumentengewichtung" geben.

Natürlich muss man etwas ausprobieren, bis man den korrekten Boost für die Einträge im Index gemäß ihrer Popularität gefunden hat. Es gibt auch optimierte Methoden zum Bestimmen dieser Stärken. Man kann zum Beispiel Protokolle für Abfragen und Verwendung nutzen, um zu bestimmen, welche Dokumente am beliebtesten sind, und die Werte für den Boost entsprechend einstellen. Alternativ kann die Gewichtung von einer Drittquelle kommen (zum Beispiel Kasseneingänge). Dann kann die Verknüpfung der Daten mit dem Boost für die Dokumente durch einen iterativen Prozess erledigt werden, in dem eine Formel für den Boost ausprobiert und dann ein Testlauf von Benutzerabfragen statistisch ausgewertet wird.

 

Alles zusammensetzen

Um alles zusammenzusetzen konzentriert man sich am besten auf Datenverarbeitung und Query Processing als getrennte Untersysteme in der endgültigen Verzeichnis-Suchanwendung.

Datenverarbeitung wird benötigt, um Synonymerweiterungen, N-Gramm-Teiltreffer-Aufteilung, Indexieren von Alternativen und Gewichtung nach Popularität vorzunehmen. Einige Suchmaschinen bieten einige dieser Funktionen automatisch, meist wird man aber ein Framework für die Datenverarbeitung benötigen, um genau die Modifikationen vorzunehmen, die von Ihrer Anwendung benötigt werden, ehe die Daten an die Suchmaschine eingereicht werden.

Und man sollte nicht vergessen, dass das Framework für die Datenverarbeitung auch Updates vornehmen muss, die (wie oben beschrieben) komplizierter werden, wenn mehrere Aliase für einen einzelnen Namen als separate Einträge im Index gespeichert werden.

Auf Seiten des Query Processing muss die vom Benutzer eingegebene Abfrage verarbeitet werden, damit exakte Treffer, Treffer bei Varianten der Suchbegriffe, Treffer nach Präfix, Treffer nach Synonymen (außer, wenn diese während dem Indexieren vorgenommen werden) und Teiltreffer gefunden werden. Jede dieser verschiedenen Arten von Treffern muss unabhängig gewichtet werden, sodass explizitere und akkuratere Treffer höher gewichtet werden als unklare und weniger passende Treffer. Das Endergebnis wird höchstwahrscheinlich eine recht große Abfrage mit Dutzenden von Suchbegriffen sein, die alle so gewichtet werden, dass sie das bestmögliche Ergebnis liefern.

Und wenn das dann alles zusammen funktioniert, dann kommt dieser große "Wow"-Effekt. Und für uns hier bei Search Technologies sind diese Momente der Grund, warum wir so viel Spaß an der Arbeit haben.

 

-- Paul

0