Índice invertido - Inverted index

Em ciência da computação , um índice invertido (também conhecido como arquivo de postagens ou arquivo invertido ) é um índice de banco de dados que armazena um mapeamento de conteúdo, como palavras ou números, para suas localizações em uma tabela , ou em um documento ou conjunto de documentos (nomeados em contraste com um índice de encaminhamento , que mapeia de documentos para conteúdo). O objetivo de um índice invertido é permitir pesquisas rápidas de texto completo , a um custo de processamento maior quando um documento é adicionado ao banco de dados. O arquivo invertido pode ser o próprio arquivo de banco de dados, em vez de seu índice. É a estrutura de dados mais popular usada na recuperação de documentos sistemas, usados ​​em grande escala, por exemplo, em motores de busca . Além disso, vários sistemas significativos de gerenciamento de banco de dados baseados em mainframe de propósito geral usaram arquiteturas de lista invertida, incluindo ADABAS , DATACOM / DB e Modelo 204 .

Existem duas variantes principais de índices invertidos: Um índice invertido em nível de registro (ou índice de arquivo invertido ou apenas arquivo invertido ) contém uma lista de referências a documentos para cada palavra. Um índice invertido em nível de palavra (ou índice invertido completo ou lista invertida ) contém adicionalmente as posições de cada palavra em um documento. A última forma oferece mais funcionalidade (como pesquisas de frase ), mas precisa de mais poder de processamento e espaço para ser criado.

Formulários

A estrutura de dados do índice invertido é um componente central de um algoritmo de indexação de mecanismo de pesquisa típico . O objetivo de uma implementação de mecanismo de pesquisa é otimizar a velocidade da consulta: encontre os documentos onde ocorre a palavra X. Depois que um índice direto é desenvolvido, que armazena listas de palavras por documento, ele é invertido para desenvolver um índice invertido. Consultar o índice de encaminhamento exigiria iteração sequencial em cada documento e em cada palavra para verificar um documento correspondente. O tempo, a memória e os recursos de processamento para realizar essa consulta nem sempre são tecnicamente realistas. Em vez de listar as palavras por documento no índice direto, a estrutura de dados do índice invertido é desenvolvida, listando os documentos por palavra.

Com o índice invertido criado, a consulta agora pode ser resolvida saltando para a palavra ID (via acesso aleatório ) no índice invertido.

Em tempos pré-computador, as concordâncias para livros importantes eram montadas manualmente. Esses eram índices efetivamente invertidos com uma pequena quantidade de comentários que exigiam muito esforço para serem produzidos.

Em bioinformática, os índices invertidos são muito importantes na montagem de sequências de fragmentos curtos de DNA sequenciado. Uma maneira de encontrar a origem de um fragmento é pesquisá-lo em uma sequência de DNA de referência. Um pequeno número de incompatibilidades (devido a diferenças entre o DNA sequenciado e o DNA de referência, ou erros) pode ser contabilizado dividindo o fragmento em fragmentos menores - pelo menos um subfragmento provavelmente corresponderá à sequência de DNA de referência. A correspondência requer a construção de um índice invertido de todas as substrings de um determinado comprimento da sequência de DNA de referência. Como o DNA humano contém mais de 3 bilhões de pares de bases e precisamos armazenar uma substring de DNA para cada índice e um inteiro de 32 bits para o próprio índice, o requisito de armazenamento para esse índice invertido provavelmente seria da ordem de dezenas de gigabytes.

Compressão

Por razões históricas, a compactação de lista invertida e a compactação de bitmap foram desenvolvidas como linhas de pesquisa separadas e só mais tarde foram reconhecidas como resolvendo essencialmente o mesmo problema.

Veja também

Bibliografia

  • Knuth, DE (1997) [1973]. "6.5. Recuperação em chaves secundárias". The Art of Computer Programming (Terceira ed.). Reading, Massachusetts : Addison-Wesley . ISBN   0-201-89685-0 .
  • Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (dezembro de 1998). "Arquivos invertidos versus arquivos de assinatura para indexação de texto". Transações ACM em sistemas de banco de dados . Nova York: Association for Computing Machinery . 23 (4): 453–490. doi : 10.1145 / 296854.277632 . S2CID   7293918 .
  • Zobel, Justin; Moffat, Alistair (julho de 2006). "Arquivos invertidos para motores de busca de texto". Pesquisas de computação ACM . Nova York: Association for Computing Machinery . 38 (2): 6. doi : 10.1145 / 1132956.1132959 . S2CID   207158957 .
  • Baeza-Yates, Ricardo ; Ribeiro-Neto, Berthier (1999). Recuperação de informação moderna . Reading, Massachusetts : Addison-Wesley Longman. p. 192. ISBN   0-201-39829-X .
  • Salton, Gerard; Fox, Edward A .; Wu, Harry (1983). "Recuperação de informação booleana estendida". Comum. ACM . ACM. 26 (11): 1022. doi : 10.1145 / 182.358466 . hdl : 1813/6351 . S2CID   207180535 .
  • Recuperação de informações: implementação e avaliação de mecanismos de pesquisa . Cambridge, Massachusetts: MIT Press. 2010. ISBN   978-0-262-02651-2 .

Referências

links externos