Algoritmo de Boyer Moore para la búsqueda de patrones

La búsqueda de patrones es un problema importante en informática. Cuando buscamos una string en un bloc de notas/archivo de Word, navegador o base de datos, se utilizan algoritmos de búsqueda de patrones para mostrar los resultados de la búsqueda. Un enunciado de problema típico sería: 
Dado un texto txt[0..n-1] y un patrón pat[0..m-1] donde n es la longitud del texto y m es la longitud del patrón, escriba un función search(char pat[], char txt[]) que imprime todas las apariciones de pat[] en txt[]. Puede suponer que n > m. 
Ejemplos: 

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

En esta publicación, discutiremos el algoritmo de búsqueda de patrones de Boyer Moore. Al igual que los algoritmos KMP y Finite Automata , el algoritmo de Boyer Moore también preprocesa el patrón. 
Boyer Moore es una combinación de los dos enfoques siguientes. 

  1. Heurística de mal carácter 
  2. Buen sufijo heurístico 

Las dos heurísticas anteriores también se pueden usar de forma independiente para buscar un patrón en un texto. Primero comprendamos cómo dos enfoques independientes funcionan juntos en el algoritmo de Boyer Moore. Si echamos un vistazo al algoritmo Naive , desliza el patrón sobre el texto uno a uno. El algoritmo KMP realiza un preprocesamiento sobre el patrón para que el patrón pueda cambiarse en más de uno. El algoritmo de Boyer Moore realiza preprocesamiento por la misma razón. Procesa el patrón y crea diferentes arrays para cada una de las dos heurísticas. En cada paso, desliza el patrón por el máximo de las diapositivas sugeridas por cada una de las dos heurísticas. Por lo tanto, utiliza la mayor compensación sugerida por las dos heurísticas en cada paso

A diferencia de los algoritmos de búsqueda de patrones anteriores, el algoritmo de Boyer Moore comienza a buscar coincidencias desde el último carácter del patrón.
En esta publicación, discutiremos la heurística del mal carácter y la heurística del buen sufijo en la próxima publicación. 

 Heurística de mal carácter

La idea de la heurística del mal carácter es simple. El carácter del texto que no coincide con el carácter actual del patrón se denomina carácter incorrecto . En caso de desajuste, cambiamos el patrón hasta que: 

  1. el desajuste se convierte en un partido
  2. El patrón P se mueve más allá del carácter no coincidente.

Caso 1: la discrepancia se convierte en coincidencia 
Buscaremos la posición de la última aparición del carácter no coincidente en el patrón y, si el carácter no coincidente existe en el patrón, cambiaremos el patrón para que se alinee con el carácter no coincidente en el texto t 
 

Algoritmo de Boyer Moore para la búsqueda de patrones

caso 1

Explicación: En el ejemplo anterior, obtuvimos una discrepancia en la posición 3. Aquí nuestro carácter de discrepancia es «A». Ahora buscaremos la última aparición de «A» en el patrón. Obtuvimos «A» en la posición 1 en el patrón (mostrado en azul) y esta es la última vez que aparece. Ahora cambiaremos el patrón 2 veces para que la «A» del patrón se alinee con la «A» del texto.

Caso 2: el patrón se mueve más allá del carácter que no coincide 
. Buscaremos la posición de la última aparición del carácter que no coincide en el patrón y, si el carácter no existe, cambiaremos el patrón más allá del carácter que no coincide. 
 

Algoritmo de Boyer Moore para la búsqueda de patrones

caso2

Explicación: 

Aquí tenemos una discrepancia en la posición 7. El carácter «C» que no coincide no existe en el patrón antes de la posición 7, por lo que cambiaremos el patrón a la posición 7 y finalmente, en el ejemplo anterior, obtendremos una combinación perfecta de patrón (que se muestra en Verde). Estamos haciendo esto porque «C» no existe en el patrón, por lo que en cada cambio antes de la posición 7 obtendremos una discrepancia y nuestra búsqueda será infructuosa.

En la siguiente implementación, preprocesamos el patrón y almacenamos la última aparición de cada carácter posible en una array de tamaño igual al tamaño del alfabeto. Si el carácter no está presente en absoluto, puede resultar en un cambio de m (longitud del patrón). Por lo tanto, la heurística del mal carácter toma  En M)                    tiempo en el mejor de los casos. 
 

C++

