subcadena rabin moore kmp funciona entre distancia como caracteristicas cadenas busqueda boyer algoritmos algoritmo algorithms c algorithm string substring

rabin - distancia entre cadenas



¿Cuál es el algoritmo de búsqueda de subcadenas más rápido? (16)

Aquí está la implementación de búsqueda de Python , utilizada en todo el núcleo. Los comentarios indican que usa una tabla comprimida boyer-moore delta 1 .

He hecho algunos experimentos muy extensos con la búsqueda de cadenas, pero fue para múltiples cadenas de búsqueda. Las implementaciones de ensamblaje de Horspool y Bitap menudo pueden defenderse contra algoritmos como Aho-Corasick para recuentos bajos de patrones.

OK, entonces no parezco un idiota. Voy a exponer el problema / requisitos más explícitamente:

  • Needle (patrón) y haystack (texto para buscar) son ambas cadenas terminadas en nulo estilo C. No se proporciona información de longitud; si es necesario, debe ser computado.
  • La función debe devolver un puntero a la primera coincidencia, o NULL si no se encuentra ninguna coincidencia.
  • Los casos de falla no están permitidos. Esto significa que cualquier algoritmo con requisitos de almacenamiento no constantes (o grandes constantes) deberá tener un caso de respaldo para la falla de asignación (y el rendimiento en la atención alternativa contribuirá al peor de los casos).
  • La implementación debe estar en C, aunque una buena descripción del algoritmo (o enlace a tal) sin código también está bien.

... así como lo que quiero decir con "más rápido":

  • O(n) determinístico O(n) donde n = longitud del pajar. (Pero puede ser posible utilizar ideas de algoritmos que normalmente son O(nm) (por ejemplo, hash rodante) si se combinan con un algoritmo más robusto para obtener resultados O(n) deterministas).
  • Nunca realiza (mensurablemente, un par de relojes para if (!needle[1]) etc. están bien) peor que el ingenuo algoritmo de fuerza bruta, especialmente en agujas muy cortas, que es probablemente el caso más común. (La sobrecarga de preprocesamiento pesado incondicional es mala, al igual que tratar de mejorar el coeficiente lineal para agujas patológicas a expensas de agujas probables).
  • Dada una aguja arbitraria y un pajar, un rendimiento comparable o mejor (no peor que un 50% más de tiempo de búsqueda) versus cualquier otro algoritmo ampliamente implementado.
  • Aparte de estas condiciones, estoy dejando la definición de "más rápido" de composición abierta. Una buena respuesta debería explicar por qué considera que el enfoque que está sugiriendo es el "más rápido".

Mi implementación actual se ejecuta aproximadamente entre un 10% más lento y 8 veces más rápido (según la entrada) que la implementación de Two-Way de glibc.

Actualización: mi algoritmo óptimo actual es el siguiente:

  • Para agujas de longitud 1, use strchr .
  • Para agujas de longitud 2-4, utilice palabras de máquina para comparar 2-4 bytes a la vez de la siguiente manera: Precargue la aguja en un entero de 16 o 32 bits con cambios de bits y salga del byte antiguo / nuevos bytes desde el pajar en cada iteración . Cada byte del pajar se lee exactamente una vez e implica una comprobación contra 0 (final de la cadena) y una comparación de 16 o 32 bits.
  • Para agujas de longitud> 4, utilice el algoritmo de dos vías con una mala tabla de cambios (como Boyer-Moore) que se aplica solo al último byte de la ventana. Para evitar la sobrecarga de inicializar una tabla de 1 kb, que sería una pérdida neta para muchas agujas de longitud moderada, conservo una matriz de bits (32 bytes) que marca las entradas en la tabla de cambios que se inicializan. Los bits que no están ajustados corresponden a valores de bytes que nunca aparecen en la aguja, por lo que es posible un cambio de longitud de aguja completa.

