Indexación M. Andrea Rodríguez Tastets

DIIC - Universidad de Concepciónhttp://www.inf.udec.cl/~andrea

Introducción

Cómo recuperar información?

Una altenativa simple es buscar en todo el texto

Otra alternativa es construir estructuras de datos sobre el texto (llamdos índices) para celerar la búsqueda

Introducción

Técnicas de indexación:• Archivos invertidos• Arreglo de sufijos• Archivos de firma (signature files)

Notación

n: el tamaño del texto m: el largo del patrón v: el tamaño del vocabulario M: la cantidad de memoria principal

disponible

Inverted Files

Definición: es un mecanismo orientado a la palabra para indexar una colección de archivos.

Estructura:• Vocabulario: es un conjunto de todas las

palabras distintas en el texto • Ocurrencias: listas conteniendo toda la

información necesaria para cada palabra de vocabulario ( posición en el texto,frecuencia, documentos donde aparece,..)

Ejemoplo Texto:

Inverted file

1 6 12 16 18 25 29 36 40 45 54 58 66 70

That house has a garden. The garden has many flowers. The flowers are beautiful

beautiful

flowers

garden

house

70

45, 58

18, 29

6

Vocabulario Ocurrencias

Requerimientos de espacio

El espacio requerido para un vocabulario es más bien pequeño. De acuerdo a Heaps’ law, el vocabulario crece en un orden O(n), donde es una constante entre 0.4 y 0.6 in practica y n es la cantidad de documentos

• Las ocurrencias demandan mayor espacio. Debido a que cada palabra que aparece en el texto es referenciada una vez en la estructura, el espacio extra es O(n)

• Para reducir espacio, se usa una técnica de direccionamiento de bloque (block addressing)

Block Addressing El texto se divide en bloques Los puntos de ocurrencia son a los

bloques donde las palabras aparecen Ventajas:

• Los bloques son menores que las posiciones• Todas las referencias dentro de un bloque se

reducen a una sola ocurrencia Desventaja:

• búsqueda en línea sobre los bloques pre-seleccionados si las posiciones exactas son requeridas

Ejemplo Text:

Inverted file:

Block 1 Block 2 Block 3 Block 4

That house has a garden. The garden has many flowers. The flowers are beautiful

beautiful

flowers

garden

house

4

3

2

1

Vocabulario Ocurrencias

Búsqueda

El algoritmo de búsqeda en un archivo invertido sigue los siguientes pasos:• Búsqueda en el vocabulario• Recuperación de ocurrencias• Manipulación of ocurrencias

Búsqueda Tarea de búsqueda en archivos

invertidos siempre comienza en la vocabulario ( Es mejor tener elvocabulario en un archivo separado)

Las estructuras más usadas para el vocubulario son hashing, tries o B-trees

Una alternativa simple es mantener el vocabulario en orden (O(log v) costo )

Btree

P

C G M T X

A B N O

U V D E F J K L Q R S Y Z

Tries

19 35 45Este es un ejemplo de árboles extendidos

árboles:35a

j ejemplo:19e

x extendido:45

Construcción

Todo el vocabulario es mantenido en una estructura de datos adecuada para mantener por cada palabra una lista de ocurrencias

Cada palabra del texto es leída y buscada en el vocabulario

Si no se encuentra, se agrega con una lista de ocurrencia vacía y la nueva ocurrencia en agregada a la lista

Construcción

• Una vez el texto es revisado, el vocabulario es escrito en disco. Dos archivos son creados

• en el primer archivo, la lista de ocurrencias en almacenada contiguamente

• en el segundo, el vocabulario es almacendao en orden con un puntero a lista en el primer archivo

• El proceso tiene un tiempo en el peor caso de orden O(n)

Construcción• Una opción es usar el algoritmo previo hasta

que la memoria principal se agota. Cuando esto ocurre, el índice parcial Ii obtenido hasta ahora es grabado en disco y borrado de memoria antes de continuar con el resto del texto.

• Cuando el texto se acaba, un número parcial de índices Ii existen en disco

