algorithm - ¿Cómo lucene el índice de documentos?

indexing

Question

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

Realmente no entiendo cómo Lucene indexa los documentos y no entiende 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 segmentos
  • crear índice para cada documento entrante
  • empujar nuevos índices en la pila
  • deje b = 10 ser 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 indexación optimizada?

¿Utiliza Lucene el algoritmo del árbol B o cualquier otro algoritmo como ese para indexar, o tiene un algoritmo en particular?

Answer 1

En pocas palabras, Lucene construye 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 a la RAM , como lo describe Michael McCandless, el autor del sistema de indexación de Lucene. Tenga en cuenta que mediante el uso de listas salteadas, el índice puede atravesarse de un hit a otro, haciendo posibles cosas como establecer y, en particular, consultas de rango (al igual que B-Trees). Y la entrada de Wikipedia en la indexación de Skip-Lists también explica por qué la implementación Skip-List de Lucene se denomina Skip-List de niveles múltiples , esencialmente, para hacer búsquedas O(log n) posibles (una vez más, como B-Trees).

De modo que una vez que el índice invertido (término) se basa en una estructura de datos Skip-List , se crea a partir de los documentos, el índice se almacena en el disco. Lucene carga (como ya se dijo: posiblemente, solo algunos de) esos términos en un Transductor de Estado Finito , en una implementación de FST ligeramente inspirada por Morfologick .

Michael McCandless (también) hace un trabajo bastante bueno y escueto 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 SortedMap<ByteSequence,SomeOutput> , y da una idea básica para cómo funcionan los FST (es decir, cómo el FST compacta las secuencias de bytes [es decir, los términos indexados] para que el uso de la memoria de este mapeo se vuelva sub-lineal). Y señala el documento que describe el algoritmo FST particular que usa Lucene también.

Para aquellos curiosos por qué Lucene usa Skip-Lists, mientras la mayoría de las bases de datos usan (B +) - y / o (B) -Tes, eche un vistazo a la respuesta SO correcta con respecto a esta pregunta (Skip-Lists vs. B-Trees). Esa respuesta ofrece una explicación bastante buena y profunda: esencialmente, no tanto hace que las actualizaciones concurrentes del índice sean "más fáciles" (porque puede decidir no volver a equilibrar un árbol B inmediatamente, obteniendo de ese modo el mismo rendimiento simultáneo que un Skip-List), sino que Skip-Lists le evita tener que trabajar en la operación de balanceo (retardada o no) (en última instancia) que necesitan los B-Trees (De hecho, como la respuesta muestra / referencias, es probable que haya muy poca la diferencia de rendimiento entre B-Trees y [multi-level] Skip-Lists, si cualquiera de ellas es "correcta").

Answer 2

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 archivos''.

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

Answer 3

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 que tiene menos información. que el anterior.

En pocas palabras, cuando lucene indexa un documento, lo descompone en una serie de 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 que es un poco como una tabla hash.

Los términos se generan usando 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 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.

Answer 4

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

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. Por lo tanto, si aparece el documento con el texto "Ser o no ser" y la id = 1, el índice invertido se vería así:

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

Esto es básicamente eso: el índice de la palabra a la lista de documentos que contiene la palabra dada. Cada línea de este índice (palabra) se llama lista de publicación. Este índice persiste en el almacenamiento a largo plazo en ese momento.

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

• Lucene puede omitir algunas palabras según el Analizador dado;
• las palabras pueden ser preprocesadas usando un algoritmo de derivación para reducir la flexia del idioma;
• La lista de publicación puede contener no solo identificadores de los documentos, sino también el 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 agrega . En algún momento, la aplicación decide comprometer (publicar) todos los cambios en el índice. Lucene finaliza todas las operaciones de servicio con índice y lo cierra, por lo que está disponible para realizar búsquedas. Después de comprometer 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 el 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 mediante la llamada lista de eliminación . La lista de asesinatos es la única parte del índice comprometido que puede cambiar. Como puede imaginarse, la eficiencia del índice disminuye con el tiempo, porque los índices antiguos pueden contener documentos eliminados en su mayoría.

Aquí es donde entra en juego la fusión. Fusionar: es el proceso de combinar varios índices para hacer un índice más eficiente en general. Lo que básicamente sucede durante la fusión es copiar documentos en vivo en el segmento nuevo y eliminar segmentos antiguos por completo.

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

Espero que ayude