Was ist der Unterschied zwischen einem invertierten Index und einem einfachen alten Index?

98

In der Softwareentwicklung erstellen wir ständig Indizes (z. B. in Datenbanken), aber ich höre auch viele Leute, die über invertierte Indizes sprechen. Gibt es etwas grundlegend anderes zwischen den beiden? Sie klingen wie das Gleiche.

Guidoismus
quelle
Zur Verdeutlichung fragen Sie: Was ist anders an einem normalen Index ( en.wikipedia.org/wiki/Index_%28database%29 ), der eine Tabelle basierend auf Daten aufschlüsselt, die bereits in dieser Tabelle vorhanden sind? Ist das korrekt?
Jwheron
3
@guidoism Was jeder nicht erwähnt hat (obwohl Normalität es teilweise anhand von Beispielen beschreibt und Lovesh so ziemlich auf der Schaltfläche steht), ist, dass invertierte Indizes die Basisdaten "invertieren", um effizienter zu sein (z. B. Schlüssel / Daten tauschen, um aus einer anderen Perspektive zu suchen oder alphabetisch / numerisch sortieren, um schnelle Suchalgorithmen zu ermöglichen), während ein Standardindex Daten so speichert, wie sie gefunden werden. Die "Rückwärts / Vorwärts" -Referenzen und die wörtliche Bedeutung des Wortes "invertieren" gelten hier nicht, sondern beziehen sich auf die Inversion von Daten, um ein effizientes Format zu erzeugen, das für die jeweilige Aufgabe spezifisch ist.
TheManWithNoName

Antworten:

215

Eine häufige Verwendung ist "... um eine schnelle Volltextsuche zu ermöglichen."

Die beiden Typen bezeichnen Direktionalität . Einer führt Sie vorwärts durch den Index und der andere führt Sie rückwärts (umgekehrt) durch den Index. Das ist es. Hier gibt es kein Geheimnis zu entdecken. Ansonsten sind die beiden Typen identisch. Es geht nur darum, welche Informationen Sie haben und welche Informationen Sie suchen.

Um Ihre Anfrage zu beantworten, gibt es meines Erachtens keine Möglichkeit zu wissen, warum die Verwendung so ist, wie sie heute ist. Der einzige Grund, warum es wichtig ist zu definieren, welches ist forwardund welches ist, invertedist, dass wir alle ein Gespräch über sie führen können und jeder weiß, über welche Richtung wir sprechen. Denken Sie an die Begriffe "links" und "rechts": Sie sind relativ. Welches ist, was keine Rolle spielt, außer dass jeder zustimmen muss, welches "links" und welches "rechts" ist, damit die Wörter Bedeutung haben. Wenn wir uns als Kultur dazu entschlossen hätten, nach links und rechts zu wechseln, hätten Sie das gleiche Problem, herauszufinden, was eine "Rechtskurve" gegenüber einer "Linkskurve" ist, da sich die vereinbarte Bedeutung geändert hat. Die Benennung ist jedoch beliebig, auf die Bedeutung.

In Ihrem Kommentar, in dem Sie fragen: "Bitte definieren Sie nicht nur die Begriffe", verpassen Sie den Punkt, und ich denke, Sie hängen nur an der Formulierung, wenn es absolut keinen Unterschied zwischen ihnen gibt.


Zum Nutzen zukünftiger Leser werde ich nun einige "Vorwärts" - und "Invertiert" -Indexbeispiele bereitstellen:

Beispiel 1: Websuche

Wenn Sie denken, dass die Umkehrung eines Index so etwas wie das ist Umkehrung einer Funktion in der Mathematik ist , bei der die Umkehrung eine besondere Sache ist, die eine andere Form hat, dann irren Sie sich: Das ist hier nicht der Fall.

In einer Suchmaschine haben Sie eine Liste von Dokumenten (Seiten auf Websites), in die Sie einige Schlüsselwörter eingeben und Ergebnisse zurückerhalten.

