Como funciona o Lucene

90

Eu gostaria de saber como a pesquisa lucene funciona tão rápido. Não consigo encontrar nenhum documento útil na web. Se você tiver qualquer coisa (exceto o código-fonte lucene) para ler, me avise.

Uma consulta de pesquisa de texto usando pesquisa de texto mysql5 com índice leva cerca de 18 minutos no meu caso. Uma pesquisa lucene para a mesma consulta leva menos de um segundo.

Midhat
fonte
2
Posso solicitar que esta pergunta seja convertida em um wiki da comunidade? Lucene parece uma plataforma agora.
asyncwait

Respostas:

75

Lucene é um índice de texto completo invertido. Isso significa que ele pega todos os documentos, os divide em palavras e, a seguir, cria um índice para cada palavra . Como o índice é uma correspondência exata de string, não ordenado, pode ser extremamente rápido. Hipoteticamente, um índice SQL não ordenado em um varcharcampo poderia ser tão rápido e, de fato, acho que você descobrirá que os grandes bancos de dados podem fazer uma consulta simples de igualdade de strings muito rapidamente nesse caso.

Lucene não precisa otimizar o processamento de transações. Quando você adiciona um documento, não é necessário garantir que as consultas o vejam instantaneamente . E não precisa otimizar para atualizações de documentos existentes.

No entanto, no final do dia, se você realmente quiser saber, você precisa ler a fonte. Afinal, ambas as coisas que você faz referência são de código aberto.

bmargulies
fonte
Se bem entendi, o que diferencia os motores de busca de texto é como eles lidam com pesquisas com várias palavras e juntam os resultados das pesquisas a vários índices em tempo real. Eu não sugeriria consultar a fonte da Lucene para isso. Provavelmente seria melhor ler um pouco sobre a teoria da pesquisa de texto, a resposta de @alienCoder me ajudou.
Chris Dutrow de
1
@bmargulies, Se a indexação for "por palavra", por que a pesquisa de usuário stackoverflow stackoverflow.com/users permite correspondências de substring?
Pacerier
2
Este não é o lugar para respostas de livros inteiros. Existem inúmeras elaborações sobre o conceito básico aí.
bmargulies
O que quer dizer "um índice para cada palavra" ... se eu começar a digitar "abc", como vou encontrar "abc" no documento?
Alexander Mills
1
Um índice (árvore B) de palavra para documento pode pesquisar documentos por palavras no documento porque a tabela de tal índice é (palavra, documento) onde o índice está na coluna da palavra. Considere uma consulta como: "Encontre documentos com as palavras 'polícia', 'crime', 'estatísticas'" neles. Ao pesquisar o índice de palavras, você pode fazer três pesquisas de log (N) para obter O (N) documentos com uma dessas palavras neles. Em seguida, você pode fazer dois loops O (N) para construir um conjunto contendo documentos com todas as três palavras. Embora esta seja teoricamente uma operação O (N), a maioria dos documentos não tem todas as três palavras, então é O (n) onde n <N.
Calicoder
34

Lucene cria um grande índice. O índice contém a id da palavra, o número de documentos onde a palavra está presente e a posição da palavra nesses documentos. Portanto, quando você dá uma consulta de palavra única, ela apenas pesquisa o índice (complexidade de tempo O (1)). Em seguida, o resultado é classificado usando diferentes algoritmos. Para consulta de várias palavras, basta pegar a interseção do conjunto de arquivos onde as palavras estão presentes. Portanto, Lucene é muito rápido.

Para obter mais informações, leia este artigo de desenvolvedores do Google- http://infolab.stanford.edu/~backrub/google.html

alienCoder
fonte
8
Passei os olhos pelo papel e foi muito útil. Especificamente, "4.5 Pesquisando" tinha a resposta que eu procurava. Especificamente, parece que uma pesquisa hash O (1) é usada para palavras individuais, mas uma varredura O (n) é usada para juntar os resultados com um limite de 40.000 documentos. Presumo que um algoritmo de redução de mapa seja usado para dividir este trabalho de forma que o usuário obtenha resultados instantâneos.
Chris Dutrow de
Um algoritmo popular é o algoritmo de classificação de pombo. Embora eu não saiba muito sobre isso.
alienCoder
3
Esse artigo é engraçado: "Neste artigo, apresentamos o Google, um protótipo ...". Acho que o Google nem sempre foi uma megacorporação.
Buttons840
não conheço o Lucene, mas uma pergunta: A classificação acontece a cada pesquisa? Ou mantém os documentos pré-classificados? Se ele mantém os documentos de acordo com a classificação com antecedência, como ele mantém a consulta de várias palavras?
Vikas Prasad
O link está quebrado agora. @alienCoder
CEGRD
20

Em uma palavra: indexação.

O Lucene cria um índice do seu documento que permite uma pesquisa muito mais rápida.

É a mesma diferença entre uma estrutura de dados de lista O (N) e uma estrutura de dados de tabela hash O (1). A lista deve percorrer toda a coleção para encontrar o que você deseja. A tabela hash tem um índice que permite descobrir exatamente onde o item desejado está e simplesmente buscá-lo.

Atualizar:

Não tenho certeza do que você quer dizer com "pesquisas de índice Lucene são muito mais rápidas do que pesquisas de índice mysql."

Meu palpite é que você está usando o MySQL "WHERE document LIKE '% frase%'" para pesquisar um documento. Se isso for verdade, então o MySQL tem que fazer uma varredura de tabela em cada linha, que será O (N).

Lucene consegue analisar o documento em tokens, agrupá-los em n-gramas conforme sua orientação e calcular os índices para cada um deles. É O (1) para encontrar uma palavra em um documento Lucene indexado.

duffymo
fonte
10
Sim, eu entendo a parte de indexação, mas, novamente, as pesquisas de índice lucene são muito mais rápidas do que as pesquisas de índice mysql. Como isso acontece
Midhat
8

Lucene trabalha com frequência de termo e frequência de documento inverso . Ele cria um índice de mapeamento de cada palavra com o documento e sua contagem de frequência, que nada mais é do que o índice inverso do documento.

Exemplo :

Arquivo 1: Memória de acesso aleatório é a memória principal.

Arquivo 2: os discos rígidos são memória secundária.

Lucene cria um índice reverso parecido com

Arquivo 1:

Termo: Aleatório

Frequência: 1

Posição: 0

Termo: Memória

Frequência: 2

Cargo: 3

Cargo: 6

Portanto, é capaz de pesquisar e recuperar o conteúdo pesquisado rapidamente. Quando há muitas correspondências para a consulta de pesquisa, ele exibe o resultado com base no peso. Considere a consulta de pesquisa "Memória principal", ela pesquisa por todas as 4 palavras individualmente e o resultado seria como,

a Principal

Arquivo 1: Frequência - 1

Memória

Arquivo 1: Frequência - 2

Arquivo 2: Frequência - 1

O resultado seria Arquivo1 seguido por Arquivo2 . Para não se deixar levar por pesos nas palavras mais comuns, como 'e', ​​'ou', 'o', ele considera a frequência inversa do documento (ou seja, 'diminui o peso da palavra mais popular no conjunto de documentos).

Tom Taylor
fonte