Las grandes preguntas que quedan en mi mente son:

  • ¿Hay alguna manera de hacer un mejor uso de la mala tabla de cambios? Boyer-Moore hace el mejor uso escaneando hacia atrás (de derecha a izquierda), pero Two-Way requiere un escaneo de izquierda a derecha.
  • Los dos únicos algoritmos candidatos posibles que he encontrado para el caso general (sin condiciones de rendimiento de memoria o cuadrática) son la Two-Way y cadenas en alfabetos ordenados . Pero, ¿hay casos fácilmente detectables en los que diferentes algoritmos serían óptimos? Ciertamente, muchos de los algoritmos de O(m) (donde m es la longitud de la aguja) en el espacio podrían usarse para m<100 o más. También sería posible usar algoritmos que son el peor caso cuadrático si hay una prueba fácil para las agujas que probablemente solo requieren tiempo lineal.

Puntos de bonificación por:

  • ¿Se puede mejorar el rendimiento suponiendo que la aguja y el pajar están bien formados UTF-8? (Con caracteres de diferentes longitudes de bytes, la buena formación impone algunos requisitos de alineación de cadenas entre la aguja y el pajar, y permite cambios automáticos de 2 a 4 bytes cuando se encuentra un byte de cabecera que no coincide. Pero estas restricciones le compran mucho / más allá de lo que cómputos de sufijos máximos, buenos cambios de sufijos, etc. ¿Ya te dan varios algoritmos?)

Nota: Conozco muy bien la mayoría de los algoritmos disponibles, simplemente no lo bien que funcionan en la práctica. Aquí hay una buena referencia para que la gente no siga dándome referencias sobre algoritmos como comentarios / respuestas: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Construya una biblioteca de prueba de posibles agujas y pajares. Perfila las pruebas en varios algoritmos de búsqueda, incluida la fuerza bruta. Elija el que tenga el mejor rendimiento con sus datos.

Boyer-Moore usa una tabla de caracteres malos con una buena tabla de sufijos.

Boyer-Moore-Horspool usa una mala tabla de caracteres.

Knuth-Morris-Pratt usa una tabla de coincidencias parciales.

Rabin-Karp usa hashes en ejecución.

Todos ellos intercambian gastos generales para comparaciones reducidas en un grado diferente, por lo que el rendimiento en el mundo real dependerá de la longitud promedio de la aguja y el pajar. Cuanta más sobrecarga inicial, mejor con entradas más largas. Con agujas muy cortas, la fuerza bruta puede ganar.

Editar:

Un algoritmo diferente podría ser mejor para encontrar pares de bases, frases en inglés o palabras sueltas. Si hubiera un mejor algoritmo para todas las entradas, se habría publicitado.

Piensa en la siguiente tabla pequeña. Cada signo de interrogación podría tener un mejor algoritmo de búsqueda diferente.

short needle long needle short haystack ? ? long haystack ? ?

Esto realmente debería ser un gráfico, con un rango de entradas más cortas a más largas en cada eje. Si trazaste cada algoritmo en dicho gráfico, cada uno tendría una firma diferente. Algunos algoritmos sufren con mucha repetición en el patrón, lo que podría afectar usos como la búsqueda de genes. Algunos otros factores que afectan el rendimiento general buscan el mismo patrón más de una vez y buscan diferentes patrones al mismo tiempo.

Si necesitaba un conjunto de muestras, creo que iría a un sitio como google o wikipedia, y luego eliminaría el html de todas las páginas de resultados. Para un sitio de búsqueda, escriba una palabra y luego use una de las frases de búsqueda sugeridas. Elija algunos idiomas diferentes, si corresponde. Al usar páginas web, todos los textos serían cortos a medios, por lo tanto, combine suficientes páginas para obtener textos más largos. También puede encontrar libros de dominio público, registros legales y otras grandes cantidades de texto. O simplemente genere contenido aleatorio eligiendo palabras de un diccionario. Pero el objetivo de la creación de perfiles es probar el tipo de contenido que buscará, de modo que utilice muestras del mundo real si es posible.

