PDF de programación - Procesamiento de Cadenas - Introducción

Contenido
Introducción
Conceptos Básicos

Procesamiento de Cadenas

Introducción

H Tejeda

Facultad de Ciencias Físico Matemáticas

Universidad Michoacana de San Nicolás de Hidalgo

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Introducción

Conceptos Básicos

Paralelismo de bits y operaciones bit
Trie
Autómata
Notaciones de complejidad

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento de Cadenas

Una cadena es una secuencia de caracteres sobre un alfabeto finito Σ.
ATCTAGAGA es un cadena sobre Σ = {A, C, G, T}.
El problema de apareamiento de cadenas es encontrar todas las ocurrencias
de una cadena p, llamada patrón, en una cadena más grande T del mismo
alfabeto, llamada texto.

Dadas las cadenas x, y y z, se dice que x es:

a) un prefijo de xy,
b) un sufijo de yx,
c) y un factor de yxz.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Aproximaciones

Existen tres aproximaciones generales, dependiendo de la forma como el patrón
es buscado en el texto.

a) Se leen todos los caracteres en el texto uno después de otro y en cada paso
se actualizan algunas variables para identificar una posible ocurrencia. El
algoritmo clásico es el de Knuth-Morris-Pratt y el más rápido el Shift-Or
que puede extenderse a patrones más complicados.

b) Se busca la cadena p en una ventana que se desliza a lo largo del texto T .
Para cada posición de la ventana, se busca hacia atrás por un sufijo de la
ventana que empate con un sufijo de p. El algoritmo clásico es el de Boyer-
Moore, que es más lento que una de sus simplificaciones, Horspool y cuando
no, es más lento que las otras aproximaciones.

c) Es la más reciente y son los algoritmos más eficientes en la práctica para una
p suficientemente larga. La búsqueda es hacia atrás en una ventana, pero se
busca por el sufijo más largo de la ventana que también es un factor de p. El
primer algoritmo fue BDM, y cuando p es suficientemente pequeña lleva al
más simple y eficiente, BNDM. Para patrones grandes se emplea BOM.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento múltiple de cadenas

Un conjunto de cadenas P = p1, p2, . . . , pr puede ser buscada de la misma

forma que una sola cadena, leyendo el texto una sola vez.

Las aproximaciones para el apareamiento de una cadena se han extendido

para un conjunto de cadenas.

Para la primera aproximación esta el algoritmo Aho-Corasick y, cuando
la suma de las longitudes de los patrones, |P|, es muy pequeña, esta el
algoritmo Multiple Shift-And.

La segunda remite al algoritmo de Commentz-Walter, que no es eficiente
en la práctica, y la extensión del algoritmo de Horspool, Set Horspool,
que es eficiente para pequeños conjuntos en alfabetos grandes. El algoritmo
Wu-Manber mezcla la búsqueda de sufijos con el paradigma de hash y por
su adaptabilidad es rápido, en la práctica.

La tercera permite una extensión de BOM, SBOM, el cual se hace muy
eficiente cuando la longitud del patrón mínimo crece. El algoritmo BNDM
lleva a Multiple BNDM cuando |P| es muy pequeño.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento Extendido de Cadenas

Se consideran varias extensiones que aparecen en aplicaciones.
Todas las extensiones pueden ser convertidas en expresiones regulares, pero

algoritmos particulares más simples y rápidos existen.

La extensión más simple es la de permitir que el patrón sea una secuencia

de clases (conjuntos) de caracteres en vez de sólo caracteres.

Cualquier carácter de texto en la clase apareará con aquella posición del
patrón. Es posible que las clases aparezcan en el texto, no solamente en el
patrón.

Una segunda extensión son los huecos de longitud acotada: algunas posi-
ciones del patrón están designadas para empatar con cualquier secuencia de
texto, la cual esté entre un valor mínimo y máximo dados.

Lo anterior es de interés para las aplicaciones de biología computacional,

por ejemplo, para buscar patrones PROSITE.

Una tercera extensión es el carácter opcional que podría aparecer o no en
la ocurrencia del texto, y otra es el carácter repetido que podría aparecer
una o más veces.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento Extendido de Cadenas cont.

Los problemas de las tres extensiones y las combinaciones pueden ser re-

sueltas adaptando Shift-Or y BNDM.

Shift-Or y BNDM involucran paralelismo de bits para simular un autómata

no determinístico que encuentra todas las ocurrencias del patrón.

Se emplean autómatas más complejos y la parte medular del problema es

