Programa Java para implementar el algoritmo de coincidencia de strings Zhu–Takaoka

El algoritmo de coincidencia de strings de Zhu-Takaoka es una variante del algoritmo de Boyer Moore para la coincidencia de patrones en una string. Hay un ligero cambio en el concepto de Bad Maps en este algoritmo. El concepto de Good Suffixes sigue siendo el mismo que el de Boyer Moore, pero en lugar de usar un solo carácter para Bad Shifts, ahora en este algoritmo, realizaremos dos turnos.

Por lo tanto, este algoritmo proporciona un poco de velocidad sobre el de Boyer. Tanto los sufijos buenos como los cambios malos de dos caracteres se pueden usar juntos en el código para dar una ventaja adicional en el rendimiento del algoritmo. Estamos discutiendo la idea de cómo cambiar el cálculo de cambios de caracteres incorrectos para este algoritmo y la idea de sufijos buenos se puede derivar del algoritmo de Boyer.

Funcionamiento de algoritmos:

Al principio, este algoritmo comienza igual que el de Boyer, es decir, compara el patrón con la string de derecha a izquierda. Por lo tanto, cada carácter del patrón se compara con el de la string de derecha a izquierda. Entonces, el índice inicial de la comparación debe ser la longitud del patrón.

String :     ABCDEFGH

Pattern:    BCD

Por lo tanto, la comparación debe comenzar en el índice de ‘C’ en la string, es decir, 2 (se usa la indexación basada en 0). Entonces, la comparación comienza en el índice = Longitud del patrón – 1. Si se encuentra una coincidencia, el índice se reduce hasta que se encuentran las coincidencias. Una vez que no se encuentra la coincidencia, es hora de hacer cambios para los personajes malos.

String :     ABCDEFGH

Pattern:    BCC

a) En el índice 2, String tiene Char ‘C’ y, dado que Pattern[2]==’C’, se encuentra una coincidencia de caracteres. Así que ahora vamos a comprobar los índices anteriores, es decir, 1, 0. Así que en la string [1] (que es igual a ‘B»), Patrón [1]! = ‘B’ Entonces no se encuentra la coincidencia y es el momento para cambiar los personajes.

Tabla de cálculo para cambios de caracteres incorrectos (denominada tabla ZTBC): esta etapa es una etapa de preprocesamiento, es decir, debe realizarse antes de comenzar las comparaciones. Las tablas de caracteres incorrectos son un mapa hash que tiene todos los alfabetos de patrón como claves y el valor representa el número de turnos que se debe dar al patrón para que:

• El desajuste se convierte en coincidencia.
• El patrón pasó ese carácter no coincidente de la string.

Entonces, en el algoritmo Zhu-Takaoka, mantenemos una array 2-D que puede dar la cantidad de cambios en función de los dos primeros caracteres de la string desde donde comenzó la comparación. Por lo tanto, aumentar el número de turnos y disminuir el número de comparaciones da como resultado un mayor rendimiento.

Procedimiento: Construcción de lógica. La idea para calcular la tabla es como se muestra a continuación: 

La tabla está hecha usando un Array 2D donde todas las columnas y filas son nombradas por el carácter de los Patrones. La tabla se inicializa con la longitud del patrón, ya que si el par de caracteres no se encuentra en el patrón, la única forma es pasar todo el patrón a través del carácter que no coincide.

If pattern is  = "ABCD"

The ZTBC =  A  B  C  D  E...

                 A  4  4  4  4  4 

                 B  4  4  4  4  4

                 C  4  4  4  4  4

                 D  4  4  4  4  4

                 E.....

Ahora, si de los dos caracteres, si el segundo es el carácter inicial del patrón, entonces cambiar todo el patrón no es la idea correcta, debemos hacer coincidir el segundo carácter con el primero del patrón. Entonces deberíamos cambiar el patrón por Len-1.

so For all i in size of array 

ZTBC[i][pattern[0]] = len-1.

so ZTBC now looks like :

ZTBC =         A  B  C  D  E....

                A   3  4  4  4  4

                B   3  4  4  4  4

                C   3  4  4  4  4

                D   3  4  4  4  4

                E.....

Ahora, si ambos caracteres se encuentran consecutivamente en el patrón, entonces deberíamos cambiar el patrón solo tanto como para que el par de caracteres en la string y el patrón coincidan.

for all i in array.size

ZTBC[pattern[i-1]][pattern[i]] = len-i-1 ; //This is the amount of shifts if two matching pair is found.

So finally ZTBC looks like

