Qual é a diferença entre um índice invertido e um índice simples e antigo?

98

Na engenharia de software, criamos índices o tempo todo (por exemplo, em bancos de dados), mas também ouço muitas pessoas falarem sobre índices invertidos. Existe algo fundamentalmente diferente entre os dois? Eles soam como a mesma coisa.

indexing terminology guidoísmo
fonte
3
en.wikipedia.org/wiki/Inverted_index
paxdiablo
Para esclarecer, você está perguntando: o que há de diferente em um índice normal ( en.wikipedia.org/wiki/Index_%28database%29 ) que divide uma tabela com base nos dados que já existem nessa tabela? Isso é correto?
jwheron
3
@guidoism O que todos deixaram de mencionar (embora normalocity o descreva parcialmente por exemplos e lovesh esteja praticamente certo) é que os índices invertidos "invertem" os dados básicos para serem mais eficientes (por exemplo, chaves de troca / dados para pesquisar de diferentes perspectivas ou ordenando alfabeticamente / numericamente para permitir algoritmos de pesquisa rápida), enquanto um índice padrão armazena os dados à medida que os encontra. As referências "para trás / para a frente" e o significado literal da palavra "inverter" não se aplicam aqui, em vez disso, ela se refere à inversão de dados para produzir um formato eficiente específico para a tarefa em questão.
TheManWithNoName

Respostas:

215

Um uso comum é "... para permitir uma pesquisa rápida de texto completo."

Os dois tipos denotam direcionalidade . Um leva você para frente no índice e o outro leva você para trás (o inverso) através do índice. É isso aí. Não há mistério para descobrir aqui. Caso contrário, os dois tipos são idênticos, é apenas uma questão de quais informações você tem e, como resultado, quais informações você está tentando encontrar.

Para responder à sua pergunta, não acho que haja realmente uma maneira de saber por que o uso é o que é hoje. A única razão pela qual é importante definir qual é forwarde qual é o significado.inverted é para que todos possamos ter uma conversa sobre eles e todos saibam de que direção estamos falando. Pense nos termos "esquerda" e "direita": eles são relativos. O que não importa, exceto que todos precisam concordar em qual é "esquerdo" e qual é "certo" para que as palavras tenham significado. Se, como cultura, decidíssemos virar para a esquerda e para a direita, você teria o mesmo problema em descobrir o que é uma "curva à direita" versus uma "curva à esquerda", uma vez que o significado acordado mudou. No entanto, a nomenclatura é arbitrária,

Em seu comentário em que você pergunta "por favor, não defina apenas os termos", você está perdendo o ponto e acho que está apenas ficando preso ao texto quando não há absolutamente nenhuma diferença entre eles.


Para o benefício de futuros leitores, irei agora fornecer vários exemplos de índice "avançado" e "invertido":

Exemplo 1: pesquisa na web

Se você está pensando que o inverso de um índice é algo como o inverso de uma função em matemática , onde o inverso é uma coisa especial que tem uma forma diferente, você está enganado: esse não é o caso aqui.

Em um mecanismo de busca, você tem uma lista de documentos (páginas em sites), onde você insere algumas palavras-chave e obtém os resultados.

Um índice de encaminhamento (ou apenas índice) é a lista de documentos e quais palavras aparecem neles. No exemplo da pesquisa na web, o Google rastreia a web, construindo a lista de documentos, descobrindo quais palavras aparecem em cada página.

O índice invertido é a lista de palavras e os documentos nos quais aparecem. No exemplo de pesquisa na web, você fornece a lista de palavras (sua consulta de pesquisa) e o Google produz os documentos (links de resultados de pesquisa).

Ambos são índices - é apenas uma questão de qual direção você está indo. Encaminhar é de documentos-> para-> palavras, invertido é de palavras-> para-> documentos.

Exemplo 2: DNS

Outro exemplo é uma consulta DNS (que pega um nome de host e retorna um endereço IP) e uma consulta reversa (que pega um endereço IP e fornece o nome do host).

