Como lucene indexa documentos?

95

Eu li algum documento sobre Lucene; também li o documento neste link ( http://lucene.sourceforge.net/talks/pisa ).

Eu realmente não entendo como o Lucene indexa documentos e não entendo quais algoritmos o Lucene usa para indexação?

No link acima, diz que Lucene usa este algoritmo para indexação:

  • algoritmo incremental:
    • manter uma pilha de índices de segmento
    • criar índice para cada documento recebido
    • coloque novos índices na pilha
    • seja b = 10 o fator de fusão; M = 8

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

Como esse algoritmo fornece indexação otimizada?

O Lucene usa o algoritmo B-tree ou qualquer outro algoritmo parecido para indexação - ou ele tem um algoritmo específico?

M.Amrollahi
fonte
A maioria das respostas aqui estão corretas que primeiro o Lucene cria índice invertido, mas isso não explica o ponto-chave de como esse índice de termo é posteriormente pesquisado (e é, acredito, o que o OP realmente pediu). Portanto, a seguir, encontre uma nova resposta para esta questão bastante antiga que, esperançosamente, fornece uma visão melhor.
fnl
1
Atualizei minha resposta mais uma vez, porque as respostas atuais (incluindo a minha!) Não são realmente satisfatórias para responder às duas perguntas principais do OP (como o Lucene fornece indexação otimizada e por qual algoritmo específico - uma lista de pulos, não uma árvore B, BTW). Espero que minhas atualizações finais agora respondam adequadamente à pergunta real!
fnl de

Respostas:

54

Há um artigo bastante bom aqui: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Editar 12/2014: Atualizado para uma versão arquivada devido ao original ter sido excluído, provavelmente a melhor alternativa mais recente é http://lucene.apache.org/core/3_6_2/fileformats.html

Há uma versão ainda mais recente em http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , mas parece ter menos informações. do que o mais velho.

Em suma, quando lucene indexa um documento, ele o divide em vários termos. Em seguida, ele armazena os termos em um arquivo de índice, onde cada termo é associado aos documentos que o contêm. Você pode pensar nisso como um hashtable.

Os termos são gerados usando um analisador que leva cada palavra à sua forma raiz. O algoritmo de lematização mais popular para o idioma inglês é o algoritmo de lematização de Porter: http://tartarus.org/~martin/PorterStemmer/

Quando uma consulta é emitida, ela é processada por meio do mesmo analisador que foi usado para construir o índice e, em seguida, usado para pesquisar os termos correspondentes no índice. Isso fornece uma lista de documentos que correspondem à consulta.

Darren
fonte
Obrigado pela sua resposta e links. Mas ouvi dizer que o projeto Lucene tem um lematizador especial chamado "Bola de neve"? Você ouviu alguma coisa sobre isso?
M. Amrollahi,
Esta é uma pergunta diferente: Veja lucidimagination.com/search/… Fora isso, vendo seu padrão de perguntas, sugiro que você leia o livro 'Lucene em Ação': manning.com/hatcher2 (A primeira edição está um pouco desatualizada, mas pode ser encontrado em uma versão de árvore morta. A segunda edição pode ser comprada como um e-book).
Yuval F
5
Você pode modificar sua resposta, o primeiro link que é um link da IBM não foi encontrado :)
Adelin
Além disso, como os campos inserem a imagem inteira? Se a consulta está em um campo específico, como e em que ponto lucene sabe que o termo que aponta para o documento não está em qualquer lugar do documento, mas dentro de um campo solicitado?
Levon Tamrazov
44

Resumindo, Lucene constrói um índice invertido usando Skip-Lists no disco e, em seguida, carrega um mapeamento para os termos indexados na memória usando um Finite State Transducer (FST). Observe, entretanto, que o Lucene não carrega (necessariamente) todos os termos indexados na RAM , conforme descrito por Michael McCandless, o próprio autor do sistema de indexação do Lucene. Observe que, usando Skip-Lists, o índice pode ser percorrido de um hit para outro, tornando possíveis coisas como set e, particularmente, consultas de intervalo (bem como B-Trees). E a entrada da Wikipedia sobre indexação de Listas de Salto também explica porque a implementação de Lista de Saltos do Lucene é chamada de multi-nívelLista de pulos - essencialmente, para tornar O(log n)possíveis as pesquisas (mais uma vez, como as árvores B).

Assim, uma vez que o índice invertido (termo) - que é baseado em uma estrutura de dados Skip-List - é criado a partir dos documentos, o índice é armazenado no disco. Lucene então carrega (como já foi dito: possivelmente, apenas alguns desses) termos em um Transdutor de Estado Finito , em uma implementação de FST vagamente inspirada em Morfologick .

Michael McCandless (também) faz um trabalho muito bom e conciso ao explicar como e por que Lucene usa um FST (acíclico mínimo) para indexar os termos que Lucene armazena na memória, essencialmente como um SortedMap<ByteSequence,SomeOutput>, e dá uma ideia básica de como funcionam os FSTs (ou seja, como o FST compacta as sequências de bytes [isto é, os termos indexados] para fazer o uso da memória deste mapeamento crescer sublinear). E ele aponta para o artigo que descreve o algoritmo FST específico que Lucene usa também.