Ein Forward-Index (oder nur Index) ist der Liste der Dokumente und welche Wörter darin enthalten sind. Im Beispiel für die Websuche durchsucht Google das Web, erstellt die Liste der Dokumente und ermittelt, welche Wörter auf jeder Seite angezeigt werden.

Der invertierte Index ist die Liste der Wörter und der Dokumente, in denen sie erscheinen. Im Beispiel für die Websuche geben Sie die Liste der Wörter an (Ihre Suchanfrage), und Google erstellt die Dokumente (Links zu Suchergebnissen).

Sie sind beide Indizes - es ist nur eine Frage der Richtung, in die Sie gehen. Weiterleiten erfolgt von Dokumenten-> zu-> Wörtern, invertiert von Wörtern-> zu-> Dokumenten.

Beispiel 2: DNS

Ein weiteres Beispiel ist eine DNS-Suche (die einen Hostnamen verwendet und eine IP-Adresse zurückgibt) und eine umgekehrte Suche (die eine IP-Adresse verwendet und Ihnen den Hostnamen gibt).

Beispiel 3: Ein Buch

Der Index auf der Rückseite eines Buches ist tatsächlich ein invertierter Index , wie in den obigen Beispielen definiert - eine Liste von Wörtern und wo sie im Buch zu finden sind. In einem Buch ist das Inhaltsverzeichnis wie ein Vorwärtsindex : Es ist eine Liste von Dokumenten (Kapiteln), die das Buch enthält, außer dass die Inhaltsverzeichnisse anstelle der Auflistung der Wörter in diesen Abschnitten nur einen Namen / eine allgemeine Beschreibung dessen enthalten, was ist in diesen Dokumenten (Kapiteln) enthalten.

Beispiel 4: Ihr Handy

Der Vorwärtsindex in Ihrem Mobiltelefon ist Ihre Kontaktliste und welche Telefonnummern (Mobiltelefon, Zuhause, Arbeit) diesen Kontakten zugeordnet sind. Mit dem invertierten Index können Sie eine Telefonnummer manuell eingeben. Wenn Sie auf "Wählen" klicken, wird der Name der Person und nicht die Nummer angezeigt, da Ihr Telefon die Telefonnummer übernommen und den damit verbundenen Kontakt gefunden hat.