Exemplo 3: um livro

O índice no final de um livro é na verdade um índice invertido , conforme definido pelos exemplos acima - uma lista de palavras e onde encontrá-las no livro. Em um livro, o índice analítico é como um índice de encaminhamento : é uma lista de documentos (capítulos) que o livro contém, exceto em vez de listar as palavras nessas seções, o índice analítico apenas fornece um nome / descrição geral do que contidas nesses documentos (capítulos).

Exemplo 4: seu telefone celular

O índice de encaminhamento no seu telefone celular é sua lista de contatos e quais números de telefone (celular, residencial, comercial) estão associados a esses contatos. O índice invertido é o que permite inserir manualmente um número de telefone, e quando você clica em "discar", vê o nome da pessoa, ao invés do número, porque seu telefone pegou o número de telefone e encontrou o contato associado a ele.

Jefflunt
fonte
11
obrigado pelo seu tempo. mas sua resposta ainda não é informativa. Como mencionei em meu pedido de recompensa, eu compreendo o que os termos envolvidos significam e por que eles surgem. Minha pergunta era: "por que as pessoas que nomearam índices invertidos os chamam de invertidos quando temos uma longa tradição que os chama de índices simples? Por exemplo, os índices no final dos livros, como você salientou, estão na verdade invertidos. Indo pela perspectiva histórica, os índices no final dos livros vieram antes dos índices da web. Então, por que inverter a tradição? ”. Meu palpite é que foi apenas uma daquelas coisas que acabaram de acontecer ...
Manav
1
"Não acho que seja possível saber por quê sem fazer um exame histórico do uso dos termos" - eu esperava que alguém fizesse esse exame histórico e desse uma resposta. :-) Porque isso sendo oposto ao significado da linguagem comum de "índice" é surpreendente. (Uma resposta possível é que quando a frase "índice invertido" foi pensada pela primeira vez, a frase "índice" já era para algum "índice" invertido em relação a "índice invertido", ou seja, invertido com o significado real de "índice ". Nesse caso, seria útil saber por que o" índice "direto recebeu o nome estranho.)
ShreevatsaR
2
@jefflunt apenas querendo saber por que a indexação direta deve ser usada. Estou falando particularmente sobre o exemplo de pesquisa na web aqui. Portanto, se o Google, como parte da indexação direta, faz a lista de documentos <-> palavras neles e, por fim, usa a lista de palavras <-> lista de documentos em sua pesquisa, por que a lista de documentos <-> palavras em eles ? Em outras palavras, minha pergunta é: não se pode perguntar ao google quais palavras existem em uma determinada página (documento) ou principalmente vai perguntar onde as palavras-chave que ele procura aparecem nas páginas. Então, por que fazer indexação direta?
quickbrownfox
1
Então, no contexto do banco de dados relacional, não há índice invertido? ou esses índices são na verdade 'índice invertido'. Problemas com termos "agradáveis" na literatura são ignorância / erro / deliberação de poucos pioneiros ou corporações que iniciam acordos diferentes e parte da comunidade segue essa nomenclatura. Todo mundo fica confuso depois de algum tempo. Tenho certeza de que há muitos termos em software que originalmente deveriam ser, digamos, A, mas uma comunidade diferente, deliberada ou erroneamente, considera A 'ou B, sintaticamente fora do curso. Ainda confunde o inferno fora do novo aluno.
nir
1
@Roylee - Eu não li esse white paper. Acho que o que você está perguntando é: "Você atualiza o índice invertido ao atualizar o índice direto?" Se essa é sua pergunta, a resposta é sim.
jefflunt
26

Eles o chamaram de invertido apenas porque já existe um índice direto. Tomemos o exemplo do motor de busca, composto por duas partes: a primeira parte é "web crawler e parser" que constrói um índice de documento a palavra, a segunda parte é banco de dados de busca que constrói um índice de palavra a documento. Como o primeiro índice existe, naturalmente chamamos o segundo índice de índice invertido.

