java - sirve - Algoritmo rápido para buscar subcadenas en una cadena
obtener cadena java (10)
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.
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 candidatas - CAND :
"AB", "CDE", "FG", "H", "IJ"
Encuentre cualquier cadena de CAND que coincida como subcadenas dentro de INSTR
En este ejemplo, coincidiría con "CDE", "FG" y "H" (pero no con "AB" y "IJ")
Podría haber muchos 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ÁPIDA.
Me gustaría trabajar con arreglos 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 e 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 que debería haber mencionado, el conjunto de cadenas de CAND es invariante en todos los valores de INSTR.
Actualizar Solo necesito saber que hubo una coincidencia, y no necesito saber cuál fue el partido.
Actualización final Opté por probar AhoCorsick y Rabin-Karp, debido a la simplicidad de la implementación. Debido a que 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 subcadena rodante. Para Aho Corsick usé this
En mi prueba, busqué 1000 patrones en dos documentos, artículos de periódicos, promediados en 1000 iteraciones, etc. Los tiempos normalizados para completar fueron:
AhoCorsick : 1
RabinKarp : 1.8
Búsqueda ingenua (verifique cada patrón y use cadena.contiene): 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
Es posible que desee examinar el algoritmo Aho-Corasick y los algoritmos relacionados. No conozco ninguna biblioteca que implemente esto, de manera espontánea, pero esta es la forma clásica de resolver este problema.
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ías 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 escape método debe escapar de cualquier carácter que tenga un significado especial en una expresión regular.
Lea sobre el algoritmo Aho-Corasick y el algoritmo Rabin-Karp .
Si la entrada no es demasiado grande, no quiere 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 artículo de Wikipedia sobre algoritmos de búsqueda ofrece muchos algoritmos con tiempos de ejecución y preprocesamiento.
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:
Otra solución es usar una matriz de sufijos para el INSTR .
Como el INSTR es pequeño, puede ordenarlo con el tipo de burbuja.
Luego puede buscar una cadena de CAND específica en el tiempo O (logN),
donde N = longitud (sufijo_array) = longitud (INSTR).
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.
Podemos agrupar todas las subcadenas posibles de INSTR en un hash una vez que costará O (n ^ 2) tiempo. 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 un conjunto de sufijos y no ordenarlo, 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 la longitud (CAND) <= length (sufijo). Cada una de esas comparaciones será O (n).
También verifique el algoritmo de Boyer-Moore para la coincidencia de patrones de una sola cuerda.
La búsqueda de patrones múltiples de Rabin-Karp parece ser la más rápida.
Here hay algunas implementaciones de algoritmos rápidos de búsqueda de cadenas en Java.
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();
}
}