Me fui corto y largo vago. Para la aguja, creo que tiene menos de 8 caracteres, menos de 64 caracteres y menos de 1k. Para el pajar, pienso en corto como en 2 ^ 10, mediano como en 2 ^ 20, y largo hasta 2 ^ 30 caracteres.

El algoritmo bidireccional que mencionas en tu pregunta (que, por cierto, es increíble) se ha mejorado recientemente para que funcione de manera eficiente en palabras de varios bytes a la vez: Optimal Packed String Matching .

No he leído todo el artículo, pero parece que confían en un par de nuevas instrucciones especiales de CPU (incluidas, por ejemplo, SSE 4.2) que son O (1) para su reclamo de complejidad de tiempo, aunque si no están disponibles, pueden simularlos en el tiempo O (log log w) para palabras de w-bit que no suena tan mal.

El algoritmo de búsqueda de subcadenas más rápido va a depender del contexto:

  1. el tamaño del alfabeto (p. ej., ADN vs inglés)
  2. la longitud de la aguja

El documento de 2010 "El problema de correspondencia exacta: una evaluación experimental completa" proporciona tablas con tiempos de ejecución para 51 algoritmos (con diferentes tamaños de alfabeto y longitudes de aguja), para que pueda elegir el mejor algoritmo para su contexto.

Todos estos algoritmos tienen implementaciones C, así como un conjunto de pruebas, aquí:

http://www.dmi.unict.it/~faro/smart/algorithms.php

El enlace http://www-igm.univ-mlv.fr/~lecroq/string/index.html que señala es una excelente fuente y resumen de algunos de los algoritmos de coincidencia de cadenas más conocidos e investigados.

Las soluciones para la mayoría de los problemas de búsqueda implican compensaciones con respecto a los gastos generales de procesamiento previo, los requisitos de tiempo y espacio. Ningún algoritmo único será óptimo o práctico en todos los casos.

Si su objetivo es diseñar un algoritmo específico para la búsqueda de cadenas, entonces ignore el resto de lo que tengo que decir. Si desea desarrollar una rutina de servicio general de búsqueda de cadenas, intente lo siguiente:

Dedica algo de tiempo a revisar las fortalezas y debilidades específicas de los algoritmos a los que ya has hecho referencia. Realice la revisión con el objetivo de encontrar un conjunto de algoritmos que cubran el rango y el alcance de las búsquedas de cadenas que le interesen. Luego, cree un selector de búsqueda de front-end basado en una función de clasificador para seleccionar el mejor algoritmo para las entradas dadas. De esta forma, puede emplear el algoritmo más eficiente para hacer el trabajo. Esto es particularmente efectivo cuando un algoritmo es muy bueno para ciertas búsquedas, pero se degrada poco. Por ejemplo, la fuerza bruta es probablemente la mejor para agujas de longitud 1 pero se degrada rápidamente a medida que aumenta la longitud de la aguja, con lo que el algoritim sustik-moore puede ser más eficiente (sobre alfabetos pequeños), luego para agujas más largas y alfabetos más grandes, el KMP o Boyer -Manos algoritmos pueden ser mejores. Estos son solo ejemplos para ilustrar una posible estrategia.

El enfoque de algoritmo múltiple no es una idea nueva. Creo que ha sido empleado por algunos paquetes comerciales de clasificación / búsqueda (por ejemplo, SYNCSORT comúnmente utilizado en mainframes implementa varios algoritmos de clasificación y usa heurística para elegir el "mejor" para las entradas dadas)

Cada algoritmo de búsqueda tiene varias variaciones que pueden generar diferencias significativas en su rendimiento, como, por ejemplo, este paper ilustra.

