irmulticompression: esquema multicompresión para índices invertidos de motores de búsqueda

Este repositorio contiene el código utilizado en las experimentaciones del trabajo final de la materia Recuperación de Información (Taller Libre I) de la carrera Licenciatura en Sistemas de Información, dictada en la Universidad Nacional de Luján.

Descripción

La implementación aquí presente propone un sistema de recuperación de información (SRI) básico, que únicamente permite realizar búsquedas booleanas de tipo AND, pero que admite la compresión de un índice invertido con la posibilidad de utilizar más de una codificación tanto para el bloque de documentos, como para el de frecuencias. Este desarrollo se auxilia del submódulo ircodecs: compresión de enteros aplicada a IR (para Python) gestado en el presente trabajo.

Modo de uso

En este apartado se exponen los pasos necesarios para la puesta en marcha del SRI, desde el proceso de indexación de un corpus, hasta el de recuperación (o búsqueda). A tal efecto, y en primer lugar, se requieren los siguientes imports:

from lib.browser import Browser, BrowseType
from lib.index.indexer import Indexer, CorpusTypes, IndexerStatusTypes
from lib.index.compression.ircodecs import EncodeTypes

Indexación

El indexador debe inicializarse con la siguiente sentencia:

indexer = Indexer(dirin, CorpusTypes.Text, reuse_tmp=True)

Para el caso, el primer parámetro del constructor refiere al directorio del corpus, el segundo a su tipo (Text o Trec), mientras que el tercero indica si se deben utilizar los archivos temporales producto de (dado el caso) una indexación anterior. Tener en cuenta que, por defecto, el proceso de indexación genera 4 subíndices temporales, haciendo uso de 2 hilos: esto puede ser modificado desde el archivo indexer.py, mediante las variables MAX_CHILD_INDEXERS y RESOURCES_FACTOR. A su vez, es posible definir el o los códecs a utilizar en el bloque de frecuencias y/o de documentos, que deben ser especificados con un objeto lista donde cada elemento debe ser del tipo EncodeTypes:

indexer.doc_encode = [EncodeType_1, ..., EncodeType_n]
indexer.freq_encode = [EncodeType_1, ..., EncodeType_n]

Los tipos posibles de códecs son: PForDelta, Simple16, VariableByte, BitPacking, Gamma, Unary y EliasFano. En caso de definir más de un método de compresión, el indexador utilizará el que menos cantidad de bits genere. Si más de un códec genera la cantidad de bits mínima, para la elección se tendrá en cuenta el siguiente criterio de orden: PForDelta, Simple16, VariableByte, Empaquetado binario, Gamma, Unario, Elias Fano. Por defecto, se utiliza Variable Byte en ambos bloques. Ejemplos:

Un único método de compresión:

indexer.doc_encode = [EncodeTypes.VariableByte]
indexer.freq_encode = [EncodeTypes.Unary]

Más de un método de compresión:

indexer.doc_encode = [EncodeTypes.VariableByte, EncodeTypes.PForDelta]
indexer.freq_encode = [EncodeTypes.Gamma, EncodeTypes.Unary]

Para iniciar el proceso de indexación se debe invocar al método create_index(string, bool, int), indicando directorio de salida. Alternativamente es posible especificar si debe sobre-escribirse el índice en caso de haber sido creado previamente y el tamaño de partición (chunk) a utilizar para cada una de las listas invertidas. Nota: por defecto, el valor del parámetro de chunk es 0 (cero), lo cual indica que las listas no se deben particionar.

index, status = indexer.create_index(dirout, False, 128)

Al finalizar el proceso de indexación el método create_index(string, bool, int) retorna el índice correspondiente junto a uno de tres estados:

• Already_Indexed, que (sólo en caso de que la opción de sobre-escritura sea falsa) indica que el índice especificado para el corpus ya ha sido creado previamente.
• Ok, que especifica que la indexación se llevó a cabo correctamente.
• Collection_Non_Existent, que indica que la colección con la que se ha inicializado el indexador no existe. Para el caso, el índice retornado es nulo.

Por otro lado, en la carpeta other del directorio de salida, se genera un archivo de nombre status.txt que indica el tiempo empleado para el proceso de merge del índice y los tamaños (en MiB) de los archivos generados. En caso de especificarse más de un códec en el bloque de documentos o de frecuencias se generan, respectivamente, los archivos 'encoder_docs_statistics.txt' y 'encoder_freqs_statistics.txt': cada uno contiene las listas invertidas raws (crudas) del índice donde, para cada una, se especifica también el término correspondiente y el códec utilizado.

Archivos generados en la indexación

Cada índice creado se compone de 4 archivos:

• Colección (collection.txt), que mapea cada identificador de documento con su nombre.
• Vocabulario (vocabulary.txt) que, por cada término, almacena un apuntador a su información de chunks.
• Información de chunks (chunksinfo.bin), que contiene los datos necesarios para accesar las listas invertidas de cada término (por ejemplo, apuntadores a particiones, códecs utilizados, etc).
• Postings (postings.bin) que, por cada chunk de término, almacena el bloque de documentos y de frecuencias correspondientes.

Carga de índice

Luego del proceso de indexación, se debe proceder con la carga del índice mediante el método load(bool). La carga puede realizarse en dos modalidades, dependiendo del valor del parámetro chunks_info_in_memory: si este es True, el archivo de información de chunks se carga en memoria RAM; y, en caso de ser False, este archivo se lee directamente desde disco conforme se requieran resolver las consultas.

index.load(False)   # Carga de índice sin información de chunks en RAM.

Finalmente, debe inicializarse el buscador mediante las siguientes sentencias de ejemplo:

browser = Browser(index, BrowseType.Boolean)    # Índice y tipo de búsqueda.
text = input()                                  # Texto a buscar.
doc_ids = browser.browse(text.lower().strip())  # Docids resultado de la búsqueda.

Nota: sólo se encuentra implementada la búsqueda booleana de tipo AND.

Scripts de ejemplo

La carpeta test contiene el archivo de ejemplo main.py, que construye dos índices en base al corpus del directorio resources/collections/T12012-gr. Por otro lado, el archivo simplebrowsetest.py permite realizar búsquedas de prueba en el primer índice generado, mientras que comparebrowsetest.py, permite comparar los resultados de búsqueda de ambos índices (que debieran ser iguales independientemente de los métodos de compresión utilizados).

Analizadores

En la carpeta analyzers pueden encontrarse 4 scripts, que se corresponden con los análisis realizados en el trabajo:

• Analizador de frecuencias (freqsanalyzer.py) que, en base al archivo encoder_freqs_statistics.txt, permite analizar la distribución de frecuencias de un corpus.
• Analizador de velocidad de recuperación (indexqueryanalyzer.py), que permite computar la velocidad de recuperación de los índices generados, en dos modalidades: con la carga de información de chunks en RAM y con la lectura de esta desde disco.
• Analizador de tamaño de índices (indexsizeanalyzer.py), que computa el tamaño de cada uno de los archivos generados para cada índice.
• Analizador de estadísticas de multicompresión (multiencodeanalyzer.py), que permite analizar los archivos encoder_docs_statistics.txt y encoder_freqs_statistics.txt generando las siguientes estadísticas: tamaño promedio de lista invertida (del corpus) y primer número, distancia promedio, tamaño y cantidad de listas invertidas por cada códec.

Requerimientos

Se requiere el lenguaje de programación Python v3. Además, luego de la operación de clone del repositorio, es necesaria la carga del submódulo ircodecs con la siguiente secuencia de comandos:

$ git submodule init
$ git submodule update

Autor

Agustín González