Was ist invertierter Index? Es ist allgemein bekannt, dass Sie Indizes erstellen müssen, um effiziente Suchvorgänge zu implementieren. Was ist der Unterschied zwischen Index und invertiertem Index und wie baut man einen invertierten Index auf?


Antwort 1:

Invertierter Index

Die elastische Suche verwendet eine Struktur, die als invertierter Index bezeichnet wird und eine sehr schnelle Volltextsuche ermöglicht. Ein invertierter Index besteht aus einer Liste aller eindeutigen Wörter, die in einem Dokument vorkommen, und für jedes Wort aus einer Liste der Dokumente, in denen es vorkommt.

Nehmen wir zum Beispiel an, wir haben zwei Dokumente mit jeweils einem Inhaltsfeld, das Folgendes enthält:

  1. Der schnelle braune Fuchs sprang über den faulen HundSchnelle braune Füchse springen im Sommer über faule Hunde

Um einen invertierten Index zu erstellen, teilen wir zuerst das Inhaltsfeld jedes Dokuments in separate Wörter (die wir als Begriffe oder Token bezeichnen) auf, erstellen eine sortierte Liste aller eindeutigen Begriffe und listen dann auf, in welchem ​​Dokument jeder Begriff erscheint. Das Ergebnis sieht ungefähr so ​​aus:

Term Doc_1 Doc_2
-------------------------
Schnell | | X
Die | X |
braun | X | X
Hund | X |
Hunde | | X
Fuchs | X |
Füchse | | X
in | | X
gesprungen | X |
faul | X | X
Sprung | | X
über X | X
schnell X |
Sommer | | X
die | X |
------------------------

Wenn wir jetzt nach schnellem Braun suchen möchten, müssen wir nur die Dokumente finden, in denen jeder Begriff vorkommt:

Term Doc_1 Doc_2
-------------------------
braun | X | X
schnell X |
------------------------
Insgesamt | 2 | 1

Beide Dokumente stimmen überein, aber das erste Dokument hat mehr Übereinstimmungen als das zweite. Wenn wir einen naiven Ähnlichkeitsalgorithmus anwenden, der nur die Anzahl der übereinstimmenden Begriffe zählt, können wir sagen, dass das erste Dokument besser mit unserer Abfrage übereinstimmt - als das zweite.

Es gibt jedoch einige Probleme mit unserem aktuellen invertierten Index:

  • Schnell und schnell erscheinen sie als separate Begriffe, während der Benutzer sie wahrscheinlich als dasselbe Wort betrachtet. Fuchs und Füchse sind sich ziemlich ähnlich, ebenso wie Hund und Hunde. Sie haben dasselbe Wurzelwort. Springen und springen, obwohl sie nicht aus demselben Wurzelwort stammen, haben sie eine ähnliche Bedeutung. Sie sind Synonyme.

Mit dem vorhergehenden Index würde eine Suche nach + Quick + Fox zu keinem Dokument passen. (Denken Sie daran, ein vorangestelltes + bedeutet, dass das Wort vorhanden sein muss.) Sowohl der Begriff Quick als auch der Begriff fox müssen sich im selben Dokument befinden, um die Abfrage zu erfüllen, aber das erste Dokument enthält quick fox und das zweite Dokument enthält Quick Füchse.

Unser Benutzer kann davon ausgehen, dass beide Dokumente mit der Suchanfrage übereinstimmen. Wir können es besser machen.

Wenn wir die Begriffe in ein Standardformat normalisieren, können wir Dokumente finden, die Begriffe enthalten, die nicht genau mit den vom Benutzer angeforderten übereinstimmen, die jedoch so ähnlich sind, dass sie immer noch relevant sind. Zum Beispiel:

  • Quick kann zu Quick gesenkt werden. Füchse können aufgehalten - auf ihre Wurzelform reduziert - werden, um Fuchs zu werden. In ähnlicher Weise könnten Hunde zu dog.jumped und leap als Synonyme gezüchtet und als einzelner Begriff jump indiziert werden.

Nun sieht der Index so aus:

Term Doc_1 Doc_2
-------------------------
braun | X | X
Hund | X | X
Fuchs | X | X
in | | X
springen | X | X
faul | X | X
über X | X
schnell X | X
Sommer | | X
die | X | X
------------------------

Aber wir sind noch nicht da. Unsere Suche nach + Quick + Fox würde immer noch scheitern, da wir nicht mehr den genauen Begriff Quick in unserem Index haben. Wenn wir jedoch die gleichen Normalisierungsregeln anwenden, die wir für das Inhaltsfeld für unsere Abfragezeichenfolge verwendet haben, wird dies zu einer Abfrage für + quick + fox, die beiden Dokumenten entspricht!

Hinweis: - Dies ist sehr wichtig. Sie können nur Begriffe finden, die in Ihrem Index vorhanden sind. Daher müssen sowohl der indizierte Text als auch die Abfragezeichenfolge in dieselbe Form normalisiert werden.

Referenz: Der endgültige Leitfaden [2.x] | Elastisch


Antwort 2:

In einfachen Worten, es ist eine Hashmap-ähnliche Datenstruktur, die Sie von einem Wort zu einem Dokument oder einer Webseite leitet.

Lassen Sie uns das Problem aus einer anderen Richtung betrachten. Sie haben Millionen von Dokumenten, Webseiten oder Bildern, die wir möglicherweise später abrufen müssen. Um Ihre Intuition in Bezug auf das Indizieren und Abrufen von Informationen zu verbessern, möchte ich Sie daran erinnern, dass Sie den invertierten Index bereits früher gesehen haben.