Jefflunt
quelle
11
Vielen Dank für Ihre Zeit. aber Ihre Antwort ist immer noch nicht informativ. Wie ich in meiner Kopfgeldanfrage erwähnt habe, verstehe ich, was die betreffenden Begriffe bedeuten und warum sie entstehen. Meine Frage war: "Warum haben die Leute, die invertierte Indizes benannt haben, sie invertiert genannt, wenn wir eine lange Tradition haben, die sie nur einfache Indizes nennt? Zum Beispiel sind Indizes am Ende von Büchern, wie Sie betonen, tatsächlich invertiert Aus historischer Sicht standen die Indizes am Ende der Bücher vor den Webindizes. Warum dann die Tradition umkehren? ". Ich vermute, dass es nur eines dieser Dinge war, die gerade passiert sind ...
Manav
1
"Ich glaube nicht, dass es möglich ist zu wissen, warum, ohne eine historische Prüfung der Verwendung der Begriffe durchzuführen " - ich hätte gehofft, jemand würde eine solche historische Prüfung durchführen und eine Antwort geben. :-) Weil es überraschend ist, dass dies der allgemeinsprachigen Bedeutung von "Index" entgegengesetzt ist. (Eine mögliche Antwort ist, dass, als der Ausdruck "invertierter Index" zum ersten Mal gedacht wurde, der Ausdruck "Index" bereits für einen "Index" verwendet wurde, der invertiert in "invertierter Index" ist, dh invertiert in Bezug auf die reale Bedeutung von "Index" ". In diesem Fall wäre es nützlich zu wissen, warum der Forward" Index "den seltsamen Namen bekam.)
ShreevatsaR
2
@jefflunt fragt sich nur, warum die Vorwärtsindizierung verwendet werden soll. Ich spreche hier besonders über das Beispiel der Websuche. Wenn also Google im Rahmen der Vorwärtsindizierung die Liste der Dokumente <-> Wörter in ihnen erstellt und letztendlich die Liste der Wörter <-> der Dokumente in ihrer Suche verwendet, warum wird die Liste der Dokumente <-> Wörter in verwendet? sie ? Mit anderen Worten, meine Frage lautet: Man kann Google nicht fragen, welche Wörter auf einer bestimmten Seite (einem bestimmten Dokument) vorhanden sind, oder es wird hauptsächlich gefragt, wo die von ihm gesuchten Schlüsselwörter auf den Seiten vorkommen. Warum dann Forward-Indizierung?
Quickbrownfox
1
Im Kontext der relationalen Datenbank gibt es also keinen invertierten Index? oder diese Indizes sind tatsächlich "invertierter Index". Probleme mit "akzeptablen" Begriffen in der Literatur sind Unwissenheit / Fehler / Überlegungen von wenigen Pionieren oder Korps, die unterschiedliche Vereinbarungen treffen und ein Teil der Gemeinschaft dieser Nomenklatur folgt. Jeder wird nach einiger Zeit verwirrt. Ich bin sicher, es gibt viele Begriffe in Software, die ursprünglich als A gedacht waren, aber eine andere Community nimmt sie absichtlich oder fälschlicherweise als A 'oder B, syntaktisch vom Kurs abweichend. Es verwirrt immer noch die Hölle von neuen Lernenden.
Nir
1
@ Roylee - Ich habe dieses Whitepaper nicht gelesen. Ich denke, Sie fragen: "Aktualisieren Sie den invertierten Index, wenn Sie den Forward-Index aktualisieren?" Wenn das Ihre Frage ist, lautet die Antwort ja.
Jefflunt
26

Sie nannten es invertiert, nur weil es bereits einen Forward-Index gibt. Nehmen wir das Beispiel einer Suchmaschine, die aus zwei Teilen besteht: Der erste Teil ist "Webcrawler und Parser", die einen Index von Dokument zu Wort erstellen, der zweite Teil ist eine Suchdatenbank, die einen Index von Wort zu Dokument erstellt. Da der erste Index existiert, nennen wir den zweiten Index natürlich als invertierten Index.

Wenn Sie das Inhaltsverzeichnis (Inhaltsverzeichnis) eines Buches als Index bezeichnen, sollten Sie den Index am Ende des Buches als "invertierten Index" bezeichnen. Auf der anderen Seite können Sie das Inhaltsverzeichnis auch als invertierten Index aufrufen.

xeranisch
quelle
6
Dies sollte die akzeptierte Antwort sein, da sie die Frage beantwortet, warum wir einen Index "invertiert" nennen, auch wenn es genau das ist, was jeder von einem "normalen Index" hält. Ein SQL-B-Tree-Index speichert für jedes Wort einen Zeiger auf alle Zeilen ("Dokumente"), die ihn enthalten. Dort nennen wir es "Index". Aber in Suchmaschinen nennen wir genau das gleiche Verfahren plötzlich "invertierter Index". Nicht weil es grundlegend anders ist, sondern weil wir zuerst einen "Vorwärtsindex" (geteilten Text) erstellt und ihn dann "invertiert" haben. Alles in allem stammt der Name "invers" also aus dem Erstellungsprozess und nicht aus der endgültigen Struktur des Index.
Foo Bar
@xeranic danke für die Einblicke. Kurze Frage: Ist es praktisch, Einträge aus der Vorwärtsindexdatei zu entfernen, nachdem daraus ein invertierter Index erstellt wurde?
Roy Lee
3
Ich stimme @FooBar zu. Diese Antwort sollte als die richtige Antwort gewählt werden. Es antwortete, warum wir einen neuen Begriff erfinden inverted index , obwohl alle normalen Indizes in unserem Leben bereits als verwendet werden inverted.
Ryan Lyu
7

Wenn Sie über Index sprechen, meinen Sie normalerweise einige hinzugefügte Berechnungen oder gespeicherte Ergebnisse von Prozeduren, die durchgeführt wurden, um die Anwendung zu beschleunigen (z. B. MySQL oder anderes RDBMS. Konsultieren Sie MySQL in den Dokumenten ). Die Indizierung kann auch mit dem Caching usw. zusammenhängen.

Invertierter Index erstellt eine Datei mit einer Struktur, die in erster Linie für die (Volltext-) Suche gedacht ist.

Der invertierte Index besteht aus zwei Hauptdateien:

  • Wortschatz
  • Vorkommen

Im Wortschatz sind gebräuchliche Wörter aus Text extrahiert (natürlich nach dem Filtern von Blacklist-Wörtern wie Pronomen). Die Vorkommensdatei enthält die Verbindung zwischen Wörtern und Dokumenten (word1 wird in doc1 und doc2 angezeigt, nicht in doc3). Es wird in Form einer Matrix dargestellt.

Indizierungsprozess - invertierter Index

In der obigen Abbildung ist der Vorgang zum Erstellen der beiden genannten Dateien dargestellt.

Wenn Sie sich weiter für dieses Problem interessieren, kann ich Ihnen ein großartiges Buch empfehlen, das von Ricardo Yated geschrieben wurde - Modern Information Retrieval ( siehe Amazon ) - ungefähr auf Seite 200, denke ich.

Ich hoffe es hilft :-)

