String Matching usando Transformada Discreta de Fourier

Notación

Considerando el problema de matching exacto de cadenas de caracteres, sean:

Planteo Formal

El problema se puede escribir como:

O bien, por conveniencia, calculamos la convergencia cuadrática (notar que no estamos elevando ambos miembros al cuadrado, sino cada término):

Desarrollando cada binomio de la sumatoria:

Multiplicando punto a punto por el arreglo t[i+k]:

Y haciendo lo propio por el arreglo p[k]:

Extendiendo con ceros el arreglo p, puedo cambiar los límites de la sumatoria:

Por asociatividad de la suma:

Aplicando la definición de convolución circular:

Sean:

Y las siguientes propiedades de la transformada discreta de Fourier:

Puedo transformar ambos miembros de la ecuación como:

Aplicando los productos puntuales en cada término:

Y aplicando la transformada inversa:

Finalmente, si se cumple esta ecuación, hay un match que comienza en la posición i de t.

Además, se observan las siguientes igualdades:

Algoritmo

A partir del planteo anterior y utilizando como primitiva una implementación de la transformada rápida de Fourier (con orden algorítmico O(N*log(N))), podemos escribir el siguiente algoritmo:

# Sea la Transformada Rápida de Fourier (Fast Fourier Transform):

Arreglo<N> FFT(Arreglo<N>)

# Se instancian los arreglos

t1, t2, t3, p1, p2, p3 = Arreglos de largo N inicializado con ceros

# Representación numérica del texto

for i in 0..N-1:

    t1[i] := Representación numérica del i-ésimo caracter del texto

    t2[i] := t1[i] * t1[i]

    t3[i] := t2[i] * t1[i]

# Representación numérica del patrón invirtiendo el dominio

for i in 0..M-1:

    p1[M-i-1] := Representación i-ésimo caracter del pattern

    p2[M-i-1] := p1[M-i-1] * p1[M-i-1]

    p3[M-i-1] := p2[M-i-1] * p1[M-i-1]

# Cálculo de las transformadas discretas de Fourier del texto

T1 := FFT(t1)

T2 := FFT(t2)

T3 := FFT(t3)

# Cálculo de las transformadas discretas de Fourier del patrón

P1 := FFT(p1)

P2 := FFT(p2)

P3 := FFT(p3)

# Productos punto a punto de las transformadas

R1 := T3 * P1

R2 := T2 * P2

R3 := T1 * P3

# Cálculo de las transformadas inversas de los productos

r1 := IFFT(R1)

r2 := IFFT(R2)

r3 := IFFT(R3)

for i in 0..N-M:

    if r1[M-1-i] - 2 * r2[M-1-i] + r3[M-1-i] == 0:

        Mostrar match en la posición i

Orden del Algoritmo

Como la FFT tiene orden O(N*log(N)), y el resto de las operaciones del algoritmo son de orden lineal, se conservará el orden de la FFT.

Ejemplo gráfico

Buscaremos la subcadena ‘ANA’ dentro de la cadena ‘BANANA’.

Tenemos entonces:

El texto representado como señal se verá como:

text.png

Y el patrón (ya invertido) como:

patt1-0.png

Las señales elevadas punto a punto al cuadrado y al cubo:

Texto

Patrón

x

text.png

patt1-0.png

x2

t2.png

p2.png

x3

t3.png

p3.png

Sus transformadas de Fourier discretas (tomo parte real para graficar en dos dimesiones):

Texto

Patrón

X1

fftt1.png

fftp1.png

X2

fftt2.png

fftp2.png

X3

fftt3.png

fftp3.png

Haciendo el producto punto a punto de las señales:

R1 = T3P1

t3p1.png

R2 = T2P2

t2p2.png

R3 = T1P3

t1p3.png

Aplicando la transformada discreta inversa de Fourier:

r1 = IDFT(R1)

r1.png

r2 = IDFT(R2)

r2.png

r3 = IDFT(R3)

r3.png

Y por último, aplicando la combinación lineal r1[i] - 2 r2[i] + r3[i] punto a punto:

result.png

Vemos que hay ceros en i=3 e i=5, lo cual quiere decir que los matches terminan en las posiciones 3 y 5 del texto (empiezan en n=3+M-1=1 y n=5+M-1=3).

Adaptaciones del Algoritmo