Uso del algoritmo de coincidencia de cadenas (sin terminar)
La diferencia entre monomodo y multimodo es si se pueden encontrar todas las cadenas multimodo atravesando la cadena principal a la vez.
El nombre completo en inglés es Brute Force, un algoritmo de coincidencia de fuerza bruta. El método de coincidencia de cadenas es fuerza bruta y fácil de entender. La idea general es:
Podemos ver que en el caso extremo, si busca la cadena de patrón aab...aab en la cadena principal aaaa, entonces el total * * * necesita buscar (n-m 1) veces, cada vez que es necesario comparar m veces, entonces la complejidad del tiempo es (n-m 1) * m, que es O (n * m). Pero, de hecho, no será tan ineficiente, porque la cadena principal y la cadena de patrón en nuestro escenario de uso no serán demasiado largas, y al comparar cada subcadena y cadena de patrón, siempre que haya una discrepancia en el medio, la comparación actual Será Terminará temprano, por lo que en la mayoría de los casos la complejidad del tiempo será mejor que O (n * m).
Introdujimos el algoritmo hash basado en el algoritmo BF. En lugar de comparar cada subcadena carácter por carácter con el patrón, calculamos el hash de cada subcadena y luego lo comparamos con el hash del patrón. Si son iguales, significa que hay una subcadena que coincide con la cadena del patrón.
Aunque solo necesitamos comparar el valor hash de la cadena del patrón y la subcadena para obtener el resultado coincidente, el número de veces es (n-m 1), pero al calcular el hash de cada subcadena, necesitamos para atravesar cada carácter, por lo que el número de veces También es m, por lo que la complejidad del tiempo total sigue siendo O (n * m), lo que no se ha mejorado significativamente.
Entonces, ¿cómo podemos encontrar una manera de mejorar el tiempo de cálculo de cada valor hash de subcadena? Ésta es la esencia del algoritmo RK. Supongamos que el número de elementos en el juego de caracteres contenidos en la subcadena es K, luego la subcadena se representa mediante un número de base K y luego el proceso de hash consiste en convertir el número de base K en un número decimal. es el valor hash de la subcadena.
Los hashes de subcadenas adyacentes se calculan periódicamente. Solo necesitamos recorrer la cadena principal una vez para obtener los valores hash de todas las subcadenas. La complejidad del algoritmo es O (n), en lugar de la complejidad temporal original de cada subcadena, que es O (m).
El hash de la cadena del patrón luego se compara con los hash de todas las subcadenas. La complejidad temporal de cada comparación es O (1) y el número total de comparaciones es * * * (n-m 1), por lo que la sobrecarga de tiempo total del algoritmo RK es O (n) O (1) * O (n-m) .
Por supuesto, donde hay hashes, puede haber conflictos de hashes. Es posible que la subcadena y el valor hash sean los mismos que el valor hash de la cadena del patrón, pero el contenido sea diferente. ¿Qué debo hacer en este momento? En realidad es muy simple. Para subcadenas con el mismo valor hash, puede agregar un seguro doble para comparar si los caracteres M son iguales. El costo de tiempo total es O(n) O(1)* O(n-m 1) O(m), que es O(n).
¿Qué debo hacer si hay muchas colisiones de hash en casos extremos? Necesitamos comparar cada subcadena con el mismo valor hash que la cadena del patrón una por una, por lo que el costo de tiempo total será O(n) O(1)* O(n-m 1) O(m)* O(n-m 1) , Es decir, O (n *)
Al buscar y reemplazar cadenas en un editor de texto real, el algoritmo utilizado no es ni el algoritmo BF ni el algoritmo RK. El algoritmo BF solo es adecuado para cadenas principales que no son muy largas, mientras que el algoritmo RK requiere diseñar un algoritmo hash con una baja probabilidad de colisión, lo cual es relativamente difícil, por lo que en realidad utiliza el algoritmo BM, que es una coincidencia de cadenas muy común. Algoritmo en ingeniería. Máxima eficiencia.
La idea y el proceso del algoritmo son algo complicados y se resolverán más adelante.
El algoritmo KMP es esencialmente el mismo que el algoritmo BM. La idea y el proceso del algoritmo son algo complicados y se analizarán más adelante.
¿Cómo se implementa la coincidencia de entrada inteligente en el cuadro de entrada del navegador y cómo realiza una búsqueda dinámica de coincidencia de cadenas? Esto utiliza un árbol Trie.
El árbol de diccionario, también conocido como árbol de diccionario, es una estructura de árbol especialmente utilizada para encontrar rápidamente resultados coincidentes de prefijos de cadenas. Su esencia es combinar los prefijos repetidos de todas las cadenas para construir un árbol de múltiples ramas.
Entre ellos, el nodo raíz no contiene ninguna información, cada nodo representa un carácter y la ruta desde el nodo raíz al nodo rojo representa una cadena almacenada. Cuando buscamos "él" en el árbol Trie de arriba, encontramos que "él" no es una cadena, sino el prefijo común de "Hola" y "Ella", luego encontraremos estas dos cadenas y las devolveremos.
¿Cómo se almacenan los árboles en la memoria? Debido a que cada nodo puede contener todos los caracteres, cada nodo es una matriz (o tabla hash) que almacena punteros a cada carácter y sus nodos sufijos.
Usando un árbol Trie, al comienzo de la construcción, la complejidad del tiempo es O (n), donde n es la suma de las longitudes de todas las cadenas, pero una vez que se completa la construcción, las consultas frecuentes de una cadena es muy eficiente y el tiempo es La complejidad es O (k), donde k es la longitud de la cadena de búsqueda.
Aunque el árbol Trie tiene una alta eficiencia de consulta, desperdicia memoria. Cada nodo debe mantener una matriz para almacenar todos los datos de caracteres posibles y punteros al siguiente nodo, por lo que cuando no hay muchos prefijos comunes para todas las cadenas, el desperdicio de espacio de memoria es aún mayor. De hecho, existe una solución correspondiente a este problema. No podemos usar matrices, pero usamos matrices ordenadas, tablas hash y árboles rojo-negro para el almacenamiento, lo que puede reducir el rendimiento y ahorrar espacio en la memoria en consecuencia.
Los árboles Trie no solo pueden realizar la función de ingresar contenido dinámicamente para buscar candidatos en el navegador, sino que también pueden realizar la función de coincidencia de palabras sensibles multimodo. Supongamos que necesitamos verificar las palabras confidenciales ingresadas por el usuario y reemplazar todo el contenido confidencial con * * *, entonces, ¿cómo lograr esto?
En primer lugar, podemos mantener un diccionario de palabras sensible, que también se puede lograr utilizando los cuatro algoritmos de coincidencia de patrón único anteriores, pero es muy ineficiente recorrer el contenido de entrada del usuario n veces, donde n es cadena de patrón de todas las palabras sensibles. Pero si mantenemos el diccionario de palabras sensibles como un árbol Trie y luego consultamos la entrada del usuario desde la posición 0 en el árbol Trie, si un nodo rojo coincide, significa que hay una palabra sensible si no hay ningún nodo rojo coincidente; , comenzaremos desde la entrada del usuario. La siguiente posición del contenido comienza a buscarse en el árbol Trie hasta que se recorre el contenido de entrada del usuario, por lo que solo atravesamos la cadena principal una vez.
Sin embargo, una coincidencia de cadenas multipatrón más eficiente utiliza el siguiente autómata AC.
Si se compara el árbol Trie con el algoritmo BF y el algoritmo KMP es una mejora del algoritmo BF, entonces el autómata AC también utiliza la misma idea para mejorar el árbol Trie.
La idea y el proceso del algoritmo son algo complicados y se resolverán más adelante.