Se você nomear o TOC (Tabela de conteúdo) de um livro como índice, deverá chamar o índice no final do livro de "índice invertido". Ou, por outro lado, você pode chamar o TOC de índice invertido.

xerânico
fonte
6
Essa deve ser a resposta aceita, pois responde à pergunta por que chamamos um índice de "invertido", mesmo que seja apenas o que todos pensam de um "índice normal". Um índice SQL b-tree armazena para cada palavra um ponteiro para todas as linhas ("documentos") que a contêm. Lá nós o chamamos de "índice". Mas nos motores de busca de repente chamamos esse mesmo procedimento de "índice invertido". Não porque seja fundamentalmente diferente, mas porque primeiro criamos um "índice progressivo" (dividir texto) e depois o "invertemos". Portanto, em suma, o nome "inverso" vem do processo de criação, não da estrutura final do índice.
Foo Bar de
@xeranic obrigado pelos insights. Pergunta rápida: É prático remover entradas do arquivo de índice de encaminhamento após o índice invertido ser construído a partir dele?
Roy Lee
3
Eu concordo com @FooBar. Esta resposta deve ser escolhida como a resposta certa. Ele respondeu por que inventamos um novo termo inverted index , embora todos os índices normais em nossa vida já sejam usados ​​como inverted.
Ryan Lyu
7

normalmente, ao falar sobre índice, você se refere a alguns cálculos adicionados ou resultados armazenados de procedimentos que foram feitos para acelerar a aplicação (por exemplo, MySQL ou outro RDBMS Consulte a documentação do MySQL ). A indexação também pode estar relacionada ao armazenamento em cache, etc.

O índice invertido cria um arquivo com uma estrutura que se destina principalmente à pesquisa (texto completo).

O índice invertido consiste em dois arquivos principais:

  • Vocabulário
  • Ocorrências

No vocabulário, palavras comuns são extraídas do texto (é claro, depois de filtrar palavras da lista negra, como pronomes). O arquivo de ocorrências mantém a conexão entre palavras e documentos (palavra1 aparece em doc1 e doc2, não em doc3). É representado na forma de uma matriz.

Processo de indexação - índice invertido

Na imagem acima é mostrado o processo de criação dos dois arquivos mencionados.

Se você estiver mais interessado nesta problemática, posso recomendar um ótimo livro escrito por Ricardo Yated - Modern Information Retrieval ( Veja na Amazon ) - sobre a página 200, eu acho.

Espero que ajude :-)

Bery
fonte
Esta é uma resposta muito boa, pois explica o que realmente é um índice invertido. Supera a ideia de indexação direta e indexação inversa, que é diferente do algoritmo usado para um recurso de pesquisa que é ativado pela criação de um índice invertido.
AN6U5
6

a normalidade já diferenciou maravilhosamente entre um índice direto e um invertido, mas para a questão de por que um é chamado de índice direto e o outro de índice invertido, talvez seja por isso que eles são chamados assim ---

Tomando o exemplo de rastreamento e indexação do mecanismo de pesquisa (ou construção de índice para um livro), um índice de avanço pode ser construído simultaneamente enquanto você está rastreando as páginas da web (ou lendo o livro) ou avançando . Portanto, se você tem 10 páginas da web para rastrear (ou 10 capítulos em um livro), você pode rastrear a primeira página da web (ler o primeiro capítulo) e, em seguida, fazer uma lista de palavras que aparecem na página da web (palavras que aparecem no capítulo) e continuar esse processo para outras páginas da web (outros capítulos), então, no momento em que você rastrear todas as 10 páginas da web (leia todos os 10 capítulos), seu índice de encaminhamento estará completo com cada página da web (capítulo) apontando para uma lista de palavras que contém .