Bery
quelle
Dies ist eine sehr gute Antwort, da sie erklärt, was ein invertierter Index wirklich ist. Es kommt über die Idee der Vorwärtsindizierung und der inversen Indizierung hinaus, die sich von dem Algorithmus unterscheidet, der für eine Suchfunktion verwendet wird, die durch Erstellen und invertierten Index aktiviert wird.
AN6U5
6

Normalität hat sich schon wunderbar differenziert zwischen einem Forward- und einem invertierten Index unterschieden, aber für die Frage, warum einer als Forward-Index und der andere als invertierter Index bezeichnet wird, werden sie vielleicht deshalb so genannt ---

Ein Beispiel für das Crawlen und Indizieren von Suchmaschinen (oder das Erstellen eines Index für ein Buch) ist, dass ein Vorwärtsindex gleichzeitig erstellt werden kann, während Sie die Webseiten crawlen (oder das Buch lesen) oder vorwärts gehen . Wenn Sie also 10 Webseiten zum Crawlen haben (oder 10 Kapitel in einem Buch), können Sie die erste Webseite crawlen (das erste Kapitel lesen) und dann eine Liste der Wörter erstellen, die auf der Webseite erscheinen (Wörter, die im Kapitel erscheinen), und fortfahren Dieser Vorgang gilt für andere Webseiten (andere Kapitel). Wenn Sie also alle 10 Webseiten gecrawlt haben (alle 10 Kapitel lesen), ist Ihr Vorwärtsindex vollständig, wobei jede Webseite (Kapitel) auf eine Liste von Wörtern verweist, die sie enthält .

Um jedoch einen invertierten Index zu erstellen, müssen Sie alle 10 Webseiten crawlen (lesen Sie die 10 Kapitel) und dann jedes Wort aus jeder Dokumentenliste nehmen und herausfinden, welche Dokumente dieses Wort enthalten. Das ist also so, als würden Sie rückwärts gehen, wenn Sie die Webseiten gecrawlt haben (lesen Sie die Kapitel des Buches) . Es heißt also invertierter Index.

Dies ist nur meine Spekulation.

Lovesh
quelle
5

Es gibt viele Arten von Indizes. Zum Beispiel B-Baum, R-Baum, Hash ... Für verschiedene Zwecke müssen wir den richtigen Index auswählen.

Der invertierte Index ist ein besonderer. Invertierter Index, der normalerweise in Volltextsuchmaschinen verwendet wird. Mit dem invertierten Index können wir die Position eines Wortes in einem Dokument (oder einem Dokumentensatz) so schnell wie möglich ermitteln. Denken Sie an die Grenze von Speicher und CPU, andere Indizes können diesen Job nicht beenden.