Compare su servicio para categorizar las áreas donde se necesitan estrategias de búsqueda adicionales o para ajustar con más efectividad su función de selector. Este enfoque no es rápido ni fácil, pero si se hace bien puede producir muy buenos resultados.

Me sorprendió ver nuestro informe técnico citado en esta discusión; Soy uno de los autores del algoritmo que se nombró Sustik-Moore anteriormente. (No usamos ese término en nuestro artículo).

Quería enfatizar aquí que, para mí, la característica más interesante del algoritmo es que es bastante simple probar que cada letra se examina como mucho una vez. Para versiones anteriores de Boyer-Moore probaron que cada letra se examina como máximo 3 y más tarde 2 veces como máximo, y esas pruebas fueron más complicadas (ver citas en papel). Por lo tanto, también veo un valor didáctico al presentar / estudiar esta variante.

En el documento también describimos otras variaciones que están orientadas a la eficiencia mientras se relajan las garantías teóricas. Es un trabajo breve y, en mi opinión, el material debe ser comprensible para un graduado medio de la escuela secundaria.

Nuestro principal objetivo fue llevar esta versión a la atención de otros que pueden mejorarla aún más. La búsqueda de cadenas tiene tantas variaciones y nosotros solos no podemos pensar en todo en lo que esta idea podría traer beneficios. (Texto fijo y patrón cambiante, texto diferente de patrón fijo, posible / no posible de preprocesamiento, ejecución paralela, encontrar subconjuntos coincidentes en textos grandes, permitir errores, coincidencias cercanas, etc., etc.)

Podría implementar, digamos, 4 algoritmos diferentes. Cada M minutos (que se determinará empíricamente) ejecuta los 4 en datos reales actuales. Acumule estadísticas sobre N carreras (también TBD). Luego usa solo el ganador para los próximos M minutos.

Registre las estadísticas en Wins para que pueda reemplazar los algoritmos que nunca ganan con los nuevos. Concentrar los esfuerzos de optimización en la rutina más exitosa. Preste especial atención a las estadísticas después de cualquier cambio en el hardware, la base de datos o la fuente de datos. Incluya esa información en el registro de estadísticas, si es posible, para que no tenga que averiguarlo a partir de la fecha / hora del registro.

Recientemente descubrí una buena herramienta para medir el rendimiento de los diversos algos disponibles: http://www.dmi.unict.it/~faro/smart/index.php

Tu podrias encontrar esto útil. Además, si tengo que hacer una llamada rápida en el algoritmo de búsqueda de subcadenas, me gustaría ir con Knuth-Morris-Pratt.

Sé que es una vieja pregunta, pero la mayoría de las malas tablas de cambios son de un solo carácter. Si tiene sentido para su conjunto de datos (por ejemplo, especialmente si se trata de palabras escritas), y si tiene el espacio disponible, puede obtener una aceleración dramática utilizando una tabla de cambios mala hecha de n-grams en lugar de caracteres individuales.

Simplemente busque "strstr más rápido", y si ve algo de interés solo pregúnteme.

En mi opinión, usted se impone demasiadas restricciones (sí, todos queremos líneas lineales sublineales en el buscador máximo), sin embargo, se necesita un verdadero programador para intervenir, hasta entonces creo que el enfoque hash es simplemente una solución de limbo ingenioso ( bien reforzado por BNDM para patrones más cortos de 2..16).

Solo un rápido ejemplo:

Hacer búsqueda de patrones (32bytes) en cadenas (206908949bytes) como una línea ... Saltar-Actuación (mejor-mejor): 3041%, 6801754 saltos / iteraciones Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade rendimiento: 3483KB / reloj

Haciendo búsqueda de patrones (32bytes) en cadenas (206908949bytes) como una línea ... Skip-Performance (mejor-más-grande): 1554%, 13307181 saltos / iteraciones Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg performance: 2434KB / reloj

