¿Qué algoritmo de búsqueda de cadenas es realmente el más rápido?

Depende del tipo de búsqueda que desee realizar. Cada uno de los algoritmos funciona particularmente bien para ciertos tipos de búsqueda, pero no ha indicado el contexto de sus búsquedas.

A continuación, se muestran algunos pensamientos típicos sobre los tipos de búsqueda:

• Boyer-Moore: funciona analizando previamente el patrón y comparándolo de derecha a izquierda. Si ocurre una discrepancia, el análisis inicial se utiliza para determinar qué tanto se puede cambiar el patrón w.r.t. el texto que se busca. Esto funciona particularmente bien para patrones de búsqueda largos. En particular, puede ser sublineal, ya que no es necesario leer todos los caracteres de su texto.

• Knuth-Morris-Pratt: también analiza previamente el patrón , pero intenta reutilizar lo que ya estaba emparejado en la parte inicial del patrón para evitar tener que volver a emparejarlo. Esto puede funcionar bastante bien, si su alfabeto es pequeño (por ejemplo, bases de ADN), ya que tiene una mayor probabilidad de que sus patrones de búsqueda contengan subpatrones reutilizables.

• Aho- Corasick: necesita mucho procesamiento previo, pero lo hace para varios patrones. Si sabe que buscará los mismos patrones de búsqueda una y otra vez, entonces esto es mucho mejor que el otro, porque necesita analizar los patrones solo una vez, no una vez por búsqueda.

Por lo tanto, como es habitual en CS, no existe una respuesta definitiva al mejor general . Se trata más bien de elegir la herramienta adecuada para el trabajo en cuestión.

Otra nota sobre el razonamiento del peor de los casos: considere los tipos de búsquedas necesarias para crear el peor de los casos y piense detenidamente si estos son realmente relevantes en su caso. Por ejemplo, la O(mn) complejidad del peor de los casos del algoritmo de Boyer-Moore se deriva de un patrón de búsqueda y un texto en el que cada uno usa solo un carácter (como encontrar aaa en aaaaaaaaaaaaaaaaaaaaa). ¿Realmente necesitas ser rápido para búsquedas como esa?

Comentarios

• Tengo todo el alfabeto inglés más o menos para usar y actualicé la Pregunta, lo siento por no comenzar con esto al principio.
• Y sí, necesito ser rápido incluso para búsquedas como que
• ¿puede eloborar en el algoritmo de Z ‘ s y manachar también?

Aunque llego un poco tarde para responder esta pregunta, creo que Z-Algorithm es mucho más rápido que cualquiera de sus contrapartes.Su complejidad en el peor de los casos es O (m + n) y no requiere preprocesamiento del patrón / texto. También es muy fácil de codificar en comparación con los otros algoritmos.

Funciona de la siguiente manera.

Por ejemplo, hay una cadena S ="abaaba". Debemos encontrar z(i) valores para i=0 to len(S)-1. Antes de entrar en la explicación, permítanme establecer algunas definiciones primero.

z(i) = no. de caracteres del prefijo de S que coincide con el prefijo de s(i).

s(i) = ith sufijo de S.

Los siguientes son los s(i) valores para s = "abaaba".

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

Los valores z son respectivamente

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

Para una comprensión detallada del algoritmo, consulte los siguientes enlaces.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Ahora se necesita O (N) para encontrar todos los valores z sin ninguna sobrecarga de preprocesamiento. Uno se estaría preguntando ahora ¿cómo se puede usar esta lógica para hacer coincidir el patrón en una cadena dada?

Veamos con un ejemplo. Patrón (P): aba, Text (T): aacbabcabaad.

Pon esto en la forma P $ T. ($ – cualquier carácter que no aparezca en el patrón o en el texto. Llegaré a la importancia de $ en un momento.)

P$T = aba$aacbabcabaad

Sabemos len(P) = 3.

Todos los valores z de P$T son

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

Ahora, z(i) = len(P). Ans = 11. Entonces, nuestro patrón está presente en Ans-len(P)-1 = 7. -1 es para el carácter $.

Ahora, ¿por qué $ o cualquier carácter especial de este tipo es importante. Considere P = "aaa" y T = "aaaaaaa". Sin el carácter especial, todos los z(i) tendrán valores incrementales. Aún se puede encontrar la posición del patrón en el texto con las fórmulas siguientes:

Condición: z(i)> = len(P) y Posición: Ans-len(P). Pero la condición en este caso se vuelve un poco complicada y confusa. Personalmente, prefiero utilizar la técnica de caracteres especiales.

Comentarios

• ¿Podrías explicarlo tú mismo aquí? Tener enlaces a sitios externos se puede utilizar para elaborar, pero el núcleo de una respuesta debe estar en la respuesta misma en lugar de tener que seguir un enlace a otro sitio.
• El algoritmo z es básicamente el mismo que kmp. Dudo que sea mucho más rápido.
• Estoy de acuerdo con @ThomasAhle. Computación z es preprocesamiento. Sin embargo, ‘ es una buena explicación. Puse una O(n) forma de convertir de preprocesamiento KMP a preprocesamiento Z, debido a esta respuesta. Aquí

Use memoria direccionable de contenido , implementada en software en forma de direccionamiento virtual (apuntando letras a letras).

Es algo superfluo para un algoritmo de coincidencia de cadenas promedio.

CAM puede hacer coincidir una gran cantidad de patrones simultáneamente, hasta patrones de 128 letras (si son ASCII; si son Unicode, solo 64). Y es una llamada por longitud de letra en la cadena con la que desea hacer coincidir y una lectura aleatoria de la memoria por longitud de la longitud máxima del patrón. Entonces, si estuviera analizando una cadena de 100,000 letras, con hasta 90,000,000 patrones simultáneamente (lo que tomaría alrededor de 128 GiB para almacenar un recuento de patrones tan grande), tomaría 12,800,000 lecturas aleatorias de la RAM, por lo que sucedería en 1 ms.

Así es como funciona el direccionamiento virtual.

Si comienzo con 256 direcciones de inicio, que representan la primera letra, estas letras apuntan a 256 de las siguientes letras. Si un patrón no existe, no lo almacena.

Entonces, si sigo uniendo letras con letras, es como tener 128 porciones de direccionamiento virtual apuntando a direccionamiento virtual.

Eso funciona — pero para llegar a 900,000,000 de patrones coincidentes simultáneamente, hay un último truco para agregar — y está aprovechando del hecho de que comienzas con una gran cantidad de reutilización de estos búferes de letras, pero luego se dispersan.Si enumera el contenido, en lugar de asignar los 256 caracteres, entonces se ralentiza muy poco, y obtendrá un aumento de capacidad de 100 veces, porque básicamente solo obtendrá 1 letra utilizada en cada búfer de puntero de letra (que llamé » escape «).

Si desea obtener una coincidencia de cadena del vecino más cercano, entonces tiene muchos de estos ejecutándose en paralelo y los recopila en una jerarquía, por lo que distribuye su error de manera imparcial. si intenta vecino más cercano con solo uno, entonces estás sesgado hacia el inicio del árbol.

Comentarios

• @MagnusRobertCarlWoot dado que tienes el mismo gavatar como roucer81, es una coincidencia astronómica de colisión de código hash o tiene la misma dirección de correo electrónico. Si eres la misma persona detrás de ambas cuentas, debes utilizar el formulario » contáctanos » para fusionarlas y obtener el crédito adecuado por la reputación ganada a través de los votos a favor de esta respuesta.