Umgekehrter Index

Im Informatik, ein Umgekehrter Index (auch als als bezeichnet als Postingsliste, Postingsdatei, oder inverted Datei) ist ein Datenbankindex Speichern einer Zuordnung von Inhalten wie Wörtern oder Zahlen auf seine Standorte in a Tischoder in einem Dokument oder einer Reihe von Dokumenten (im Gegensatz zu a genannt Vorwärtsindex, was von Dokumenten zu Inhalten kartiert). Der Zweck eines umgekehrten Index besteht darin, schnell zuzulassen Volltext-Suchemit Kosten einer erhöhten Verarbeitung, wenn ein Dokument in die Datenbank hinzugefügt wird. Die invertierte Datei kann die Datenbankdatei selbst und nicht der Index sein. Es ist die beliebteste Datenstruktur in Dokumentenabruf Systeme,[1] zum Beispiel in großem Maßstab in großer Maßstab in verwendet Suchmaschinen. Zusätzlich mehrere bedeutende allgemeine Verwaltungszwecke Mainframe-basierend Datenbankmanagementsystem haben umgekehrte Listenarchitekturen verwendet, einschließlich Adabas, Datacom/db, und Modell 204.

Es gibt zwei Hauptvarianten invertierter Indizes: a Invertierte Index auf Datensatzebene (oder Umgekehrter Dateiindex oder nur inverted Datei) Enthält eine Liste von Verweise auf Dokumente für jedes Wort. EIN Umgekehrter Index auf Wortebene (oder Voller invertierter Index oder Inverted List) Enthält zusätzlich die Positionen jedes Wortes in einem Dokument.[2] Die letztere Form bietet mehr Funktionen (wie Suchanfragen), benötigt aber mehr Verarbeitungsleistung und Raum, um zu erstellen.

Anwendungen

Der umgekehrte Index Datenstruktur ist eine zentrale Komponente einer typischen Suchmaschinenindizierungsalgorithmus. Ein Ziel einer Suchmaschinenimplementierung ist es, die Geschwindigkeit der Abfrage zu optimieren: Finden Sie die Dokumente, in denen Word X auftritt. Einmal Vorwärtsindex Es wird entwickelt, das Listen von Wörtern pro Dokument speichert. Als nächstes wird es umgekehrt, um einen umgekehrten Index zu entwickeln. Das Abfragen des Vorwärtsindex erfordert eine sequentielle Iteration in jedem Dokument und in jedem Wort, um ein übereinstimmendes Dokument zu überprüfen. Die Zeit-, Speicher- und Verarbeitungsressourcen zur Ausführung einer solchen Abfrage sind technisch nicht immer realistisch. Anstatt die Wörter pro Dokument im Vorwärts -Index aufzulisten, wird die invertierte Indexdatenstruktur entwickelt, in der die Dokumente pro Wort aufgeführt sind.

Mit dem erstellten invertierten Index kann die Abfrage jetzt gelöst werden, indem Sie zur Word -ID springen (via Zufallszugriff) im umgekehrten Index.

In Zeiten vor dem Komputer, Konkordanzen Wichtige Bücher wurden manuell versammelt. Dies waren effektiv umgekehrte Indizes mit einer geringen Menge an begleitender Kommentar, die eine enorme Menge an Anstrengungen zur Erzeugung erforderten.

In der Bioinformatik sind umgekehrte Indizes in der sehr wichtig Sequenzbaugruppe von kurzen Fragmenten sequenzierter DNA. Eine Möglichkeit, die Quelle eines Fragments zu finden, besteht darin, nach einer Referenz -DNA -Sequenz danach zu suchen. Eine kleine Anzahl von Fehlpaarungen (aufgrund von Unterschieden zwischen der sequenzierten DNA und der Referenz -DNA oder der Fehler) kann durch Teilen des Fragments in kleinere Fragmente berücksichtigt werden. Die Übereinstimmung erfordert das Erstellen eines invertierten Index aller Substrings einer bestimmten Länge aus der Referenz -DNA -Sequenz. Da die menschliche DNA mehr als 3 Milliarden Basispaare enthält und wir ein DNA-Substring für jeden Index und eine 32-Bit-Ganzzahl für den Index selbst speichern müssen, würde die Speicheranforderung für einen solchen invertierten Index wahrscheinlich in den Zehns von Gigabyte liegen.

Kompression

Aus historischen Gründen, umgekehrte Listenkomprimierung und Bitmap -Komprimierung wurden als getrennte Forschungslinien entwickelt und erst später als Lösung im Wesentlichen das gleiche Problem anerkannt.[3]

Siehe auch

Literaturverzeichnis

  • Knuth, D. E. (1997) [1973]. "6.5. Abrufen auf Sekundärschlüssel". Die Kunst der Computerprogrammierung (Dritter Aufl.). Lesen, Massachusetts: Addison-Wesley. ISBN 0-201-89685-0.
  • Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (Dezember 1998). "Invertierte Dateien gegen Signaturdateien für die Textindexierung". ACM -Transaktionen auf Datenbanksystemen. New York: Verband für Rechenmaschinen. 23 (4): 453–490. doi:10.1145/296854.277632. S2CID 7293918.
  • Zobel, Justin; Moffat, Alistair (Juli 2006). "Inverted Dateien für Textsuchmaschinen". ACM Computing -Umfragen. New York: Verband für Rechenmaschinen. 38 (2): 6. doi:10.1145/1132956.1132959. S2CID 207158957.
  • Baeza-yates, Ricardo; Ribeiro-Neto, Berthier (1999). Modernes Informationsabruf. Lesen, Massachusetts: Addison-Wesley Longman. p. 192. ISBN 0-201-39829-x.
  • Salton, Gerard; Fox, Edward A.; Wu, Harry (1983). "Erweiterte Boolesche Informationsabnahme". Kommunieren. ACM. ACM. 26 (11): 1022. doi:10.1145/182.358466. HDL:1813/6351. S2CID 207180535.
  • Informationsabruf: Implementierung und Bewertung von Suchmaschinen. Cambridge, Massachusetts: MIT Press. 2010. ISBN 978-0-262-02651-2.

Verweise

  1. ^ Zobel, Moffat & Ramamohanarao 1998
  2. ^ Baeza-yates & Ribeiro-Neto 1999, p. 192
  3. ^ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson."Eine experimentelle Studie zur Bitmap -Komprimierung im Vergleich zu invertierter Listenkomprimierung". 2017. doi: 10.1145/3035918.3064007

Externe Links