Ls índices parciales son mezclados para obtener el índice final

Ejemplo

I 1...8

I 1...4 I 5...8

I 1...2 I 3...4 I 5...6 I 7...8

I 1 I 2 I 3 I 4 I 5 I 6 I 7 I 8

1 2 4 5

3 6

7

final index

initial dumps

level 1

level 2

level 3

Construcción El tiempo total para generar el índice

parcial O(n) El número índices parciales O(n/M) Para mezclar los O(n/M) índices

parciales, se necesitan log2(n/M) noveles de mezcla

El costo total es de O(n log(n/M))

Arreglo de Sufijos

El índice ve el texto como una larga cadena de palabras (string). Las mayores desventajas de un arreglo de sufijo son su costo de construcción, el texto debe estar disponible al tiempo de consulta, y los resultados son entregados sin seguir el orden en el texto. Este índice puede organizar palabras y texto de caracteres.

Cada posición en el texto es vista como un sufijo (un string que va desde la posición hasta el final del texto). Sufijos partiendo de diferentes posición son siempre diferentes.

Arreglo de Sufijos: Ejemplo

4 22 37 52 62

Un texto con palabras y letras que forman párrafos.

texto con palabras y letras que forman párrafos.palabras y letras que forman párrafos.letras que forman párrafos.forman párrafos.párrafos.

Arreglo de Sufijos: Ejemplo

4 22 37 52 62

Un texto con palabras y letras que forman párrafos.

Un arreglo de suf ijos es un arreglo que contiene todos los punteros al listadode suf ijos en orden léxico.

for pal

52 37 22 62 4

Arreglo de Sujifo: Búsqueda

Para textos grandes arreglos de sufijos responden en el orden de O(log n), con n el tamaño de la base de datos textual, para búsqueda binarias.

El proceso de búsqueda es el siguiente: el patrón de búsqueda S origina dos "patrones

límites" P1 y P2 tal que cualquier sufijo es P1 S P2.

La búsqueda es binaria entre los dos patrones límites en el arreglo de sufijos.

Todas las consultas recuperan un intervalo del arreglo sufijo.

Arreglo de Sufijo: Construcción

• Se dividen los sufijos por bloques de acuerdo al orden dado por la primera letra. Luego, se sigue con la segunda letra y así. El tiempo promedio de construcción de un arreglo sufijo en memoria es O(nlog log n).

• Para texto muy largos, se construye un arreglo sufijo para un primer bloque que se combina con un segunda y con un tercero a medida que se construyen los arreglos sufijos de sucesivos bloques.

Archivos de Firmas

Los archivos signatura son estructuras de índices orientadas a la palabra basadas en hashing. Poseen un consumo extra de espacio de 10% a un 20% del texto al costo de forzar una búsqueda secuencial sobre el índice. La función hash traduce las palabras a mascaras de B bits.

Un archivo signatura divide el texto en bloques de b palabras. Para cada bloque de palabras una máscara de B bits es asignada. La máscara es asignada al "bitwise ORing" la signatura de todas las palabras en el bloque.

Archivos de Firmas

Bloque 1 Bloque 2 Bloque 3

El texto es largo. El texto es irregular, compuesto de palabras.

110101 100101 101001

Signatura de palabras:Texto: 000101Largo: 110000Irr egular: 100100Compuesto: 001001Palabras: 100001

Archivos de Firmas

El problema de este índice es cuando un máscara indica que una palabra existe aunque no se así (debido a la operación OR sobre las signaturas). Este es llamado "falso drop." La probabilidad de este error esta determinada por el tamaño B y b, es decir, por el "overhead" del sistema.

Este esquema mejora para búsqueda de frases ya que todos las palabras deben ser encontradas dentro del bloque reduciendo la probabilidad de "false drop."

Conclusiones

Archivos invertidos es probablemente el índice más adecuado para base de datos textuales

Los índices son adecuados cuando la colección de texto es grande y semi-estáctica

Si la colección de texto es volátil, búsqueda en línea es la única opción

Algunas ténicas combinan búsqueda online con indexación