Algoritmo veloce per la ricerca di sottostringhe in una stringa

Mi piacerebbe un algoritmo (o una libreria) efficiente che posso usare in Java per cercare sottostringhe in una stringa.

Quello che mi piacerebbe fare è:

Data una stringa di input – INSTR :

“BCDEFGH”

E una serie di stringhe candidate – CAND :

“AB”, “CDE”, “FG”, “H”, “IJ”

Trova le stringhe CAND corrispondenti a sottostringhe all’interno di INSTR

In questo esempio vorrei far corrispondere “CDE”, “FG” e “H” (ma non “AB” e “IJ”)

Potrebbero esserci molte migliaia di stringhe di candidati (in CAND), ma più importante farò questa ricerca molte milioni di volte quindi ho bisogno che sia FAST.

Mi piacerebbe lavorare con gli array di caratteri. Inoltre, non sono intested in soluzioni architettoniche, come la distribuzione della ricerca – solo la funzione / algoritmo più efficiente per farlo localmente.

Inoltre, tutte le stringhe in CAND e INSTR saranno relativamente piccole (<50 caratteri), ovvero la stringa di destinazione INSTR NON è lunga rispetto alle stringhe candidate.


L’aggiornamento I avrebbe dovuto menzionare, l’insieme di stringhe CAND è invariante su tutti i valori di INSTR.

Aggiornamento Ho solo bisogno di sapere che c’era una partita – e non ho bisogno di sapere quale fosse la partita.

Aggiornamento finale Ho deciso di provare AhoCorsick e Rabin-Karp, grazie alla semplicità di implementazione. Poiché ho pattern di lunghezza variabile, ho usato un Rabin-Karp modificato che blocca i primi n caratteri di ciascun pattern, dove n è la lunghezza del pattern più piccolo, N era quindi la lunghezza della mia finestra di ricerca della sottostringa scorrevole. Per Aho Corsick l’ho usato

Nel mio test ho cercato 1000 modelli in due documenti articoli di giornale, mediati su 1000 iterazioni ecc … I tempi normalizzati da completare erano:

AhoCorsick : 1

RabinKarp : 1.8

Ricerca ingenua (controlla ogni schema e usa string.contains): 50


* Alcune risorse che descrivono gli alghi citati nelle risposte qui sotto:

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

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

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

Leggi l’ algoritmo Aho-Corasick e l’ algoritmo Rabin-Karp .

Se l’input non è troppo grande, non si desidera ripetere la ricerca molte volte e non si hanno molti pattern, potrebbe essere una buona idea utilizzare un singolo algoritmo di pattern più volte. L’ articolo di Wikipedia sugli algoritmi di ricerca fornisce molti algoritmi con i tempi di esecuzione e di preelaborazione.

implementazioni:

presentazioni:

Converti l’insieme di stringhe candidate in un automa di stato finito deterministico e poi esegui la stringa di input in tempo lineare. La conversione di una singola stringa in un DFS è ben trattata nei libri standard. È ansible convertire un set di stringhe costruendo prima un automone non deterministico e quindi determinandolo. Ciò può creare una esplosione esponenziale nel caso peggiore delle dimensioni dell’automa, ma la ricerca in seguito è veloce; soprattutto se la stringa di destinazione è lunga e i candidati a breve funzioneranno bene.

Questo è ciò che le espressioni regolari sono per. Come notato sopra, gli automi a stati finiti sono ciò di cui hai bisogno, ma è esattamente come viene implementato un regexp-matcher standard.

In Java puoi scrivere qualcosa come:

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()); 

l’ escape del metodo dovrebbe sfuggire a qualsiasi carattere che abbia un significato speciale in un’espressione regolare.

La ricerca di più modelli Rabin-Karp sembra essere la più veloce.

Potresti voler esaminare l’ algoritmo di Aho-Corasick e gli algoritmi correlati. Non conosco librerie che implementano questo, in modo casuale, ma questo è il modo classico per risolvere questo problema.

Controllare anche l’ algoritmo di Boyer-Moore per la corrispondenza del modello a stringa singola.

Possiamo sfruttare la piccola dimensione (<50 char) delle stringhe per costruire un algo super veloce per questo caso, a costo della memoria.

Possiamo cancellare tutte le sottostringhe possibili di INSTR in un hash una volta che costeranno il tempo O (n ^ 2). Quindi indipendentemente dal numero di stringhe CAND, la ricerca sarà O (1). Ne vale la pena per un numero molto grande di stringhe CAND.

Se INSTR è grande, possiamo build un array suffisso e non ordinarlo, in modo che l’elemento in alto sia il più lungo (= N) e l’elemento in basso è l’ultimo carattere di INSTR. Ora per ogni stringa CAND, cerca solo dall’alto come lunghezza (CAND) <= length (suffisso). Ciascuno di questi confronti sarà O (n).

Un’altra soluzione consiste nell’utilizzare un suffisso per l’ INSTR .
Poiché INSTR è piccolo, puoi ordinarlo con bubble sort.

Successivamente è ansible cercare una specifica stringa CAND in tempo O (logN),
dove N = lunghezza (suffix_array) = lunghezza (INSTR).

Ecco alcune implementazioni di veloci algoritmi di ricerca di stringhe in 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