/* C++ Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
 
// The preprocessing function for Boyer Moore's
// bad character heuristic
void badCharHeuristic( string str, int size,
                        int badchar[NO_OF_CHARS])
{
    int i;
 
    // Initialize all occurrences as -1
    for (i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;
 
    // Fill the actual value of last occurrence
    // of a character
    for (i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
}
 
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
void search( string txt, string pat)
{
    int m = pat.size();
    int n = txt.size();
 
    int badchar[NO_OF_CHARS];
 
    /* Fill the bad character array by calling
    the preprocessing function badCharHeuristic()
    for given pattern */
    badCharHeuristic(pat, m, badchar);
 
    int s = 0; // s is shift of the pattern with
                // respect to text
    while(s <= (n - m))
    {
        int j = m - 1;
 
        /* Keep reducing index j of pattern while
        characters of pattern and text are
        matching at this shift s */
        while(j >= 0 && pat[j] == txt[s + j])
            j--;
 
        /* If the pattern is present at current
        shift, then index j will become -1 after
        the above loop */
        if (j < 0)
        {
            cout << "pattern occurs at shift = " <<  s << endl;
 
            /* Shift the pattern so that the next
            character in text aligns with the last
            occurrence of it in pattern.
            The condition s+m < n is necessary for
            the case when pattern occurs at the end
            of text */
            s += (s + m < n)? m-badchar[txt[s + m]] : 1;
 
        }
 
        else
            /* Shift the pattern so that the bad character
            in text aligns with the last occurrence of
            it in pattern. The max function is used to
            make sure that we get a positive shift.
            We may get a negative shift if the last
            occurrence of bad character in pattern
            is on the right side of the current
            character. */
            s += max(1, j - badchar[txt[s + j]]);
    }
}
 
/* Driver code */
int main()
{
    string txt= "ABAAABCD";
    string pat = "ABC";
    search(txt, pat);
    return 0;
}
  
 // This code is contributed by rathbhupendra

C

/* C Program for Bad Character Heuristic of Boyer
   Moore String Matching Algorithm */
# include <limits.h>
# include <string.h>
# include <stdio.h>
 
# define NO_OF_CHARS 256
 
// A utility function to get maximum of two integers
int max (int a, int b) { return (a > b)? a: b; }
 
// The preprocessing function for Boyer Moore's
// bad character heuristic
void badCharHeuristic( char *str, int size,
                        int badchar[NO_OF_CHARS])
{
    int i;
 
    // Initialize all occurrences as -1
    for (i = 0; i < NO_OF_CHARS; i++)
         badchar[i] = -1;
 
    // Fill the actual value of last occurrence
    // of a character
    for (i = 0; i < size; i++)
         badchar[(int) str[i]] = i;
}
 
/* A pattern searching function that uses Bad
   Character Heuristic of Boyer Moore Algorithm */
void search( char *txt,  char *pat)
{
    int m = strlen(pat);
    int n = strlen(txt);
 
    int badchar[NO_OF_CHARS];
 
    /* Fill the bad character array by calling
       the preprocessing function badCharHeuristic()
       for given pattern */
    badCharHeuristic(pat, m, badchar);
 
    int s = 0;  // s is shift of the pattern with
                // respect to text
    while(s <= (n - m))
    {
        int j = m-1;
 
        /* Keep reducing index j of pattern while
           characters of pattern and text are
           matching at this shift s */
        while(j >= 0 && pat[j] == txt[s+j])
            j--;
 
        /* If the pattern is present at current
           shift, then index j will become -1 after
           the above loop */
        if (j < 0)
        {
            printf("\n pattern occurs at shift = %d", s);
 
            /* Shift the pattern so that the next
               character in text aligns with the last
               occurrence of it in pattern.
               The condition s+m < n is necessary for
               the case when pattern occurs at the end
               of text */
            s += (s+m < n)? m-badchar[txt[s+m]] : 1;
 
        }
 
        else
            /* Shift the pattern so that the bad character
               in text aligns with the last occurrence of
               it in pattern. The max function is used to
               make sure that we get a positive shift.
               We may get a negative shift if the last
               occurrence  of bad character in pattern
               is on the right side of the current
               character. */
            s += max(1, j - badchar[txt[s+j]]);
    }
}
 
/* Driver program to test above function */
int main()
{
    char txt[] = "ABAAABCD";
    char pat[] = "ABC";
    search(txt, pat);
    return 0;
}

Java

