¿Cómo indexa lucene los documentos?

Leí un documento sobre Lucene; también leí el documento en este enlace ( http://lucene.sourceforge.net/talks/pisa ).

Realmente no entiendo cómo Lucene indexa documentos y no entiendo qué algoritmos usa Lucene para indexar.

En el enlace de arriba, dice que Lucene usa este algoritmo para indexar:

• algoritmo incremental:
  • mantener una pila de índices de segmento
  • crear índice para cada documento entrante
  • insertar nuevos índices en la pila
  • sea ​​b = 10 el factor de fusión; 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;
    }
}

¿Cómo proporciona este algoritmo una indexación optimizada?

¿Lucene usa el algoritmo B-tree o cualquier otro algoritmo como ese para indexar, o tiene un algoritmo en particular?

Hay un artículo bastante bueno aquí: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Editar 12/2014: actualizado a una versión archivada debido a que se eliminó el original, probablemente la mejor alternativa más reciente es http://lucene.apache.org/core/3_6_2/fileformats.html

Hay una versión aún más reciente en http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , pero parece tener menos información. que el más viejo.

En pocas palabras, cuando lucene indexa un documento, lo divide en varios términos. Luego almacena los términos en un archivo de índice donde cada término está asociado con los documentos que lo contienen. Podrías pensar en ello como una tabla hash.

Los términos se generan utilizando un analizador que deriva cada palabra a su forma raíz. El algoritmo de derivación más popular para el idioma inglés es el algoritmo de derivación de Porter: http://tartarus.org/~martin/PorterStemmer/

Cuando se emite una consulta, se procesa a través del mismo analizador que se usó para construir el índice y luego se usa para buscar los términos coincidentes en el índice. Eso proporciona una lista de documentos que coinciden con la consulta.

En pocas palabras, Lucene crea un índice invertido usando Skip-Lists en el disco y luego carga un mapeo para los términos indexados en la memoria usando un Transductor de Estado Finito (FST). Sin embargo, tenga en cuenta que Lucene no carga (necesariamente) todos los términos indexados en la RAM , como lo describe Michael McCandless, el autor del propio sistema de indexación de Lucene. Tenga en cuenta que al usar Listas de omisión, el índice se puede recorrer de un resultado a otro, lo que hace posibles cosas como el conjunto y, en particular, las consultas de rango (al igual que los árboles B). Y la entrada de Wikipedia sobre la indexación de listas de omisión también explica por qué la implementación de la lista de omisiones de Lucene se llama multinivelLista de omisión: esencialmente, para hacer O(log n)posibles las búsquedas (nuevamente, al igual que B-Trees).

Entonces, una vez que el índice invertido (término), que se basa en una estructura de datos de lista de omisión , se crea a partir de los documentos, el índice se almacena en el disco. Luego, Lucene carga (como ya se dijo: posiblemente, solo algunos de) esos términos en un Transductor de estado finito , en una implementación FST inspirada libremente en Morfologick .

Michael McCandless (también) hace un trabajo bastante bueno y conciso al explicar cómo y por qué Lucene usa un FST (acíclico mínimo) para indexar los términos que Lucene almacena en la memoria, esencialmente como un SortedMap<ByteSequence,SomeOutput>, y da una idea básica de cómo funcionan los FST (es decir, cómo el FST compacta las secuencias de bytes [es decir, los términos indexados] para hacer que el uso de memoria de este mapeo crezca sublineal). Y también señala el artículo que describe el algoritmo FST particular que usa Lucene.

Para aquellos curiosos de por qué Lucene usa Skip-Lists, mientras que la mayoría de las bases de datos usan (B +) - y / o (B) -Trees, eche un vistazo a la respuesta de SO correcta con respecto a esta pregunta (Skip-Lists vs.B-Trees). Esa respuesta ofrece una explicación bastante buena y profunda: esencialmente, no hace que las actualizaciones simultáneas del índice sean "más fáciles" (porque puede decidir no volver a equilibrar un árbol B inmediatamente, obteniendo así aproximadamente el mismo rendimiento simultáneo que un árbol B). Lista de omisión), sino que las listas de omisión le ahorran tener que trabajar en la operación de equilibrio (retrasada o no) (en última instancia) necesarios para los árboles B (de hecho, como muestra la respuesta / referencias, probablemente haya muy poca diferencia de rendimiento entre los árboles B y las listas de omisión [de varios niveles], si alguno de ellos se "hace bien").

Parece que su pregunta más sobre la fusión de índices que sobre la indexación en sí.

El proceso de indexación es bastante simple si ignora los detalles de bajo nivel. Lucene forma lo que se llama "índice invertido" de los documentos. Entonces, si aparece un documento con el texto "Ser o no ser" e id = 1, el índice invertido se vería así:

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

Esto es básicamente: el índice de la palabra a la lista de documentos que contienen la palabra dada. Cada línea de este índice (palabra) se denomina lista de publicación. Este índice se conserva en el almacenamiento a largo plazo.

En realidad, por supuesto, las cosas son más complicadas:

• Lucene puede omitir algunas palabras en función del Analizador particular dado;
• las palabras se pueden preprocesar utilizando un algoritmo de derivación para reducir la flexibilidad del idioma;
• La lista de publicación puede contener no solo identificadores de los documentos, sino también un desplazamiento de la palabra dada dentro del documento (potencialmente varias instancias) y alguna otra información adicional.

Hay muchas más complicaciones que no son tan importantes para la comprensión básica.

Sin embargo, es importante comprender que el índice de Lucene solo se adjunta . En algún momento, la aplicación decide confirmar (publicar) todos los cambios en el índice. Lucene finaliza todas las operaciones de servicio con index y lo cierra, para que esté disponible para la búsqueda. Después de confirmar el índice básicamente inmutable. Este índice (o parte del índice) se llama segmento . Cuando Lucene ejecuta la búsqueda de una consulta, busca en todos los segmentos disponibles.

Entonces surge la pregunta: ¿cómo podemos cambiar un documento ya indexado ?

Los documentos nuevos o las versiones nuevas de documentos ya indexados se indexan en segmentos nuevos y las versiones antiguas se invalidan en segmentos anteriores utilizando la llamada lista de eliminación . La lista de muertes es la única parte del índice comprometido que puede cambiar. Como puede imaginar, la eficiencia de los índices disminuye con el tiempo, porque los índices antiguos pueden contener en su mayoría documentos eliminados.

Aquí es donde entra en juego la fusión. Fusión: es el proceso de combinar varios índices para hacer un índice más eficiente en general. Lo que ocurre básicamente durante la fusión es que los documentos activos se copian en el nuevo segmento y los segmentos antiguos se eliminan por completo.

Con este sencillo proceso, Lucene puede mantener el índice en buena forma en términos de rendimiento de búsqueda.

Espero que te ayude.

Es un índice invertido , pero eso no especifica qué estructura usa. El formato de índice en lucene tiene información completa.
Comience con 'Resumen de extensiones de archivo'.

Primero notará que habla de varios índices diferentes. Por lo que pude notar, ninguno de estos usa estrictamente hablando un árbol B , pero hay similitudes: las estructuras anteriores se parecen a los árboles.