ConstrucciÓN DE ÍNDICES INVERTIDOS
De manera general los pasos para la construcción del índice son [1, 2]:
- Procesar el texto (Extraer los términos).
- Se busca en el vocabulario si el termino ya esta, si no se encuentra se agrega una nueva entrada para el termino y se agrega su documento a su lista de posteo.
- Si el término ya esta en el vocabulario, entonces únicamente se agrega el documento a lista de posteo del término.
- Luego se graba el índice en disco.
Los
pasos anteriores son muy generales y presentan variación según el
modelo y la técnica utilizada para su construcción. Por ejemplo para el
modelo vectorial también es necesario ir incluyendo el idf y frecuencia normalizada para cada término, además de ir ordenando los documentos en orden de esta ultima.
Un aspecto importante a tomar en cuenta en la construcción de índices
es el hecho de que será muy difícil que todo el índice quepa en memoria
principal. Por este motivo lo que generalmente se hace es crear índices
parciales y guardarlos en disco, y una vez que todos se han completado
se hace un merge entre ellos para crear un único índice total. Esta técnica también es útil para actualizar el índice.
Siguiendo con la idea anterior, una técnica muy utilizada en la
creación de índices es construcción por bloques. Un algoritmo popular
es el SPIMI o single-pass in-memory indexing [2]. Este algoritmo es presentado en la siguiente imagen:
Algoritmo SPIMI .Tomado de [2]
La idea básica del algoritmo es la siguiente [2]:
- El índice principal se creará a partir de bloques de igual tamaño. Cada bloque tendrá su propio vocabulario (el cual es comúnmente implementado como una tabla Hash) y su propia lista de posteo para cada término del vocabulario correspondiente a ese bloque.
- De igual manera que el algoritmo general, cada termino es agregado al vocabulario del bloque actual y los documentos a los cuales pertenece también son agregados a su lista de posteo. Si el tamaño del la lista de posteo no es suficiente, entonces esta es doblada.
- Una vez que la memoria para el bloque se acaba, se ordenan los términos y el bloque es escrito en disco duro y un nuevo bloque es creado para seguir con el procesamiento de la colección.
- Una vez que todos lo bloques han sido escritos en disco duro, se procede a realizar un merge entre todos los bloques, que a manera de aclaración incluye tanto a los términos del vocabulario como a las listas de posteo.
Merge de bloques en el SPIMI . Tomado de [2]