/* Java Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
 
 
class AWQ{
     
     static int NO_OF_CHARS = 256;
      
    //A utility function to get maximum of two integers
     static int max (int a, int b) { return (a > b)? a: b; }
 
     //The preprocessing function for Boyer Moore's
     //bad character heuristic
     static void badCharHeuristic( char []str, int size,int badchar[])
     {
 
      // Initialize all occurrences as -1
      for (int i = 0; i < NO_OF_CHARS; i++)
           badchar[i] = -1;
 
      // Fill the actual value of last occurrence
      // of a character (indices of table are ascii and values are index of occurrence)
      for (int i = 0; i < size; i++)
           badchar[(int) str[i]] = i;
     }
 
     /* A pattern searching function that uses Bad
     Character Heuristic of Boyer Moore Algorithm */
     static void search( char txt[],  char pat[])
     {
      int m = pat.length;
      int n = txt.length;
 
      int badchar[] = new int[NO_OF_CHARS];
 
      /* Fill the bad character array by calling
         the preprocessing function badCharHeuristic()
         for given pattern */
      badCharHeuristic(pat, m, badchar);
 
      int s = 0;  // s is shift of the pattern with
                  // respect to text
       //there are n-m+1 potential alignments
      while(s <= (n - m))
      {
          int j = m-1;
 
          /* Keep reducing index j of pattern while
             characters of pattern and text are
             matching at this shift s */
          while(j >= 0 && pat[j] == txt[s+j])
              j--;
 
          /* If the pattern is present at current
             shift, then index j will become -1 after
             the above loop */
          if (j < 0)
          {
              System.out.println("Patterns occur at shift = " + s);
 
              /* Shift the pattern so that the next
                 character in text aligns with the last
                 occurrence of it in pattern.
                 The condition s+m < n is necessary for
                 the case when pattern occurs at the end
                 of text */
              //txt[s+m] is character after the pattern in text
              s += (s+m < n)? m-badchar[txt[s+m]] : 1;
 
          }
 
          else
              /* Shift the pattern so that the bad character
                 in text aligns with the last occurrence of
                 it in pattern. The max function is used to
                 make sure that we get a positive shift.
                 We may get a negative shift if the last
                 occurrence  of bad character in pattern
                 is on the right side of the current
                 character. */
              s += max(1, j - badchar[txt[s+j]]);
      }
     }
 
     /* Driver program to test above function */
    public static void main(String []args) {
         
         char txt[] = "ABAAABCD".toCharArray();
         char pat[] = "ABC".toCharArray();
         search(txt, pat);
    }
}

Python3

# Python3 Program for Bad Character Heuristic
# of Boyer Moore String Matching Algorithm
 
NO_OF_CHARS = 256
 
def badCharHeuristic(string, size):
    '''
    The preprocessing function for
    Boyer Moore's bad character heuristic
    '''
 
    # Initialize all occurrence as -1
    badChar = [-1]*NO_OF_CHARS
 
    # Fill the actual value of last occurrence
    for i in range(size):
        badChar[ord(string[i])] = i;
 
    # return initialized list
    return badChar
 
def search(txt, pat):
    '''
    A pattern searching function that uses Bad Character
    Heuristic of Boyer Moore Algorithm
    '''
    m = len(pat)
    n = len(txt)
 
    # create the bad character list by calling
    # the preprocessing function badCharHeuristic()
    # for given pattern
    badChar = badCharHeuristic(pat, m)
 
    # s is shift of the pattern with respect to text
    s = 0
    while(s <= n-m):
        j = m-1
 
        # Keep reducing index j of pattern while
        # characters of pattern and text are matching
        # at this shift s
        while j>=0 and pat[j] == txt[s+j]:
            j -= 1
 
        # If the pattern is present at current shift,
        # then index j will become -1 after the above loop
        if j<0:
            print("Pattern occur at shift = {}".format(s))
 
            '''   
                Shift the pattern so that the next character in text
                      aligns with the last occurrence of it in pattern.
                The condition s+m < n is necessary for the case when
                   pattern occurs at the end of text
               '''
            s += (m-badChar[ord(txt[s+m])] if s+m<n else 1)
        else:
            '''
               Shift the pattern so that the bad character in text
               aligns with the last occurrence of it in pattern. The
               max function is used to make sure that we get a positive
               shift. We may get a negative shift if the last occurrence
               of bad character in pattern is on the right side of the
               current character.
            '''
            s += max(1, j-badChar[ord(txt[s+j])])
 
 
# Driver program to test above function
def main():
    txt = "ABAAABCD"
    pat = "ABC"
    search(txt, pat)
 
if __name__ == '__main__':
    main()
 
# This code is contributed by Atul Kumar
# (www.facebook.com/atul.kr.007)

C#