encontrar una forma para simularlos.

Extendiendo Shift-Or se obtiene un algoritmo que no puede saltar caracteres
de texto pero, el cual no ve afectada su eficiencia debido a la complejidad
del patrón.

Extendiendo BNDM, es más rapido pero, la eficiencia es afectada por la
longitud mínima de una ocurrencia, el tamaño del alfabeto, y el tamaño de
las clases y los saltos.

Los algoritmos clásicos no pueden ser extendidos fácilmente para obtener la

misma eficiencia.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento de Expresiones Regulares

Proporcionan una forma poderosa para expresar un conjunto de patrones de
búsqueda, conteniendo todos los tipos de problemas previamente descritos.
Una expresión regular indica cadenas simples y concatenaciones, uniones, y

repeticiones de otras subexpresiones.

Los algoritmos son más complejos y deberían ser usados solamente cuando

el problema no puede ser expresado como uno más simple.

La búsqueda de una expresión regular es un proceso multietapas.

1◦ Se analiza para obtener una representación de árbol que es más útil.
2◦ Se construye un autómata finito no determinístico NFA (nondeterministic

finite automaton) del patrón.

El NFA es una máquina de estados la cual tiene activos algunos estados que
cambian conforme se leen caracteres de texto, reconociendo ocurrencias
cuando los estados “finales” son alcanzados.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento de Expresiones Regulares cont.

Para obtener el NFA se puede usar el algoritmo de Thompson donde el
número de transiciones es proporcional a la longitud de la expresión regular,
también puede emplearse el algoritmo de Glushkov que genera un número
mínimo de estados. Ambos presentan algunas propiedades de regularidad.
El NFA puede ser empleado directamente para buscar pero, es lento porque

muchos estados pueden estar activos en algún momento.

Se puede convertir a un autómata finito determinístico DFA (deterministic

finite automaton), el cual tiene sólo un estado activo.

El DFA puede emplearse para realizar la búsqueda de expresiones regulares,
dando el algoritmo DFAClassical, su problema es que el tamaño del DFA
puede ser exponencial respecto al NFA, por lo que su uso se restringe a
patrones pequeños.

Para patrones grandes, una aproximación híbrida, DFAModules, construye

un NFA de DFAs pequeños teniendo una eficiencia razonable.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento de Expresiones Regulares cont. 2

Otra tendencia es simular el NFA usando paralelismo de bits en vez de con-
vertirlo a un DFA. Se emplea BPThompson y BPGlushkov los cuales están
basados en simular los respectivos NFAs usando sus propiedades específicas.

Se deberá usar BPGlushkov en vez de BPThompson.
Una tercera aproximación permite saltar caracteres. El algoritmo MultiS-
tringRE encuentra la longitud mínima lmin de una ocurrencia de la expre-
sión regular y computa todos los prefijos (de aquella longitud) de todas las
ocurrencias.

Entonces da una búsqueda multicadena para todas esas cadenas. Cuando

uno de esos prefijos es encontrado, este intenta completar la ocurrencia.

Una extensión es MultiFactRE, la cual selecciona un conjunto de cadenas
de longitud lmin, tal que algunas de esas cadenas deban aparecer dentro de
cualquier ocurrencia.

RegularBNDM extiende BNDM simulando el NFA de Glushkov.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Apareamiento aproximado

Es el problema de encontrar las ocurrencias de un patrón en un texto donde
el patrón y la ocurrencia podrían tener un número limitado de diferencias.
Es importante en problemas tales como: la recuperación de errores de te-
cleado o hablado al recuperar información, de alteraciones de la secuencia
o medida de errores en biología computacional, o errores de transmisión en
el procesamiento de señales.

Se modela usando una función de distancia que indica que tan similares son

dos cadenas.

Se proporciona el patrón y un borde k, la cual es la distancia máxima

permitida entre el patrón y sus ocurrencias.

La distancia de edición o de Levenshtein indica cual es el número mínimo
de inserciones de caracteres, borrados, y sustituciones necesarias para hacer
dos cadenas iguales.

H Tejeda

Procesamiento de Cadenas

Contenido
Introducción
Conceptos Básicos

Tipos de algoritmos para el apareamiento aproximado

a) Programación dinámica. Es la más vieja y todavía la más flexible, sin embargo

no es la más eficiente.

b) Convierte el problema en la salida de un NFA de búsqueda, el cual es cons-
truido como una función del patrón y k, y entonces se hace el autómata
determinístico. Se comportan razonablemente bien con patrones p