Haciendo búsqueda de patrones (32bytes) en cadenas (206908949bytes) como una línea ... Skip-Performance (mejor-más-grande): 129%, 160239051 saltos / iteraciones Two-Way_hits / Two-Way_clocks: 0/816 Two -Rendimiento de la calle : 247KB / reloj

Sanmayce,
Saludos

Un algoritmo más rápido de "búsqueda de un solo carácter coincidente" (ala strchr ).

Notas importantes:

  • Estas funciones usan un "número / recuento de (líderes | finales) ceros" compilador gcc intrinsic- __builtin_ctz . Es probable que estas funciones solo sean rápidas en máquinas que tienen una (s) instrucción (es) que realizan esta operación (es decir, x86, ppc, brazo).

  • Estas funciones suponen que la arquitectura de destino puede realizar cargas desalineadas de 32 y 64 bits. Si su arquitectura de destino no es compatible con esto, deberá agregar alguna lógica de inicio para alinear correctamente las lecturas.

  • Estas funciones son procesador neutral. Si la CPU objetivo tiene instrucciones vectoriales, es posible que pueda hacer (mucho) mejor. Por ejemplo, la función strlen continuación usa SSE3 y se puede modificar trivialmente a XOR los bytes escaneados para buscar un byte que no sea 0 . Los puntos de referencia se realizaron en una laptop Core 2 de 2.66 GHz con Mac OS X 10.6 (x86_64):

    • 843.433 MB / s para strchr
    • 2656.742 MB / s para findFirstByte64
    • 13094,479 MB / s para strlen

... una versión de 32 bits:

#ifdef __BIG_ENDIAN__ #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u) ? 0 : (__builtin_clz(_x) >> 3) + 1; }) #else #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (__builtin_ctz(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) { uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8); byteMask32 |= byteMask32 << 16; while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; } return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1)); }

... y una versión de 64 bits:

#ifdef __BIG_ENDIAN__ #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; }) #else #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (__builtin_ctzll(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) { uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8); byteMask64 |= byteMask64 << 16; byteMask64 |= byteMask64 << 32; while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; } return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1)); }

Editar 2011/06/04 El OP señala en los comentarios que esta solución tiene un "error insuperable":

puede leer más allá del byte buscado o del terminador nulo, que podría acceder a una página o página no asignada sin permiso de lectura. Simplemente no puede usar lecturas grandes en funciones de cadena a menos que estén alineadas.

Esto es técnicamente cierto, pero se aplica a prácticamente cualquier algoritmo que opera en trozos que son más grandes que un solo byte, incluido el método sugerido por el OP en los comentarios:

Una implementación típica de strchr no es ingenua, pero es bastante más eficiente que lo que le diste. Consulte el final de este para obtener el algoritmo más utilizado: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

También realmente no tiene nada que ver con la alineación per se. Es cierto que esto podría causar el comportamiento discutido en la mayoría de las arquitecturas comunes en uso, pero esto tiene más que ver con los detalles de implementación de microarquitectura: si la lectura desalineada se extiende a un límite 4K (de nuevo, típico), entonces esa lectura causará un programa terminación de la falla si el próximo límite de página de 4K no está mapeado.

Pero esto no es un "error" en el algoritmo dado en la respuesta, ese comportamiento se debe a que funciones como strchr y strlen no aceptan un argumento de length para vincular el tamaño de la búsqueda. Buscando char bytes[1] = {0x55}; , que a los fines de nuestra discusión sucede que se coloca al final de un límite de página 4K VM y la página siguiente no está strchr(bytes, 0xAA) , con strchr(bytes, 0xAA) (donde strchr es un byte a la vez) implementación) se bloqueará exactamente de la misma manera. Lo mismo strchr con el primo relacionado con strlen .

Sin un argumento de length , no hay forma de saber cuándo se debe cambiar el algoritmo de alta velocidad y volver a un algoritmo de byte a byte. Un "error" mucho más probable sería leer "más allá del tamaño de la asignación", que técnicamente resulta en undefined behavior acuerdo con los diversos estándares de lenguaje C, y sería marcado como un error por algo como valgrind .