/* C# Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
 
using System;
public class AWQ{
     
    static int NO_OF_CHARS = 256;
     
    //A utility function to get maximum of two integers
    static int max (int a, int b) { return (a > b)? a: b; }
 
    //The preprocessing function for Boyer Moore's
    //bad character heuristic
    static void badCharHeuristic( char []str, int size,int []badchar)
    {
    int i;
 
    // Initialize all occurrences as -1
    for (i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;
 
    // Fill the actual value of last occurrence
    // of a character
    for (i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
    }
 
    /* A pattern searching function that uses Bad
    Character Heuristic of Boyer Moore Algorithm */
    static void search( char []txt, char []pat)
    {
    int m = pat.Length;
    int n = txt.Length;
 
    int []badchar = new int[NO_OF_CHARS];
 
    /* Fill the bad character array by calling
        the preprocessing function badCharHeuristic()
        for given pattern */
    badCharHeuristic(pat, m, badchar);
 
    int s = 0; // s is shift of the pattern with
                // respect to text
    while(s <= (n - m))
    {
        int j = m-1;
 
        /* Keep reducing index j of pattern while
            characters of pattern and text are
            matching at this shift s */
        while(j >= 0 && pat[j] == txt[s+j])
            j--;
 
        /* If the pattern is present at current
            shift, then index j will become -1 after
            the above loop */
        if (j < 0)
        {
            Console.WriteLine("Patterns occur at shift = " + s);
 
            /* Shift the pattern so that the next
                character in text aligns with the last
                occurrence of it in pattern.
                The condition s+m < n is necessary for
                the case when pattern occurs at the end
                of text */
            s += (s+m < n)? m-badchar[txt[s+m]] : 1;
 
        }
 
        else
            /* Shift the pattern so that the bad character
                in text aligns with the last occurrence of
                it in pattern. The max function is used to
                make sure that we get a positive shift.
                We may get a negative shift if the last
                occurrence of bad character in pattern
                is on the right side of the current
                character. */
            s += max(1, j - badchar[txt[s+j]]);
    }
    }
 
    /* Driver program to test above function */
    public static void Main() {
         
        char []txt = "ABAAABCD".ToCharArray();
        char []pat = "ABC".ToCharArray();
        search(txt, pat);
    }
}
 
// This code is contributed by PrinciRaj19992

Javascript

<script>
/* Javascript Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
let NO_OF_CHARS = 256;
 
// A utility function to get maximum of two integers
function max (a,b)
{
    return (a > b)? a: b;
}
 
// The preprocessing function for Boyer Moore's
// bad character heuristic
function badCharHeuristic(str,size,badchar)
{
    // Initialize all occurrences as -1
      for (let i = 0; i < NO_OF_CHARS; i++)
           badchar[i] = -1;
  
      // Fill the actual value of last occurrence
      // of a character (indices of table are ascii and values are index of occurrence)
      for (i = 0; i < size; i++)
           badchar[ str[i].charCodeAt(0)] = i;
}
 
/* A pattern searching function that uses Bad
     Character Heuristic of Boyer Moore Algorithm */
function search(txt,pat)
{
    let m = pat.length;
      let n = txt.length;
  
      let badchar = new Array(NO_OF_CHARS);
  
      /* Fill the bad character array by calling
         the preprocessing function badCharHeuristic()
         for given pattern */
      badCharHeuristic(pat, m, badchar);
  
      let s = 0;  // s is shift of the pattern with
                  // respect to text
       // there are n-m+1 potential alignments
      while(s <= (n - m))
      {
          let j = m-1;
  
          /* Keep reducing index j of pattern while
             characters of pattern and text are
             matching at this shift s */
          while(j >= 0 && pat[j] == txt[s+j])
              j--;
  
          /* If the pattern is present at current
             shift, then index j will become -1 after
             the above loop */
          if (j < 0)
          {
              document.write("Patterns occur at shift = " + s);
  
              /* Shift the pattern so that the next
                 character in text aligns with the last
                 occurrence of it in pattern.
                 The condition s+m < n is necessary for
                 the case when pattern occurs at the end
                 of text */
              //txt[s+m] is character after the pattern in text
              s += (s+m < n)? m-badchar[txt[s+m].charCodeAt(0)] : 1;
  
          }
  
          else
              /* Shift the pattern so that the bad character
                 in text aligns with the last occurrence of
                 it in pattern. The max function is used to
                 make sure that we get a positive shift.
                 We may get a negative shift if the last
                 occurrence  of bad character in pattern
                 is on the right side of the current
                 character. */
              s += max(1, j - badchar[txt[s+j].charCodeAt(0)]);
      }
}
 
/* Driver program to test above function */
let txt="ABAAABCD".split("");
let pat = "ABC".split("");
search(txt, pat);
 
// This code is contributed by unknown2108
</script>
Producción

pattern occurs at shift = 4

Complejidad de tiempo: O (nxm)

Espacio Auxiliar: O(1)

La heurística del mal carácter puede tomar  O(mn)                    tiempo en el peor de los casos. El peor caso ocurre cuando todos los caracteres del texto y el patrón son iguales. Por ejemplo, txt[] = “AAAAAAAAAAAAAAAAAA” y pat[] = “AAAAA”. La Heurística de Carácter Malo puede tomar O(n/m) en el mejor de los casos. El mejor caso ocurre cuando todos los caracteres del texto y el patrón son diferentes. 

Algoritmo de Boyer-Moore | Buen sufijo heurístico

Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *