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.
- Heurística de mal carácter
- 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:
- el desajuste se convierte en un partido
- 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
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.
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 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>
pattern occurs at shift = 4
Complejidad de tiempo: O (nxm)
Espacio Auxiliar: O(1)
La heurística del mal carácter puede tomar 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