Como lucene indexa documentos?

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?

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.

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".)

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.

É 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.