En resumen, cualquier cosa que opere en trozos más grandes que bytes para ir más rápido, ya que este código responde y el código apuntado por el OP, pero debe tener una semántica de lectura precisa de bytes es probable que sea "defectuoso" si no hay argumento de length para controlar la (s) caja (s) de esquina de "la última lectura".

El código en esta respuesta es un kernel para poder encontrar el primer byte en un trozo de tamaño de palabra de CPU natural rápidamente si la CPU objetivo tiene una instrucción de tipo ctz rápida. Es trivial agregar cosas como asegurarse de que solo opere en límites naturales alineados correctamente, o alguna forma de límite de length , lo que le permitiría desconectarse del núcleo de alta velocidad y pasar a un control byte por byte más lento.

El OP también afirma en los comentarios:

En cuanto a su optimización de ctz, solo hace una diferencia para la operación de cola O (1). Podría mejorar el rendimiento con cadenas diminutas (por ejemplo, strchr("abc", ''a''); pero ciertamente no con cadenas de tamaño mayor.

Que esta afirmación sea o no verdadera depende en gran medida de la microarquitectura en cuestión. Utilizando el modelo de tubería RISC canónica de 4 etapas, entonces es casi seguro que sea cierto. Pero es extremadamente difícil decir si es cierto para una CPU súper escalar fuera de servicio contemporánea, donde la velocidad del núcleo puede empequeñecer por completo la velocidad de transmisión de la memoria. En este caso, no solo es plausible, sino bastante común, que haya una gran brecha en "la cantidad de instrucciones que se pueden retirar" en relación con "la cantidad de bytes que se pueden transmitir" para que tenga "el número de instrucciones que pueden retirarse para cada byte que se puede transmitir ". Si esto es lo suficientemente grande, la instrucción ctz + shift se puede hacer "gratis".

Una muy buena pregunta. Solo agrega algunos pedacitos ...

  1. Alguien estaba hablando sobre la coincidencia de secuencias de ADN. Pero para la secuencia de ADN, lo que normalmente hacemos es crear una estructura de datos (por ejemplo, matriz de sufijos, árbol de sufijos o índice de FM) para el pajar y hacer coincidir muchas agujas en su contra. Esta es una pregunta diferente.

  2. Sería genial si alguien quisiera comparar varios algoritmos. Hay muy buenos puntos de referencia en la compresión y la construcción de arreglos de sufijos, pero no he visto un punto de referencia en la coincidencia de cadenas. Los potenciales candidatos de pajar podrían ser del punto de referencia de SACA .

  3. Hace unos días estaba probando la implementación de Boyer-Moore desde la página que recomendabas (EDITAR: Necesito una función llamada como memmem (), pero no es una función estándar, así que decidí implementarla). Mi programa de benchmarking usa pajar aleatorio. Parece que la implementación de Boyer-Moore en esa página es más rápida que la memoria de glibc () y strnstr () de Mac. En caso de que esté interesado, la implementación está here y el código de evaluación comparativa está here . Esto definitivamente no es un punto de referencia realista, pero es un comienzo.

I don''t know if it''s the absolute best, but I''ve had good experience with Boyer-Moore .

Use stdlib strstr :

char *foundit = strstr(haystack, needle);

It was very fast, only took me about 5 seconds to type.

You might also want to have diverse benchmarks with several types of strings, as this may have a great impact on performance. The algos will perform differenlty based on searching natural language (and even here there still might be fine grained distinctions because of the different morphologoies), DNA strings or random strings etc.

Alphabet size will play a role in many algos, as will needle size. For instance Horspool does good on English text but bad on DNA because of the different alphabet size, making life hard for the bad-character rule. Introducing the good-suffix allieviates this greatly.