Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
String Matching
Leticia Blanco
Departamento de Informática - Sistemas
UMSS
16 de noviembre de 2017
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Contenido
Generalidades
Inocente
Rabin Karp
Automatas Finitos
Knuth Morris Pratt
Distancia de edición
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Generalidades
P, T cadenas texto y patron de búsqueda
P
alfabeto sobre el cual las cadenas se construyen, T y P
P
| | tamaño del alfabeto
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Generalidades
x @ y x cadena prefija de y
x A y x cadena sufija de y
Si se tiene: x A z y y A z
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Algoritmo inocente
Se busca recorriendo de uno en uno los caracteres dentro el texto:
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Algoritmo inocente
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Se utiliza propiedades de aritmetica modular, que indica que dos
numeros son equivalentes si son iguales mod un tercer numero
a ≡ b, ssi, a mod n = b mod n
Si se conoce el tamaño del patrón, se puede someter a una función
matemática que permita asociar el patrón a un número entero.
Se realiza la misma operación al texto cosniderando la cantidad de
caracteres que tiene el patrón por vez.
Usualmente se utiliza aritmetica modular para obtener números
“tratables”, entonces “mas o menos” lo que se hace es
“discretizar” el texto.
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Si el alfabeto es: A = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
El texto es: T = 2359023141526739921
El patrón a buscar es: P = 31415
Se somete el patrón a una función matemática:
P mod 13
Entonces: 31415 mod 13 ≡ 7
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Los equivalentes numerales para el texto tomados de |P| caracteres
son:
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Hay maneras rápidas de conseguir esos valores numéricos dado que
se tiene el previo, por ejemplo:
31415 mod 13 = 7
sobre esto se puede conseguir:
31415 - 30000 = 1415*10 + 2 = 14152
14152 mod 13 = 8
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
En corto, esto es:
((31415 - 10000*3)*10 + 2) mod 13
((7 - 3*10000)*10 + 2) mod 13
((7 - 3*3)*10 +2) mod 13
((-2)*10 + 2) mod 13
(11*10 + 2) mod 13
112 mod 13
8
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Verifica el resto de los valores de la tabla:
Utiliza conceptos de aritmetica modular
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Rabin-Karp
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Autómatas Finitos
Se basa en la construcción de una autómata finito determinsitico
que tome los sı́mbolos del alafabeto y sobre la base de estos se
genere el automata respectivo.
Este algoritmo lo que hace es basicamente seguir un flujo de
emparejamiento.
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Construcción de autómata
1 // p e s e l p a t r o n
2 // a l f e s e l a l f a b e t o = { c1 , c2 , c3 , c4 . . . }
3 int m = p . length () ;
4 f o r ( i n t q = 0 ; q <= m; q++)
5 for ( Character c : a l f ){
6 k = Math . min (m+1, q+2) ;
7 do{
8 k = k − 1;
9 } while ( ! s u f i j o ( subcad (p , k ) , subcad (p , q ) + c ) ;
10 autom [ q ] [ c ] = k ;
11 }
12 // r e s u l t a d o e s autom : e l automata d e l p a t r o n
13 // s u b c a d ( cad , p ) e s l a s u b c a d e n a de cad d e s d e e l
14 // primer caracter hasta e l p caracter
Complejidad: O(m3 |
P
|)
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Emparejando
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Emparejando
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Emparejando
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Automatas finitos - Emparejando
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt
Se basa en el concepto de prefijo, lo que registra es cuántos
prefijos autocontiene el Patron y su longitud. La finalidad es que
permite recorrer el emparejamiento de patron no de 1 en 1, sino
sobre la base de un arreglo de prefijos.
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Construcción de los prefijos
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Construcción del arreglo
1 // p e s e l p a t r o n
2 int m = p . length () ;
3 PI [ 1 ] = 0 ; k = 0 ;
4 f o r ( i n t q = 2 ; q <= m; q++){
5 w h i l e ( k > 0 && p [ k +1] != p [ q ] )
6 k = PI [ k ] ;
7 i f ( p [ k +1] == p [ q ] )
8 k = k + 1;
9 PI [ q ] = k ;
10 }
11 // r e s u l t a d o e s PI : e l a r r e g l o de p r e f i j o s
12 // PI [ i ] i n d i c a e l p r e f i j o a u t o c o n t e n i d o
13 // mas l a r g o h a s t a i
Complejidad: θ(m)
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Construcción de los prefijos
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Knuth-Morris-Pratt - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición
Dadas dos cadenas se requiere saber cual es la mı́nima cantidad de
operaciones de edición para que sean iguales.
Operaciones de edición: eliminar, insertar, cambiar
A esa cantidad de operaciones de edición se denomina distancia
de edición
Por ejemplo OSO y ORO tiene una distancia de edición de 1
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Algoritmo
Hay varios . . se tomará la de Neddleman Wunsch’s. Este algoritmo
considera las posibilidades de emparejamiento letra a letra (Ai , Bi ),
y asigna un “score” dependiendo de como son los caracteres:
iguales o distintos.
si Ai = Bi ==> score es + 2
si Ai <> Bi ==> score es − 1; que seria equivalente a:
cambiar Ai por Bi ,
insertar un espacio en Ai en la cadena A
eliminar Ai de la cadena A
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Algoritmo general
Realizar una matriz v que permita comparar las cadenas A y B. A
en las filas y B en las columnas.
sc(a, b) = a == b ? 2 : -1;
Base
v(0, 0) = 0
v(i, 0) = i * sc(A[i], _) // eliminar subcadena A[1..i]
v(0, j) = j * sc(_, B[j]) // insertar espacios B[1..j]
Emparejar
∀i, j/i, j > 0
opc1 = v(i-1, j-1) + sc(A[i], B[j])
opc2 = v(i-1, j) + sc(A[i], _)
opc3 = v(i , j-1) + sc(_, B[j])
v(i, j) = max(opc1, opc2, opc3)
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Ejecución
Leticia Blanco String Matching
Inocente
Rabin-Karp
Autómatas finitos
Knuth-Morris-Pratt
Distancia de Edición - Ejecución
Leticia Blanco String Matching