ZTBC =         A  B  C  D  E ......

                A   3  2  4  4  4

                B   3  4  1  4  4

                C   3  4  4  4  4

                D   3  4  4  4  4

                E.......

Ilustración: 

Por lo tanto, supongamos que se da una string y un patrón de la siguiente manera:

String S  = "ABCABCDE"
Pattern P = "ABCD"

Se muestra descriptivamente con la ayuda de las artes visuales a continuación de la siguiente manera:

Entonces, considerando la indexación basada en 0, comenzaremos en el índice 3

so s[3]!=P[3]  // p[3]=='D' and S[3]=='A'

Por lo tanto, ocurre un desajuste, y cambiaremos la array por 

ZTBC[C][A] since last two consecutive char is CA in string. 

Así que ahora cambiaremos el patrón por 3 

Since ZTBC[C][A] == 3, and now we are at index 6 ( 3+3 )

Y ahora deberíamos comenzar nuevamente una comparación de la string y el patrón como en el paso 1, y luego encontraríamos una coincidencia de patrón en la string, así que imprímala. Encontramos una ocurrencia. Ahora, dado que continuamos más , ahora deberíamos cambiar los dos últimos caracteres, es decir, CD en String, ya que solo están en el índice anterior. Por lo tanto, debemos cambiar nuestro patrón por 1 y continuar con el mismo proceso. Además, podemos incluir la idea de Good Suffixes en este programa para encontrar el número máximo de turnos necesarios y , por lo tanto, mejorar el rendimiento de nuestro código. La idea de Good Suffixes es la misma que la de Boyer. Por lo tanto, al presentar una fórmula general para la idea de cambio anterior, obtenemos Si se produce una falta de coincidencia en Char of String. Decir

Say S[i+m-k]!=P[m-k] //m is the size of pattern and j is the index of the start of matching .

Entonces el número del turno debe ser dado como:

ZTBC[S[i+m-2]][S[i+m-1]] // two consecutive char at the index where comparisons starts.

Ejemplo:

// Java Program to Implement Zhu–Takaoka String Matching
// Algorithm
 
// Importing required classes
import java.io.*;
import java.lang.*;
import java.util.*;
 
// Main class
public class GFG {
 
    // Declaring custom strings as inputs and patterns
    public static String string = "ABCABCDEABCDEA";
    public static String pattern = "ABCD";
 
    // And their lengths
    public static int stringlen = 14;
    public static int patternlen = 4;
 
    // Preprocessing and calculating the ZTBC for above
    // pattern by creating an integer array
 
    // As alphabets are 26 so
    // square matrix of 26 * 26
    public static int[][] ZTBC = new int[26][26];
 
    // Method
    // To calculate ZTBC to
    // print the indepattern at which the patternlenatches
    // occurs
    public static void ZTBCCalculation()
    {
 
        // Declaring variables within this scope
        int i, j;
 
        // Iterating over to compute
        // using nested for loops
        for (i = 0; i < 26; ++i)
            for (j = 0; j < 26; ++j)
                ZTBC[i][j] = patternlen;
 
        for (i = 0; i < 26; ++i)
            ZTBC[i][pattern.charAt(0) - 'A']
                = patternlen - 1;
        for (i = 1; i < patternlen - 1; ++i)
            ZTBC[pattern.charAt(i - 1) - 'A']
                [pattern.charAt(i) - 'A']
                = patternlen - 1 - i;
    }
 
    // Main driver method
    public static void main(String args[])
    {
        // Declare variables in main() body
        int i, j;
 
        // Calling the above created Method 1
        ZTBCCalculation();
 
        // Lastly, searching pattern and printing the
        // indepattern
 
        j = 0;
 
        // Till condition holds true
        while (j <= stringlen - patternlen) {
 
            i = patternlen - 1;
            while (i >= 0
                   && pattern.charAt(i)
                          == string.charAt(i + j))
                --i;
            if (i < 0) {
 
                // Pattern detected
                System.out.println("Pattern Found at "
                                   + (j + 1));
                j += patternlen;
            }
 
            // Not detected
            else
                j += ZTBC[string.charAt(j + patternlen - 2)
                          - 'A']
                         [string.charAt(j + patternlen - 1)
                          - 'A'];
        }
    }
}

Pattern Found at 4
Pattern Found at 9

Nota:

• Se encuentra que la complejidad del tiempo de ejecución es O(stringlen*patternlen) For search one y O(patterlen + (26*26)).
• Se encuentra que la complejidad espacial es O (26 × 26), que es constante casi para casos de prueba grandes.