Quale algoritmo di ricerca delle stringhe è effettivamente il più veloce?

Dipende dal tipo di ricerca che si desidera eseguire. Ciascuno degli algoritmi si comporta particolarmente bene per determinati tipi di ricerca, ma non hai indicato il contesto delle tue ricerche.

Ecco alcuni pensieri tipici sui tipi di ricerca:

• Boyer-Moore: funziona pre-analisi del pattern e confronto da destra a sinistra. Se si verifica una mancata corrispondenza, l'analisi iniziale viene utilizzata per determinare fino a che punto è possibile spostare il modello con un numero di es. il testo cercato Ciò funziona particolarmente bene per i modelli di ricerca lunghi. In particolare, può essere sub-lineare, in quanto non è necessario leggere ogni singolo carattere del testo.

• Knuth-Morris-Pratt: anche pre-analisi del pattern, ma cerca di riutilizzare ciò che era già abbinato nella parte iniziale del pattern per evitare di doverlo rivincere. Questo può funzionare abbastanza bene, se il tuo alfabeto è piccolo (ad esempio, le basi del DNA), poiché hai una maggiore possibilità che i tuoi pattern di ricerca contengano subpattern riutilizzabili.

• Aho-Corasick: richiede un sacco di pre-elaborazione, ma lo fa per un numero di pattern. Se sai che cercherai sempre gli stessi pattern di ricerca, questo è molto meglio dell'altro, perché devi analizzare i pattern una sola volta, non una volta per ricerca.

Quindi, come al solito in CS, non esiste una risposta definitiva al miglior generale . È piuttosto una questione di scegliere lo strumento giusto per il lavoro a portata di mano.

Un'altra nota sul ragionamento del tuo caso peggiore: considera i tipi di ricerche richieste per creare il caso peggiore e pensa attentamente se questi sono davvero rilevanti nel tuo caso. Ad esempio, la complessità del caso peggiore in O(mn) dell'algoritmo Boyer-Moore deriva da un modello di ricerca e un testo che usano ciascuno un solo carattere (come trovare aaa in aaaaaaaaaaaaaaaaaaaaa ) - hai davvero bisogno di essere veloce per ricerche del genere?

Anche se sono in ritardo per rispondere a questa domanda, ma penso che Z-Algorithm sia molto più veloce di qualsiasi altra controparte. La sua complessità nel caso peggiore è O (m + n) e non richiede il preprocessing del pattern / testo. È anche molto facile da codificare rispetto agli altri algoritmi.

Funziona nel modo seguente.

Ad esempio, c'è una stringa S ='abaaba' . Dobbiamo trovare z(i) valori per i=0 to len(S)-1 . Prima di entrare nella spiegazione, lascia che apponga prima alcune definizioni.

z(i) = no. di caratteri del prefisso di S che corrisponde al prefisso di s(i) .

s(i) = ith suffisso di S .

I seguenti sono i valori di s(i) per s = 'abaaba' .

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

I valori z sono rispettivamente

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

Per la comprensione dettagliata dell'algoritmo, fare riferimento ai seguenti link.

link

link

Ora occorrono O (N) per trovare tutti i valori di z senza alcun sovraccarico di pre-elaborazione. Ci si potrebbe chiedere ora come si può usare questa logica per abbinare il pattern in una determinata stringa?

Vediamo con un esempio. Pattern (P): aba , Text (T): aacbabcabaad .

Metti questo nel formato P $ T. ( $ - qualsiasi carattere che non appare né nel pattern né nel testo. Entro un po 'esisterò all'importanza di $ .)

P$T = aba$aacbabcabaad

Sappiamo len(P) = 3.

Tutti i valori z di P$T sono

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

Ora quale z(i) = len(P) . Ans = 11. Quindi il nostro modello è presente a Ans-len(P)-1 = 7 . -1 è per $ carattere.

Ora perché $ o qualsiasi carattere speciale di questo tipo è importante. Considera P = 'aaa' e T = 'aaaaaaa' . Senza il carattere speciale, tutto z(i) avrà valori incrementali. Si può ancora trovare la posizione del modello nel testo con le seguenti formule:

Condizione: z(i) > = len(P) e Posizione: Ans-len(P) . Ma la condizione in questo caso diventa un po 'complicata e confusa. Personalmente preferisco usare la tecnica del personaggio speciale.

Utilizza la memoria indirizzabile per i contenuti , implementata nel software sotto forma di indirizzamento virtuale (puntando le lettere alle lettere).

È un po 'superfluo per un algoritmo di corrispondenza delle stringhe medio.

CAM può abbinare un numero enorme di pattern contemporaneamente, fino a circa 128 lettere (se sono ASCII, se sono solo Unicode 64). Ed è una chiamata per lunghezza della lettera nella stringa a cui si desidera abbinare e una lettura casuale dalla memoria per lunghezza della lunghezza massima del pattern. Quindi, se si analizzasse una stringa di 100.000 lettere, con fino a 90.000.000 di pattern contemporaneamente (il che richiederebbe circa 128 GB per memorizzare un conteggio di pattern così grandi), occorrerebbero 12.800.000 letture casuali dalla RAM, quindi accadrebbe in 1 ms. / p>

Ecco come funziona l'indirizzamento virtuale.

Se inizio con 256 indirizzi di avvio, che rappresentano la prima lettera, queste lettere puntano a 256 delle lettere successive. Se un pattern non esiste, non lo memorizzi.

Quindi, se continuo a collegare lettere a lettere, è come avere 128 sezioni di indirizzamento virtuale che puntano all'indirizzamento virtuale.

Questo funzionerà, ma per ottenere 900.000.000 di pattern contemporaneamente corrispondenti, c'è un ultimo trucco da aggiungere ad esso - e si sta avvantaggiando del fatto che si inizia con un sacco di riutilizzo di questi buffer di lettere, ma in seguito sputa fuori. Se si elencano i contenuti, invece di allocare tutti i 256 caratteri, allora rallenta molto poco, e si otterrà un aumento di capacità di 100 volte, perché in pratica alla fine si ottiene solo 1 lettera usata in ogni buffer puntatore (che ho soprannominato ' fuga ').

Se si desidera ottenere una corrispondenza stringa vicina più vicina, molti di questi vengono eseguiti in parallelo e vengono raccolti in una gerarchia, pertanto l'errore viene distribuito in modo imparziale. se provi a un vicino più vicino con uno solo, sei inclinato verso l'inizio dell'albero.