Sie können das Lucene-Dokument für weitere Details lesen. Es ist eine Open Source Suchmaschine. http://lucene.apache.org/java/docs/index.html

virushuo
quelle
3

Der Begriff "Inverted Word Index" bezieht sich auf die Änderung der Beziehung eines einzelnen Dokuments mit vielen Wörtern zu jedem eindeutigen Wort, das eine Liste mit vielen Dokumenten enthält (oder identifiziert). Dies setzt effektiv eine Eins-zu-Viele-Beziehung (Docs to Words) voraus und kehrt sie um (oder kehrt sie um), so dass jetzt eine neue "umgekehrte" Eins-zu-Viele-Beziehung besteht, bei der es sich jeweils um ein einzigartiges Wort handelt, das sich auf Many- bezieht. Dokumente (dh alle, die dieses Wort enthalten). Der Ursprung ist wirklich so einfach, und der Begriff "invertierter Index" wurde verwendet, um manuelle Indizes des gleichen Typs zu beschreiben, lange bevor es überhaupt Computer und elektronische Hochgeschwindigkeitsindizierungen gab (ja, zugegeben, ich bin fast ein alter Geezer-Programmierer alt genug, um Grace Hopper als "süße junge Dame" zu betrachten Alter angemessen, um zurück zu werben, als COBOL eine glänzende neue Sprache war). Bitte werfen Sie uns Geezer noch nicht weg, da wir gelegentlich ein oder zwei nützliche und möglicherweise sogar wertvolle historische Leckerbissen bereitstellen können - wenn unser persönlicher RAM noch funktioniert. [Grinsen]

user1009
quelle
2

In invertierten Indizes haben wir die folgende Form:

word1-> Liste der Dokumente, in denen es vorkommt (sortierte Reihenfolge)

word2-> Liste der Dokumente, in denen es vorkommt (sortierte Reihenfolge)

Es ist sehr nützlich für die Verarbeitung von Suchmaschinenabfragen, da es uns ermöglicht, Dokumente zu finden, in denen das Wort vorkommt.

Sie können überwachtes Maschinenlernen verwenden, um diesen invertierten Index zu erstellen.

Programmierer
quelle
6
Das klingt für mich wie ein Index, was ist daran umgekehrt?
Guidoismus
2
@guidoism Ein invertierter Index ist die Inversion eines Forward-Index. Ein Vorwärtsindex speichert eine Liste von Wörtern für jedes Dokument. ZB Doc-> w1, w2
Programmierer
Ich finde immer noch keinen Unterschied zwischen Vorwärts- und Invertiertem Index (in Bezug auf die Funktionsweise lassen Sie das Namensbit). Beides sieht für mich aus wie ein Index, der ein Feld einer Reihe von Dokument-IDs zuordnet. So habe ich verstanden, wie der Orakel-Baum (auch als Forward-Index bezeichnet) die Daten organisiert. Ich sehe keinen Unterschied zu den Prinzipien des invertierten Index. Das Zuordnen eines Dokuments -> w1, w2, w3 scheint mir in Bezug auf die Suche ein ineffizienter Vorschlag zu sein. Frage mich, warum das überhaupt so ist? Damit bin ich wieder auf dem ersten Platz. :-).
user1189332
@Programmer Kurze Frage: Ist es praktisch, Einträge aus der Vorwärtsindexdatei zu entfernen, nachdem daraus ein invertierter Index erstellt wurde?
Roy Lee
0

Noch ein Unterschied:

Die Verarbeitung von Aktualisierungen mit dem invertierten Index ist im Vergleich zum Forward-Index teuer.

Der Vorwärtsindex verarbeitet Aktualisierungen problemlos, indem er die Änderungen nur im entsprechenden Dokumentindex widerspiegelt, während im invertierten Index dieselbe Änderung an mehreren Positionen im invertierten Index angezeigt werden muss.

Siva Kumar
quelle