Dies ist ein Beispiel aus einem zufälligen Lehrbuch. Wenn Sie Informationen zu einem Thema benötigen, z. B. Aktivierungsenergien, öffnen Sie den Index und finden heraus, ob dieses Wort vorhanden ist. Der invertierte Index gibt Ihnen die Seitenzahlen an, auf denen dieses Wort in einer großen Menge von tausend Seiten erklärt wird.

Siehst du? Wenn Sie eine regelmäßige lineare Suche durchführen, benötigen Sie Stunden, um diese Seite zu erreichen. Aber jetzt waren es kaum noch Sekunden.

Wie sieht ein regulärer Index aus?

Natürlich genau gegenüber. Es ordnet den Themen die Seitenzahl zu. Und Sie können leicht sagen, dass sie im Bereich der Suche und Informationsextraktion nicht so nützlich sind. (Vielleicht haben sie woanders viel Glück). Bei der Facebook-Suche werden sie für Rankingzwecke verwendet, damit Sie die relevantesten Ergebnisse erhalten.

So erstellen Sie einen invertierten Index Zum Erstellen eines invertierten Index für die Verwaltung beliebiger Suchsysteme müssen Sie eine Reihe von Schritten ausführen, während Sie die Seiten oder Dokumente analysieren. Lassen Sie uns einen Durchgang machen, während wir unsere eigene Suchmaschine konstruieren.

Ich möchte eine Suchmaschine für alle Dokumente in meinem Computer erstellen. Ich weiß was ich suche. Also starte ich ein Programm, das den gesamten Baum auf meinen Festplatten durchläuft und die gewünschten Seiten sammelt. Ich weiß, dass MP3-Dateien und JPEGs für mich keinen Nutzen haben. Ich werde mein Programm bitten, die txt-, doc- und pdf-Dateien abzurufen. Sobald ich ein Dokument erhalte, fahre ich mit dem nächsten Schritt fort.

1. Abrufen des DokumentsDer Auftrag ist sehr einfach, wenn ich eine Textdatei (.txt) erhalte. Aber wenn es ein Dokument oder ein PDF war, muss ich sie mit einigen Bibliotheken analysieren, um ihren Text abzurufen. Nehmen wir an, ich lese den Text erfolgreich. Was nun?

2. Entfernen Sie den Stop WordsConsider den letzten Absatz. Was waren die wichtigen Wörter, nach denen wir suchen könnten? "text", "libraries", "doc", "pdf", "retrieve", "successful". Aber die meisten anderen Wörter sind nur eine Verschwendung. Wir bezeichnen die am häufigsten vorkommenden Wörter als "Stoppwörter" und entfernen sie, damit ich keine Indizes für Wörter wie "Ich", "Das", "Wir", "Ist", "Ein" erhalte. Bei regelmäßiger Verwendung haben wir eine Liste von 500-1000 Wörtern. Sie kann jedoch je nach Verwendung unterschiedlich sein.

3. Stamm zur Wurzel WordThen kommt Stemming. Wenn ich jetzt nach "Abrufen" suchen möchte, möchte ich ein Dokument anzeigen, das Informationen dazu enthält. Das im Dokument vorhandene Wort heißt jedoch "Abrufen" statt "Abrufen". Um die beiden Wörter in Beziehung zu setzen, werde ich einen Teil von jedem Wort, das ich lese, hacken, damit ich das "Wurzelwort" bekomme. Abrufen kann zu "Abrufen" werden. So wird "abrufen". Wir müssen uns über die Regeln im Klaren sein, nach denen wir die Wörter hacken. Hierzu gibt es Standardwerkzeuge wie "Porter's Stemmer". Hier können Sie mit einem Porter Stemmer herumspielen: Porter Stemmer Online

4. Dokument-IDs aufzeichnen Bereiten Sie sich jetzt auf die Hauptaufgabe vor - Indizieren. Jedes Dokument, das ich habe, verfügt über eine eindeutige Dokument-ID. Wenn ich auf ein Wort stoße, das jetzt ununterbrochen vorkommt, speichere ich es in folgender Form in meinem Speicher: retriev ==> docID104007

Wenn ich das gleiche Wort in einem anderen Dokument erhalte, kann ich schreiben ==> docID104007retriev ==> docID154033

Aber sehr bald muss ich sie in einem einzigen listretriev kombinieren ==> docID104007 & docID154033

Ich kann mich weiter verbessern, indem ich schreibe, wie oft das Wort im Dokument vorkommt, damit wir die wichtigeren Dokumente beim Abrufen in eine Rangfolge bringen können. retriev ==> docID104007 | 5 | & docID154033 | 2 |

5. Zusammenführen und Speichern der TermsFinally, wir speichern sie alle in Plattendateien. Es ist großartig, wenn wir den Index nach den Wörtern sortieren, um ihn schnell und einfach abzurufen.

Dies alles erfordert natürlich einige spezifische Datenstrukturen, die Ihre Arbeit vereinfachen.

Wir können weitere Sekundärindizes erstellen, um den Abruf zu verbessern. Es gibt auch viele Probleme im Zusammenhang mit dem Ranking.

Ich hoffe, dies hat Ihnen erklärt, wie invertierte Indizes erstellt werden. Wenn Sie mehr darüber lesen möchten, können Sie auf ein fantastisches Buch mit dem Titel „Introduction to Information Retrieval“ von Chris Manning verweisen, das kostenlos online verfügbar ist.