PDF de programación - Procesamiento de cadenas - Apareamiento de Expresiones Regulares

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Procesamiento de cadenas

Apareamiento de Expresiones Regulares

H Tejeda

Facultad de Ciencias Físico Matemáticas

Universidad Michoacana de San Nicolás de Hidalgo

H Tejeda

Apareamiento de expresiones regulares

1/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Conceptos básicos

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Aproximaciones clásicas para búsqueda de expresiones regulares

Simulación del AFN de Thompson
Autómata determinístico
Aproximación híbrida

Algoritmos de paralelismo de bits

Thompson con paralelismo de bits
Glushkov con paralelismo de bits

Aproximaciones por filtración

Aproximaciones por filtración
Aproximación de apareamiento de multicadenas
Factores necesarios
Aproximación basada en BNDM

Mapa Experimental

Otros algoritmos y referencias

H Tejeda

Apareamiento de expresiones regulares

2/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Conceptos básicos

Las expresiones regulares son usadas en la recuperación de texto o aplica-
ciones de biología computacional porque representan patrones de búsqueda
más complejos que una cadena, un conjunto de cadenas, o una cadena
extendida.

Definición. Una expresión regular ER es una cadena sobre el conjunto de
símbolos Σ ∪ {ε,|,·,∗, (, )}, la cual está definida recursivamente como la
cadena vacía ε; un caracter α ∈ Σ; y ( ER1 ), (ER1 · ER2), (ER1|ER2),
y (ER1∗), donde ER1 y ER2 son expresiones regulares.

Por ejemplo, la expresión regular (((A · T)|(G · A)) · A · G)|((A · A) · A))∗)). Cuan-

do no haya ambig¨uedad, se simplifica la expresión escribiendo ER1ER2 en
vez de (ER1 · ER2). De esta forma se obtiene una expresión más legible,
teniendo en este caso (AT|GA)((AG|AAA)∗).

Para retirar paréntesis se usa el siguiente orden de precedencia “∗”,“·”,“|”.
Los símbolos “∗”, “·”, “|” son llamados operadores. Se acostumbra agregar

un operador posfijo “+” equivalente a ER+ = ER · ER∗.

H Tejeda

Apareamiento de expresiones regulares

3/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Lenguaje representado por una expresión regular

Definición. El lenguaje representado por una expresión regular ER es un
conjunto de cadenas sobre Σ, el cual está definido recursivamente en la
estructura de ER como sigue:

Si ER es ε, entonces L(ER) = {ε}, la cadena vacía.
Si ER es α ∈ Σ entonces L(ER) = {α}, una cadena de un sólo carácter.
Si ER es de la forma ( ER1 ), entonces L(ER) = L(ER1).
Si ER es de la forma (ER1 · ER2), entonces L(ER) = L(ER1)· L(ER2),
donde W1 · W2 es el conjunto de cadenas w tales que w = w1w2, con
w1 ∈ W1 y w2 ∈ W2. El operador “·” representa la concatenación clásica de
cadenas.
Si ER es de la forma (ER1|ER2), entonces L(ER) = L(ER1)∪ L(ER2),
la unión de los dos lenguajes. Se llama al símbolo “|” operador unión.
i≥0 L(ER1)i,
donde L0 = ε y Li = L · Li−1 para cualquier L. El resultado es el conjunto
de cadenas formadas por una concatenación de cero o más cadenas represen-
tadas por ER1. Se llama a “∗” el operador estrella.

Si ER es de la forma (ER1∗), entonces L(ER) = L(ER)∗ =

H Tejeda

Apareamiento de expresiones regulares

4/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Ejemplo de expresión regular

L((AT|GA)((AG|AAA)∗)) = {AT, GA, ATAG, GAAG, ATAAA, GAAAA, ATAGAG,

ATAGAAA, ATAAAAG, ATAAAAAA, GAAGAG, GAAGAAA, . . .}.

De acuerdo a la definición del operador estrella, Σ∗, denota el conjunto de

