Arreglo de sufijos
Un
arreglo de sufijos es una estructura de datos utilizada para búsqueda
eficiente en textos largos. Esta estructura es un arreglo con todos los
punteros a los sufijos del texto almacenados alfabéticamente. Cada
sufijo es una termino(o cadena de caracteres) que inicia en cierta
posición en el texto y termina al final de este. Esto permite que
buscar un texto se alcance con solo ejecutar búsqueda binaria sobre el
arreglo de sufijos [5].
Para ilustrar su funcionamiento se construirá un arreglo de sufijos para”abracadabra” [5]:
El primer paso es asignar posiciones de índice al texto, donde cada
posición indica donde una búsqueda puede ser ejecutada. En este ejemplo
se tomará como sufijo cada carácter, también se incluye una pequeña
ilustración de este proceso aplicado a RI donde más bien se orienta a
términos más que a caracteres:
Arreglo de sufijos. Tomado de [5]
Arreglo de sufijos con términos. Tomado de [1]
Lo segundo es ordenar el arreglo respecto a sus sufijos alfabéticamente
Ordenamiento de sufijos. Tomado de [5]
Ordenamiento de sufijos con términos. Tomado de [1]
La siguiente imagen muestra el proceso de búsqueda para “ra”. Esto se realiza con búsqueda binaría.
Búsqueda de “ra”. Tomado de [5]
Dentro de RI sus principales utilidades pueden ser para análisis
lingüístico especializado, búsqueda de frases de varias palabras
o búsqueda de patrones que trascienda palabras [1]. En estos sentidos
es superior al índice invertido, pero no para el resto de aplicaciones
que tiene este ultimo. Para reducir el costo de búsqueda binaria en
memoria principal dentro de sistema de RI se puede utilizar supra
índices, que serian la combinación de más caracteres para ocupar menos
espacio y tener que buscar menos. Un ejemplo se muestra en la siguiente
figura:
Utilización de supra índices. Tomado de [1]
Un
aspecto importante a tomar en cuenta en la construcción de un arreglo
de sufijos para un sistema RI es que será muy costoso de construir, por
lo que se deberán utilizar técnicas división del trabajo como en la
construcción de índices invertidos. Un algoritmo que puede ser
utilizado para su construcción puede ser el siguiente [1]:
“
- Cortar el texto en bloques que se puedan indexar en memoria.
- Traerse el primer bloque, construir su arreglo y mandarlo a disco.
- Al procesar el bloque i, el invariante es que el arreglo de sufijos para los i - 1 bloques anteriores está construido.
- Traer el bloque i-´esimo y construir su arreglo de sufijos.
- Leer el texto de los i 1 bloques anteriores y buscar cada sufijo en el arreglo del bloque i-´esimo.
- Determinar cuantos sufijos del arreglo grande van entre cada par de posiciones del arreglo chico.
- Realizar el merge secuencial de los dos arreglos con esa información.