Algoritmo rápido para buscar subcadenas en una cadena

Question

Me gustaría un algoritmo (o biblioteca) eficiente que pueda usar en Java para buscar subcadenas en una cadena.

Lo que me gustaría hacer es:

Dada una cadena de entrada - INSTR:

"BCDEFGH"

Y un conjunto de cadenas de candidatos - CAND :

"AB", "CDE", "FG", "H", "IJ"

: todas las CAND cadenas que coinciden como subcadenas dentro INSTR

En este ejemplo coincidiría con "CDE", "FG" y "H" (pero no con "AB" y "IJ")

Podría haber miles de cadenas candidatas (en CAND), pero lo más importante es que haré esta búsqueda muchos millones de veces, así que necesito que sea RÁPIDO.

Me gustaría trabajar con matrices de caracteres. Además, no estoy probado en soluciones arquitectónicas, como distribuir la búsqueda, solo la función/algoritmo más eficiente para hacerlo localmente.

Además, todas las cadenas en CAND y INSTR serán relativamente pequeñas (< 50 caracteres), es decir, la cadena de destino INSTR NO es larga en relación con las cadenas candidatas.

---

actualización debería haber mencionado, el conjunto de cadenas CAND es invariante en todos los valores de INSTR.

Actualización Solo necesito saber que hay una coincidencia, y no necesito saber cuál fue el partido.

Informe final de actualización que optamos por tratar AhoCorsick y Rabin-Karp, debido a la simplicidad de implementación. Como tengo patrones de longitud variable, utilicé un Rabin-Karp modificado que hash los primeros n caracteres de cada patrón, donde n es la longitud del patrón más pequeño, N fue entonces la longitud de la ventana de búsqueda de mi subserie móvil. Para el Aho Corsick que utilizan this

En mi prueba Busqué 1000 patrones en dos documentos de artículos de prensa de papel, promediados entre 1000 iteraciones etc ... tiempos normalizados para completar eran:

AhoCorsick: 1

RabinKarp: 1.8

Naive Buscar (marque cada string.contains patrón de uso &): 50

---

* Algunos recursos que describen los algos mencionados en las respuestas a continuación:

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html *

Answer 1

Lea en el Aho-Corasick algorithm y el Rabin-Karp algorithm.

Si la entrada no es demasiado grande, no desea repetir la búsqueda muchas veces y no tiene muchos patrones, puede ser una buena idea usar un algoritmo de patrón único varias veces. El Wikipedia article on search algorithms proporciona muchos algoritmos con tiempos de ejecución y preproceso.

Implementaciones:

• https://hkn.eecs.berkeley.edu/~dyoo/java/index.html
• http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html
• https://github.com/hankcs/AhoCorasickDoubleArrayTrie
• https://github.com/RokLenarcic/AhoCorasick
• https://github.com/robert-bor/aho-corasick

Presentaciones:

• http://www.slideshare.net/taka111/ahocorasick-string-matching-algorithm-15078438

Answer 2

Convierta el conjunto de cadenas candidatas en un autómata de estado finito determinista y luego ejecute la cadena de entrada en tiempo lineal. La conversión de una sola cadena en un DFS está bien cubierta en los libros estándar. Puede convertir un conjunto de cadenas construyendo primero un autómata no determinista y luego determinándolo. Eso puede crear una explosión exponencial en el peor de los casos en el tamaño del autómata pero la búsqueda posterior es rápida; especialmente si la cadena objetivo es larga y los candidatos cortos van a funcionar bien.

Answer 3

Es posible que desee ver en Aho-Corasick algorithm y algoritmos relacionados. No conozco ninguna biblioteca que implemente esto, de manera espontánea, pero esta es la forma clásica de resolver este problema.

Answer 4

Rabin-Karp multiple pattern search parece ser el más rápido.

Answer 5

También verifique el Boyer-Moore algorithm para coincidencia de patrón de una sola cuerda.

Answer 6

Esto es para lo que son las expresiones regulares. Como se indicó anteriormente, los autómatas de estados finitos son lo que necesita, pero así es exactamente como se implementa un regexp-matcher estándar.

en Java podría escribir algo como:

StringBuilder sb = new StringBuilder(); 
bool first = true; 
for (String subStr : substrings) { 
    if (first) 
     first = false; 
    else 
     sb.append('|'); 
    sb.append(escape(subStr)); 
} 
Pattern p = Pattern.compile(sb.toString()); 

el método escape debe escapar los caracteres que tienen un significado especial en una expresión regular.

Answer 7

Otra solución es utilizar un suffix array para el INSTR.
Desde el INSTR es pequeño se puede ordenar con ordenamiento de burbuja.

Después se puede buscar una cadena específica CAND en O (logN),
donde N = longitud (suffix_array) = longitud (INSTR).

Answer 8

Podemos aprovechar el tamaño pequeño (< 50 caracteres) de las cadenas para crear un algoritmo súper rápido para este caso, a costa de la memoria.

Nos puede dispersar todas las posibles subcadenas de INSTR en un hash una vez que va a costar un tiempo O (n^2). Entonces, independientemente del número de cadenas CAND, la búsqueda será O (1). Vale la pena por una gran cantidad de cadenas de CAND.

Si INSTR es grande, podemos construir una matriz de sufijos y no ordenarla, de modo que el elemento superior sea el más largo (= N) y el último elemento sea el último carácter de INSTR. Ahora, para cada cadena CAND, solo busque desde la parte superior siempre que tenga longitud (CAND) < = longitud (sufijo). Cada una de esas comparaciones será O (n).

Answer 9

Here son algunos de Cuerda implementación de algoritmos de búsqueda rápida en Java.

Answer 10

import java.util.Scanner; 

public class StringMatch 
{ 
    static int temp,i=0,j=0; static boolean flag=true,matcher=false; 

    static String str=null,mstr=null;static char astr[],amstr[]; 

    static void getter(){ 
     Scanner sc = new Scanner(System.in); 
     str = sc.nextLine(); 
     //String str="today is Monday"; 
     astr=str.toCharArray(); 
     mstr = sc.nextLine(); 
     //String mstr="is"; 
     amstr=mstr.toCharArray(); 
    } 

    static void stringMatch(){ 
     while(i<astr.length){ 
      if(astr[i]==amstr[j]){ 
      while((j!=amstr.length)&&flag){temp=i; 
       if(astr[i]!=amstr[j]) {flag=false;matcher=false;} 
       else{matcher=true;} 
       i++;j++; 
       //System.out.println(i+"\t"+j); 
      }if(matcher==true)break;i=temp;}i++;j=0;flag=true; 

     } 
     if(matcher==true) {System.out.println("true");} 
     else {System.out.println("false");} 
    } 

    public static void main(String[] args) { 

    StringMatch.getter(); 
    StringMatch.stringMatch(); 

    } 
}