Mas para fazer um índice invertido, você precisa rastrear todas as 10 páginas da web (leia os 10 capítulos) e, em seguida, pegar cada palavra de cada lista de documentos e descobrir quais documentos contêm essa palavra. Portanto, é como voltar atrás depois de rastrear as páginas da web (leia os capítulos do livro) . Portanto, é chamado de índice invertido.

Esta é apenas minha especulação.

amor
fonte
5

Existem muitos tipos de índice. Por exemplo, B-tree, R-tree, hash ... Para diferentes propósitos, devemos escolher o índice correto.

O índice invertido é especial. Índice invertido geralmente usado no mecanismo de pesquisa de texto completo. Usando o índice invertido, podemos descobrir a localização de uma palavra em um documento (ou conjunto de documentos) o mais rápido possível. Pense no limite de memória e cpu, outro índice não pode terminar este trabalho.

Você pode ler o documento lucene para mais detalhes. É um mecanismo de busca de código aberto. http://lucene.apache.org/java/docs/index.html

virushuo
fonte
3

O termo "Índice de palavras invertidas" refere-se à mudança no relacionamento de um único documento contendo muitas palavras, para cada palavra única contendo (ou identificando) uma lista de muitos documentos. Isso é efetivamente pegar um relacionamento de um para muitos (documentos para palavras) e invertê-lo (ou revertê-lo) de forma que agora exista um novo relacionamento de um para muitos "Invertido", que é cada palavra única relacionada com muitos Documentos (ou seja, todos os que contêm essa palavra). Sua origem é realmente simples, e o termo "índice invertido" foi usado para descrever índices manuais do mesmo tipo muito antes de os computadores e a indexação eletrônica de alta velocidade sequer existirem (sim, admito, sou um programador velho, quase com idade suficiente para ter considerado Grace Hopper uma "doce jovem" idade apropriada para cortejar de volta quando COBOL era uma linguagem novinha em folha). Por favor, não descarte nossos geezers ainda, pois ocasionalmente podemos fornecer um ou dois dados históricos úteis, e possivelmente valiosos - quando nossa RAM pessoal ainda está funcionando, é claro. [sorriso]

user1009
fonte
2

em índices invertidos, temos a seguinte forma:

palavra1-> lista de documentos em que ocorre (ordem de classificação)

palavra2-> lista de documentos em que ocorre (ordem de classificação)

É muito útil para o processamento de consultas do mecanismo de pesquisa, pois nos permite encontrar os documentos em que a palavra ocorre.

Você pode usar a aprendizagem de máquina supervisionada para construir este índice invertido.

Programador
fonte
6
Isso soa como um índice para mim, o que há de invertido nisso?
guidoísmo
2
@guidoísmo Um índice invertido é a inversão de um índice direto. um índice de encaminhamento armazena uma lista de palavras para cada documento. Ex: Doc-> w1, w2
Programador
Ainda não encontrei nenhuma diferença entre o índice Forward e Inverted (em termos de como funciona, deixe o bit de nomenclatura). Tanto para mim, parece um índice que mapeia um campo para um monte de ids de documentos. Foi assim que entendi como o oracle btree (também conhecido como índice de encaminhamento) organiza os dados. Não vejo nenhuma diferença nos princípios do índice invertido. Mapear um Doc -> w1, w2, w3 parece uma proposição ineficiente para mim em termos de pesquisa. Quer saber por que isso em primeiro lugar? Isso me deixa de volta à estaca zero. :-).
user1189332
@Programmer Pergunta rápida: É prático remover entradas do arquivo de índice de encaminhamento após o índice invertido ser construído a partir dele?
Roy Lee
0

Mais uma diferença:

O tratamento de atualizações com o índice invertido é caro em comparação com o índice direto.

O índice progressivo lida com atualizações facilmente refletindo as mudanças apenas no índice do documento correspondente, enquanto no índice invertido, a mesma mudança deve refletir em várias posições no índice invertido.

Siva Kumar
fonte