Índex invertit
|
No s'ha de confondre amb Índex invers. |
En informàtica, un índex invertit (també anomenat fitxer de publicacions o fitxer invertit) és un índex de base de dades que emmagatzema un mapatge des de contingut, com ara paraules o números, fins a les ubicacions d’una taula, d’un document o d’un conjunt de documents (anomenats en contrast amb un índex directe, que assigna els documents al contingut). L’objectiu d’un índex invertit és permetre cerques ràpides de text complet, amb un cost de processament augmentat quan s’afegeix un document a la base de dades. El fitxer invertit pot ser el propi fitxer de base de dades, en lloc del seu índex. És l'estructura de dades més popular que s'utilitza en sistemes de recuperació de documents [1] utilitzada a gran escala, per exemple en motors de cerca. A més, diversos sistemes significatius de gestió de bases de dades basats en mainframe per a usos generals han utilitzat arquitectures de llistes invertides, incloses ADABAS, DATACOM / DB i Model 204 .
Hi ha dues variants principals dels índexs invertits: un índex invertit a nivell de registre (o un índex de fitxer invertit o simplement un fitxer invertit) conté una llista de referències a documents per a cada paraula. Un índex invertit a nivell de paraula (o índex invertit complet o llista invertida) conté addicionalment les posicions de cada paraula dins d'un document.[2] Aquest darrer formulari ofereix més funcionalitats (com ara cerques de frases), però necessita més poder de processament i espai per crear-se.
Aplicacions
[modifica]L'estructura de dades de l’ índex invertit és un component central d’un algorisme típic d’indexació de motors de cerca. L’objectiu d’una implementació del motor de cerca és optimitzar la velocitat de la consulta: trobar els documents on es produeix la paraula X. Un cop es desenvolupa un índex de reenviament, que emmagatzema llistes de paraules per document, a continuació, s'inverteix per desenvolupar un índex invertit. La consulta de l’índex directe requeriria una iteració seqüencial a través de cada document i de cada paraula per verificar un document coincident. El temps, la memòria i els recursos de processament per realitzar aquesta consulta no sempre són tècnicament realistes. En lloc de llistar les paraules per document a l'índex directe, es desenvolupa l'estructura de dades de l'índex invertit que llista els documents per paraula.
Amb l’índex invertit creat, la consulta ara es pot resoldre saltant a la paraula ID (mitjançant accés aleatori) a l’índex invertit.
En temps anteriors a la informàtica, les concordances amb llibres importants es muntaven manualment. Es tractava d’índexs invertits efectivament amb una petita quantitat de comentaris acompanyants que requeria un gran esforç per produir.
En bioinformàtica, els índexs invertits són molt importants en el conjunt de seqüències de fragments curts d'ADN seqüenciat. Una manera de trobar la font d’un fragment és buscar-lo contra una seqüència d’ADN de referència. Es pot explicar un nombre reduït de desajustos (a causa de les diferències entre l’ADN seqüenciat i l’ADN de referència, o errors) dividint el fragment en fragments més petits; és probable que almenys un subfragment coincideixi amb la seqüència d’ADN de referència. La coincidència requereix la construcció d’un índex invertit de totes les cadenes d’una determinada longitud a partir de la seqüència d’ADN de referència. Com que l’ADN humà conté més de 3.000 milions de parells de bases i necessitem emmagatzemar una subcadena d’ADN per a cada índex i un enter de 32 bits per a l’índex mateix, el requisit d’emmagatzematge d’aquest índex invertit probablement estaria en les desenes de gigabytes.
Compressió
[modifica]Per motius històrics, la compressió de llistes invertides i la compressió de mapes de bits es van desenvolupar com a línies de recerca separades i només després es va reconèixer que resolia essencialment el mateix problema.[3]
Vegeu també
[modifica]Bibliografia
[modifica]- Knuth, D. E.. «6.5. Retrieval on Secondary Keys». A: The Art of Computer Programming. Third. Reading, Massachusetts: Addison-Wesley, 1997. ISBN 0-201-89685-0.
- Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri ACM Transactions on Database Systems [Nova York], 23, 4, 12-1998, pàg. 453–490. DOI: 10.1145/296854.277632.
- Zobel, Justin; Moffat, Alistair ACM Computing Surveys [Nova York], 38, 2, 7-2006, pàg. 6. DOI: 10.1145/1132956.1132959.
- Baeza-Yates, Ricardo. Modern information retrieval. Reading, Massachusetts: Addison-Wesley Longman, 1999, p. 192. ISBN 0-201-39829-X.
- Salton, Gerard; Fox, Edward A.; Wu, Harry Commun. ACM, 26, 11, 1983, pàg. 1022. DOI: 10.1145/182.358466.
- Information Retrieval: Implementing and Evaluating Search Engines. Cambridge, Massachusetts: MIT Press, 2010. ISBN 978-0-262-02651-2 [Consulta: 25 febrer 2021]. Arxivat 2020-10-05 a Wayback Machine.
Referències
[modifica]- ↑ Zobel, Moffat & Ramamohanarao 1998
- ↑ Baeza-Yates & Ribeiro-Neto 1999
- ↑ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson. "An Experimental Study of Bitmap Compression vs. Inverted List Compression" Arxivat 2019-12-07 a Wayback Machine.. 2017. doi: 10.1145/3035918.3064007
Enllaços externs
[modifica]- Diccionari d’algorismes i estructures de dades del NIST: índex invertit
- Gestió de gigabytes per a Java, un motor de cerca gratuït de text complet per a grans col·leccions de documents escrits en Java.
- Lucene - Apache Lucene és una biblioteca de motors de cerca de text amb funcions completes escrita en Java.
- Sphinx Search : biblioteca de motors de cerca de text de gran rendiment, amb funcions completes, utilitzada per craigslist i altres que utilitzen un índex invertit.
- Exemples d'implementacions al codi Rosetta