Pregunta ¿Cómo lucene el índice de documentos?


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 algoritmo B-tree o cualquier otro algoritmo como ese para indexar - o tiene un algoritmo en particular?


75
2018-04-08 17:51


origen


Respuestas:


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


49
2018-04-09 13:22



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 al lista de documentos que contienen una 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 entender que el índice de Lucene es anexar solo. 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 los documentos ya indexados se indexan en segmentos nuevos y las versiones antiguas se anulan en segmentos anteriores mediante el llamado lista de muertes. 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


21
2017-10-01 01:58



En pocas palabras, Lucene construye un índice invertido usando Skip-Lists  en el discoy luego carga un mapeo para los términos indexados en la memoria usando un Transductor de estado finito (FST). Tenga en cuenta, sin embargo, que Lucene no (necesariamente) carga 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 al utilizar Skip-Lists, el índice puede atravesarse de un hit a otro, haciendo cosas como conjunto y, particularmente, consultas de rango posible (al igual que B-Trees). Y el Entrada de Wikipedia en indexación Skip-Lists también explica por qué la implementación de Skip-List de Lucene se llama multi nivel Skip-List - esencialmente, para hacer O(log n) búsquedas posibles (de nuevo, muy parecido a B-Trees).

Así que una vez que el índice invertido (término) - que se basa en una Estructura de datos Skip-List - se construye 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 libremente inspirado por Morfologick.

Michael McCandless (también) hace un trabajo bastante bueno y escueto de explicando cómo y por qué Lucene usa un FST (acíclico mínimo) para indexar los términos Lucene almacena en la memoria, esencialmente como un SortedMap<ByteSequence,SomeOutput>, y proporciona 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 se vuelva sub-lineal). Y él apunta a el documento que describe el algoritmo FST particular Lucene también lo usa.

Para los curiosos, ¿por qué Lucene usa Skip-Lists, mientras que la mayoría de las bases de datos usan (B +) - y / o (B) -Tes, eche un vistazo a el derecho Pues contesta con respecto a esta pregunta (Skip-Lists vs. B-Trees). Esa respuesta da una explicación bastante buena y profunda, esencialmente, no tanto, hacer que las actualizaciones concurrentes del índice sean "más fáciles" (porque puede decidir no volver a equilibrar un árbol B inmediatamente, obteniendo así el mismo rendimiento simultáneo que una lista saliente), sino más bien: Skip-Lists le ahorra tener que trabajar en el (demorado o no) operación de equilibrio (en última instancia) necesarios para B-Trees (De hecho, como la respuesta muestra / referencias, es probable que exista muy poca diferencia de rendimiento entre B-Trees y [multi-level] Skip-Lists, si alguno de ellos es "hecho bien").


16
2018-04-04 09:30



Es índice invertido, pero eso no especifica qué estructura usa. 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 notar, ninguno de estos usa estrictamente una B-tree, pero hay similitudes: las estructuras anteriores se parecen a los árboles.


12
2018-04-09 08:36