¿Cómo indexa lucene los documentos?

95

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?

M. Amrollahi
fuente
La mayoría de las respuestas aquí son correctas en cuanto a que primero Lucene crea un índice invertido, pero eso no explica el punto clave de cómo se busca ese índice de término posteriormente (y es, creo, lo que realmente pidió el OP). Entonces, a continuación, encuentre una nueva respuesta a esta pregunta bastante antigua que, con suerte, proporcione una mejor comprensión.
fnl
1
Actualicé mi respuesta una vez más, porque las respuestas actuales (¡incluida la mía!) No son realmente satisfactorias para responder las dos preguntas principales del OP (cómo Lucene proporciona una indexación optimizada y mediante qué algoritmo en particular: una lista de omisión, no un árbol B, Por cierto). ¡Espero que mis actualizaciones finales ahora respondan correctamente a la pregunta real!
fnl

Respuestas:

54

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.

Darren
fuente
Gracias por tu respuesta y enlaces. ¿Pero escuché que el proyecto de Lucene tiene un derivador especial llamado "Snowball"? ¿Escuchaste algo sobre eso?
M.Amrollahi
Esta es una pregunta diferente: vea lucidimagination.com/search/ ... Aparte de eso, al ver su patrón de preguntas, le sugiero que lea el libro 'Lucene en acción': manning.com/hatcher2 (la primera edición está un poco anticuada, pero puede ser encontrado en una versión de árbol muerto. La segunda edición se puede comprar como un libro electrónico).
Yuval F
5
¿Puede modificar su respuesta, el primer enlace que es un enlace de IBM no se encuentra :)
Adelin
Además, ¿cómo entran los campos en la imagen completa? Si una consulta está en un campo específico, ¿cómo y en qué momento sabe lucene que el término que apunta al documento no está en ninguna parte del documento, sino dentro de un campo solicitado?
Levon Tamrazov
44

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

fnl
fuente
1
Afaik, están usando Skip List en lugar de B-tree para reducir la cantidad de búsquedas de disco, ya que la parte de Skip List reside en la memoria y muy pocas E / S de disco requieren al atravesar el índice
Anton
24

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.

Denis Bazhenov
fuente
1
Entonces, en aras de encontrar primero los resultados más actualizados, ¿comenzaría una búsqueda observando los segmentos más nuevos? Entonces, solo para aclarar, supongamos que se actualiza un documento. La versión anterior del documento se agrega a la lista de eliminación, luego cualquier coincidencia que se encuentre en segmentos más antiguos se elimina de los resultados de búsqueda si su identificación de documento coincide con una identificación en la lista de eliminación.
Joel B
2
Sí, estás en lo correcto. Lo único que hay que mencionar es que el orden final se define mediante reglas de clasificación (índice de relevancia en un caso trivial), por lo que el orden en el que se buscan los segmentos no es relevante.
Denis Bazhenov
12

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.

Insensatez
fuente
1
El índice invertido de Lucene se basa en una lista de omisión, no en un árbol B. Sigue siendo una estructura en forma de árbol en un sentido muy amplio, pero solo para ser completa, por ejemplo, vea esta pregunta SO re. El uso de Lucene de un salto-lista y esta pregunta así que por qué saltarse las listas podrían ser preferibles a los árboles B .
fnl