Para os curiosos por Lucene usa Skip-Lists, enquanto a maioria dos bancos de dados usar (B +) - e / ou (B) -Árvores, dê uma olhada a direita resposta SO sobre esta questão (Skip-Lists vs. B-Trees). Essa resposta dá uma explicação muito boa e profunda - essencialmente, não tanto torna as atualizações simultâneas do índice "mais amenas" (porque você pode decidir não reequilibrar uma B-Tree imediatamente, ganhando assim sobre o mesmo desempenho simultâneo de um Skip-List), mas sim, Skip-Lists evita que você tenha que trabalhar na operação de balanceamento (atrasada ou não) (no final das contas) necessária para as Árvores B (Na verdade, como mostra a resposta / faz referência, provavelmente há muito pouca diferença de desempenho entre as Árvores B e as Listas de Ignorar [multinível], se ambas forem "feitas da maneira certa".)

fnl
fonte
1
Afaik, eles estão usando a Lista de Pulos em vez de B-tree para reduzir o número de buscas de disco, uma vez que a parte da Lista de Pulos reside na memória e muito poucos IO de disco exigem ao atravessar o índice
Anton
24

Parece que sua pergunta é mais sobre a mesclagem de índices do que sobre a própria indexação.

O processo de indexação é bastante simples se você ignorar os detalhes de baixo nível. Lucene forma o que é chamado de "índice invertido" de documentos. Portanto, se o documento com o texto "Ser ou não ser" e id = 1 vier, o índice invertido ficará assim:

[to] → 1
[be] → 1
[or] → 1
[not] → 1

É basicamente isso - o índice da palavra à lista de documentos que contêm determinada palavra. Cada linha deste índice (palavra) é chamada de lista de postagem. Esse índice é persistido no armazenamento de longo prazo.

Na realidade, é claro que as coisas são mais complicadas:

  • Lucene pode pular algumas palavras com base no Analisador específico fornecido;
  • palavras podem ser pré-processadas usando algoritmo de lematização para reduzir flexia do idioma;
  • A lista de postagem pode conter não apenas identificadores dos documentos, mas também o deslocamento da palavra dada dentro do documento (potencialmente várias instâncias) e algumas outras informações adicionais.

Existem muitas outras complicações que não são tão importantes para o entendimento básico.

É importante entender, porém, que o índice Lucene é apenas anexo . Em algum ponto no tempo, o aplicativo decide confirmar (publicar) todas as alterações no índice. O Lucene termina todas as operações de serviço com índice e fecha-o, para que fique disponível para pesquisa. Após o índice de confirmação basicamente imutável. Este índice (ou parte do índice) é denominado segmento . Quando Lucene executa a pesquisa de uma consulta, ela pesquisa em todos os segmentos disponíveis.

Então surge a pergunta - como podemos alterar um documento já indexado ?

Novos documentos ou novas versões de documentos já indexados são indexados em novos segmentos e versões antigas invalidadas em segmentos anteriores usando a chamada lista de eliminação . A lista de eliminação é a única parte do índice confirmado que pode ser alterada. Como você pode imaginar, a eficiência do índice cai com o tempo, porque os índices antigos podem conter a maioria dos documentos removidos.

É aqui que entra a fusão. Mesclagem - é o processo de combinar vários índices para tornar o índice geral mais eficiente. O que basicamente acontece durante a mesclagem são os documentos ativos copiados para o novo segmento e os segmentos antigos totalmente removidos.

Usando este processo simples, o Lucene é capaz de manter o índice em boa forma em termos de desempenho de pesquisa.

Espero que ajude.

Denis Bazhenov
fonte
1
Portanto, para encontrar os resultados mais atualizados primeiro, uma pesquisa começaria examinando os segmentos mais recentes? Então, apenas para esclarecer - suponha que um documento seja atualizado. A versão mais antiga do documento é adicionada à lista de eliminação, então quaisquer correspondências encontradas em segmentos mais antigos são removidas dos resultados da pesquisa se o id do documento corresponder a um id na lista de eliminação.
Joel B de
2
Sim você está correto. A única coisa a mencionar é que a ordem final é definida usando regras de classificação (índice de relevância no caso trivial), portanto, a ordem em que os segmentos são pesquisados ​​não é relevante.
Denis Bazhenov
12

É um índice invertido , mas não especifica qual estrutura ele usa. Formato de índice em lucene tem informações completas.
Comece com 'Resumo das extensões de arquivo'.

Você notará primeiro que ele fala sobre vários índices diferentes. Pelo que pude notar, nenhum deles usa uma árvore B estritamente falando , mas há semelhanças - as estruturas acima se parecem com árvores.

Irracional
fonte
1
O índice invertido do Lucene é baseado em uma lista de ignorar, não em uma árvore B. Ainda é uma estrutura semelhante a uma árvore em um sentido muito amplo, mas apenas para ser completo - por exemplo, veja esta pergunta do SO. Uso do Lucene de uma lista de salto e esta pergunta SO por que pular listas pode ser preferível ao longo do B-árvores .
fnl de