Estudiante

Algoritmos de Búsqueda Secuencial de Texto

UCR – ECCI CI-2414 Recuperación de Información Prof. M.Sc. Kryscia Daviana Ramírez Benavides

Agenda
Introducción. Algoritmo Fuerza Bruta (Naive). Algoritmo Shift-Or. Algoritmo Boyer-Moore-Horspool. Conclusiones. Referencias Bibliográficas.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

2Introducción
Aunque los datos se pueden presentar de varias maneras, el texto sigue siendo la forma principal para intercambiar la información:
En la literatura o la lingüística los datos se componen de la recopilación y de diccionarios enormes. En la informática existe una gran cantidad de datos que se almacenan en archivos. En la biología molecular, las moléculas biológicas se pueden aproximar amenudo como secuencias de nucleótidos o de aminoácidos.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

3

Introducción (cont.)
Además, la cantidad de datos disponibles en estos campos tiende a duplicarse cada 18 meses. Ésta es la razón por la que los algoritmos deben ser eficientes, incluso la velocidad y la capacidad del almacenaje de computadorasaumentan regularmente. La búsqueda secuencial de texto consiste en encontrar una o, más generalmente, ocurrencias de una secuencia (generalmente llamada patrón) en un texto.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

4

Introducción (cont.)
Algoritmos más comunes:
Fuerza bruta. Familia de algoritmos de corrimiento.
Permite análisis (o búsqueda)paralelo.
Permite encontrar de una sola pasada dos ocurrencias de la subhilera ABRACADABRA en la hilera ABRACADABRACADABRA

Funciona como una máquina de estados.

Familia de algoritmos Boyer–Moore.
No analiza todos los caracteres del texto. Preprocesa el patrón a buscar para calcular saltos en el análisis (o búsqueda).

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de BúsquedaSecuencial de Texto

5

Introducción (cont.)
Todos los algoritmos que se exponen, encuentran todas las ocurrencias del patrón en el texto. El patrón se denota por x = x[0, ..., m-1]; su longitud es igual a m. El texto se denota por y = y[0, ..., n-1]; su longitud es igual a n. Ambas secuencias son estructuras sobre un sistema finito de caracteres llamado alfabeto denotado por Σ, con tamañoigual a σ.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

6

Introducción (cont.)
En cada algoritmo se presenta:
Las características principales. La descripción. El código C. El comportamiento con un ejemplo típico, donde:
x = GCAGAGAG. y = GCATCGCAGAGAGTATACAGTACG.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencialde Texto

7

Algoritmo Fuerza Bruta (Ingenuo – Naive)

Principales Características
No existe un preprocesamiento del patrón. Requiere espacio constante. Realiza siempre saltos de un carácter. Compara de izquierda a derecha. Realiza la búsqueda del patrón en un tiempo O(mn). Realiza 2n comparaciones previstas de los caracteres del texto.

UCR-ECCI CI-2414 Recuperación de InformaciónAlgoritmos de Búsqueda Secuencial de Texto

9

Descripción
No requiere ninguna fase de preproceso previo, ni un espacio extra constante además del espacio asignado al patrón y al texto. Para la búsqueda:
Consiste en la comparación de todas las posiciones del texto entre 0 y el n-m, si una ocurrencia del patrón corresponde o no. Si encuentra una no ocurrencia, o una ocurrencia total del patrón,salta un carácter hacia la derecha.

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

10

Código C

Ver Algoritmo-FB.txt

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto

11

Ejemplo

Ver Algoritmo-FB.pps

UCR-ECCI CI-2414 Recuperación de Información Algoritmos de Búsqueda Secuencial de Texto...