Inverterat index

Inom datavetenskap är ett inverterat index (även kallat en postningslista , postingsfil eller inverterad fil ) ett databasindex som lagrar en mappning från innehåll, såsom ord eller siffror, till dess platser i en tabell eller i ett dokument eller en uppsättning dokument (namngivna i motsats till ett framåtindex , som mappar från dokument till innehåll). Syftet med ett inverterat index är att möjliggöra snabba fulltextsökningar , till en kostnad av ökad bearbetning när ett dokument läggs till i databasen. Den inverterade filen kan vara själva databasfilen, snarare än dess index. Det är den mest populära datastrukturen som används i dokumenthämtningssystem , som används i stor skala till exempel i sökmotorer . Dessutom har flera betydande stordatorbaserade databashanteringssystem för allmänna ändamål använt inverterade listarkitekturer, inklusive ADABAS , DATACOM/DB och Model 204 .

Det finns två huvudvarianter av inverterade index: Ett inverterat index på rekordnivå (eller inverterat filindex eller bara inverterad fil ) innehåller en lista med referenser till dokument för varje ord. Ett inverterat index på ordnivå (eller helt inverterat index eller inverterad lista ) innehåller dessutom positionerna för varje ord i ett dokument. Den senare formen erbjuder mer funktionalitet (som frassökningar ), men behöver mer processorkraft och utrymme för att skapas.

Ansökningar

Den inverterade indexdatastrukturen är en central komponent i en typisk sökmotorindexeringsalgoritm . Ett mål med en sökmotorimplementering är att optimera sökhastigheten: hitta de dokument där ordet X förekommer. När ett framåtindex har utvecklats, som lagrar listor med ord per dokument, inverteras det nästa för att utveckla ett inverterat index. Att fråga framåtindexet skulle kräva sekventiell iteration genom varje dokument och till varje ord för att verifiera ett matchande dokument. Tiden, minnet och bearbetningsresurserna för att utföra en sådan fråga är inte alltid tekniskt realistiska. Istället för att lista orden per dokument i framåtindexet utvecklas den inverterade indexdatastrukturen som listar dokumenten per ord.

Med det inverterade indexet skapat kan frågan nu lösas genom att hoppa till ordet ID (via direktåtkomst ) i det inverterade indexet.

I före-datortider sammanställdes överensstämmelser till viktiga böcker manuellt. Dessa var effektivt inverterade index med en liten mängd åtföljande kommentarer som krävde en enorm ansträngning att producera.

Inom bioinformatik är inverterade index mycket viktiga i sekvenssammansättningen av korta fragment av sekvenserat DNA. Ett sätt att hitta källan till ett fragment är att söka efter det mot en referens-DNA-sekvens. Ett litet antal felmatchningar (på grund av skillnader mellan sekvenserat DNA och referens-DNA, eller fel) kan förklaras genom att dela upp fragmentet i mindre fragment - minst ett subfragment kommer sannolikt att matcha referens-DNA-sekvensen. Matchningen kräver att man konstruerar ett inverterat index av alla delsträngar av en viss längd från referens-DNA-sekvensen. Eftersom det mänskliga DNA:t innehåller mer än 3 miljarder baspar, och vi behöver lagra en DNA-delsträng för varje index och ett 32-bitars heltal för själva indexet, skulle lagringskravet för ett sådant inverterat index troligen vara i tiotals gigabyte.

Kompression

Av historiska skäl utvecklades inverterad listkomprimering och bitmappskomprimering som separata forskningslinjer, och först senare erkändes de lösa i huvudsak samma problem.

Se även

Bibliografi

Knuth, DE (1997) [1973]. "6.5. Hämtning på sekundära nycklar". The Art of Computer Programming (tredje upplagan). Reading, Massachusetts : Addison-Wesley . ISBN 0-201-89685-0 .
Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (december 1998). "Inverterade filer kontra signaturfiler för textindexering" . ACM-transaktioner på databassystem . New York: Association for Computing Machinery . 23 (4): 453–490. doi : 10.1145/296854.277632 . S2CID 7293918 .
Zobel, Justin; Moffat, Alistair (juli 2006). "Inverterade filer för textsökmotorer". ACM Computing Surveys . New York: Association for Computing Machinery . 38 (2): 6. doi : 10.1145/1132956.1132959 . S2CID 207158957 .
Baeza-Yates, Ricardo ; Ribeiro-Neto, Berthier (1999). Modern informationssökning . Reading, Massachusetts : Addison-Wesley Longman. sid. 192. ISBN 0-201-39829-X .
Salton, Gerard; Fox, Edward A.; Wu, Harry (1983). "Utökad boolesk informationsinhämtning". Commun. ACM . ACM. 26 (11): 1022. doi : 10.1145/182.358466 . hdl : 1813/6351 . S2CID 207180535 .
Informationssökning: Implementering och utvärdering av sökmotorer . Cambridge, Massachusetts: MIT Press. 2010. ISBN 978-0-262-02651-2 . Arkiverad från originalet 2020-10-05 . Hämtad 2010-08-08 .

externa länkar

NIST:s Dictionary of Algorithms and Data Structures: inverterat index
Hantera Gigabyte för Java en gratis sökmotor i fulltext för stora dokumentsamlingar skrivna i Java.
Lucene - Apache Lucene är ett fullfjädrat textsökmotorbibliotek skrivet i Java.
Sphinx Search - Öppen källkod högpresterande, fullfjädrad textsökmotorbibliotek som används av craigslist och andra som använder ett inverterat index.
Exempel på implementeringar på Rosetta Code
Caltechs verktygslåda för bildsökning i stor skala : en verktygslåda från Matlab som implementerar bildsökning med inverterad fil i Bag-of-Words.