¿Cómo lucene el índice de documentos?

Question

Leí algún 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 anterior, se dice Lucene utiliza este algoritmo para la indexación:

• algoritmo incremental:
  • mantener una pila de índices de segmento
  • crear un índice para cada documento entrante
  • insertar nuevos índices en la pila
  • dejar 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 este algoritmo optimizado proporciona la indexación?

¿Utiliza Lucene el algoritmo B-tree o cualquier otro algoritmo como el que se utiliza para indexar , o tiene un algoritmo en particular?

Answer 1

Es inverted index, pero eso no especifica qué estructura utiliza. Index format in lucene tiene información completa.
Comience con 'Resumen de extensiones de archivos'.

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

Answer 2

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

Edición 12/2014: Se ha actualizado a una versión archivada debido a la probablemente la mejor alternativa original se va a eliminar, más reciente es http://lucene.apache.org/core/3_6_2/fileformats.html

Hay una aún más reciente versión 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 el término correspondiente.) en el índice. Eso proporciona una lista de documentos que coinciden con la consulta.

Answer 3

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

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. Así que si el documento con el texto "Ser o no ser" y el id = 1 entra, índice inverso sería el resultado:

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

Ésta es básicamente - 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 basadas en el Analizador particular, dada;
• palabras pueden preprocesarse utilizando algoritmo de tallo para reducir la flexia del idioma;
• lista de publicación puede contener no solo los 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.

Es importante entender, sin embargo, 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 anteriores se anulan en los segmentos anteriores utilizando la llamada lista kill. 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.

Answer 4

En pocas palabras, Lucene construye un índice invertido usando Skip-Listsen el disco y, a continuación, carga una asignación para los términos indexadas en la memoria usando un Finite State Transducer (FST). Tenga en cuenta, sin embargo, que Lucene does not (necessarily) load all indexed terms to RAM, tal 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 que cosas como establezcan y, en particular, consultas de rango posibles (al igual que B-Trees). Y el Wikipedia entry on indexing Skip-Lists también explica por qué la implementación Skip-List de Lucene se llama multi-nivel Skip-List - esencialmente, para hacer que las búsquedas O(log n) sean posibles (de nuevo, muy parecido a B-Trees).

Entonces, una vez que el índice invertido (término) se basa en un Skip-List data structure, se genera 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 Finite State Transducer, en una implementación de FST loosely inspired por Morfologick.

Michael McCandless (también) hace un trabajo bastante bueno y conciso de explaining how and why Lucene uses a (minimal acyclic) FST para indexar los términos de las tiendas de Lucene en la memoria, esencialmente como un SortedMap<ByteSequence,SomeOutput>, y da una idea básica de cómo funcionan los FST (es decir, la forma en la FST compacta el byte secuencias [es decir, los términos indexados] para hacer que el uso de la memoria de este mapeo crezca sub-lineal). Y apunta a the paper that describes the particular FST algorithm que usa Lucene también.

Para los curiosos por qué Lucene usa Skip-Lists, mientras que la mayoría de las bases de datos usan (B +) - y/o (B) -Trees, consulte the right SO answer con respecto a esta pregunta (Skip-Lists vs. B-Trees). Esa respuesta ofrece una explicación bastante buena y profunda: esencialmente, no tanto hacen que las actualizaciones concurrentes del índice sean "más fáciles de usar" (porque puede decidir no volver a equilibrar un árbol B inmediatamente, obteniendo así el mismo rendimiento simultáneo) como una lista saliente), sino más bien, Skip-Lists le ahorra tener que trabajar en el (demorado o no) operación de balanceo (en última instancia) necesaria para B-Trees (De hecho, como la respuesta muestra/referencias , es probable que exista muy poca diferencia de rendimiento entre B-Trees y [multinivel] Omitir listas, si cualquiera de ellas está "bien hecho")