todas las cadenas sobre el alfabeto Σ.

El tamaño de una expresión regular ER es el número de carácteres de Σ
dentro de esta. Por ejemplo, el tamaño de (AT|GA)((AG|AAA)∗) es 9. Las
complejidades de los algoritmos que se verán están basadas en esta medida.
El problema de búsqueda para una expresión regular ER en un texto T es

encontrar todos los factores de T que pertenecen al lenguaje L(ER).

H Tejeda

Apareamiento de expresiones regulares

5/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Aproximación clásica

La siguiente figura resume la aproximación clásica. La expresión regular es
primero analizada en un árbol de expresión, la cual es transformada en un
Autómata Finito No Determinístico, AFN, en varias formas posibles.

Se presentan dos construcciones AFN, que son las más interesantes en la

práctica, la construcción de Thompson y la de Glushkov.

H Tejeda

Apareamiento de expresiones regulares

6/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Estrategias de búsquedas usando autómatas

Es posible buscar directamente con el AFN, y hay varias formas de hacerlo,
pero el proceso es muy lento. El algoritmo consiste en guardar una lista
de estados activos y actualizar la lista cada vez que un nuevo caracter es
leído. El tiempo de búsqueda en el peor caso es O(mn), pero requiere poca
memoria.

Otra aproximación es convertir el AFN en un autómata Finito Determinísti-
co, AFD, lo cual permite tiempo O(n) en búsqueda haciendo una transición
directa por carácter de texto pero, el tiempo y espacio en la construcción
del autómata en el peor caso es O(2m).

H Tejeda

Apareamiento de expresiones regulares

7/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Búsqueda con apareamiento múltiple de patrones

Una tercera estrategia es filtrar el texto usando apareamiento múltiple de
patrones o herramientas relacionadas, como encontrar anclas alrededor de
donde podría haber una ocurrencia, y entonces localmente verificar una
posible ocurrencia usando una de las estrategias previas. La siguiente figura
ilustra el esquema descrito.

Estas estrategias pueden combinarse. Por otra parte, el uso de paralelismo

de bits puede acelerar algunas partes del proceso de búsqueda.

H Tejeda

Apareamiento de expresiones regulares

8/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Representación de árbol

La mayoría de las construcciones de autómatas usan una representación de

árbol de la expresión regular ER para realizar los cálculos.

Las hojas del árbol están etiquetadas con los carácteres de Σ de la ER y

también con los símbolos de ε, si los hay.

Los nodos internos están etiquetados con los operadores. Los nodos que
están etiquetados con “|” o “·” tienen dos hijos que representan las subex-
presiones ER1 y ER2. Los nodos etiquetados por “∗” tienen un hijo único
representando ER1.

La representación de árbol usualmente no es la única, ya que algunos ope-

radores son conmutativos y/o asociativos.

H Tejeda

Apareamiento de expresiones regulares

9/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Representación de árbol de la ER (AT|GA)((AG|AAA)∗)

En representaciones de árbol, se asume que · (vl, vr) significa un árbol de
concatenación con raíz “·” e hijos vl y vr. | (vl, vr) es el árbol enraízado
con “|”. El símbolo * (v∗) es un nodo “∗” con un hijo único v∗.

H Tejeda

Apareamiento de expresiones regulares

10/77

Contenido
Conceptos básicos
Aproximaciones clásicas para búsqueda de expresiones regulares
Algoritmos de paralelismo de bits
Aproximaciones por filtración
Mapa Experimental

Análisis de una expresión regular
Analizador básico recursivo
Autómata de Thompson
Autómata de Glushkov

Análisis de una expresión regular para hallar su árbol

En general el árbol no es único. En el árbol, cada hoja está etiquetada por
un caracter de Σ ∪ {ε} y cada nodo interno por un operador del conjunto
{|,·,∗}

La aproximación general es tratar una expresión regular como una cadena
generada por una gramática, y entonces usa