Publicado el 24 de Marzo del 2018
924 visualizaciones desde el 24 de Marzo del 2018
1,2 MB
78 paginas
Creado hace 8a (04/05/2016)
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
Comentarios de: Procesamiento de cadenas - Apareamiento de Expresiones Regulares (0)
No hay comentarios