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

Dipende dal tipo di ricerca che desideri eseguire. Ciascun algoritmo funziona particolarmente bene per determinati tipi di ricerca, ma non hai specificato il contesto delle tue ricerche.

Di seguito sono riportate alcune riflessioni tipiche sui tipi di ricerca:

• Boyer-Moore: funziona pre-analizzando il modello e confrontandolo da destra a sinistra. Se si verifica una mancata corrispondenza, lanalisi iniziale viene utilizzata per determinare di quanto può essere spostato il modello rispetto a. il testo cercato. Questo funziona particolarmente bene per i modelli di ricerca lunghi. In particolare, può essere sub-lineare, poiché non è necessario leggere ogni singolo carattere del testo.

• Knuth-Morris-Pratt: analizza anche in anticipo il modello , ma cerca di riutilizzare tutto ciò che era già abbinato nella parte iniziale del pattern per evitare di doverlo rivedere. Questo può funzionare abbastanza bene, se il tuo alfabeto è piccolo (es. Basi del DNA), poiché hai maggiori possibilità che i tuoi schemi di ricerca contengano modelli secondari riutilizzabili.

• Aho- Corasick: necessita di molta pre-elaborazione, ma lo fa per una serie di pattern. Se sai che cercherai gli stessi schemi di ricerca più e più volte, allora questo è molto meglio dellaltro, perché devi analizzare i modelli solo una volta, non una per ricerca.

Quindi, come al solito in CS, non esiste una risposta definitiva al migliore in assoluto . Si tratta piuttosto di scegliere lo strumento giusto per il lavoro da svolgere.

Unaltra nota sul tuo ragionamento nel caso peggiore: considera i tipi di ricerca necessari per creare quel caso peggiore e pensa attentamente se questi sono davvero rilevanti nel tuo caso. Ad esempio, la O(mn) complessità nel caso peggiore dellalgoritmo di Boyer-Moore deriva da uno schema di ricerca e da un testo che utilizzano ciascuno un solo carattere (come trovare aaa in aaaaaaaaaaaaaaaaaaaaa) – hai davvero bisogno di essere veloce per ricerche del genere?

Commenti

• Ho tutto lalfabeto inglese o giù di lì da usare e ho aggiornato la domanda, scusa per non aver iniziato con questo durante lelemosina.
• E sì, devo essere veloce anche per ricerche come che
• puoi per favore spiegare lalgoritmo di Z ‘ se anche manachar?

Anche se sono un po in ritardo per rispondere a questa domanda, ma penso che Z-Algorithm sia molto più veloce delle sue controparti.La sua complessità nel caso peggiore è O (m + n) e non richiede pre-elaborazione 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, lasciatemi stabilire 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 s(i) valori 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 una comprensione dettagliata dellalgoritmo, fare riferimento ai seguenti link.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Ora è necessario O (N) per trovare tutti i valori z senza alcun sovraccarico di pre-elaborazione. Ci si potrebbe chiedere ora come puoi usare questa logica per trovare il pattern in una data stringa?

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

Mettilo nel formato P $ T. ($ – qualsiasi carattere che non compaia né nel pattern né nel testo. Tra poco imparerò limportanza di $.)

P$T = aba$aacbabcabaad

Conosciamo 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 che z(i) = len(P). Ans = 11. Quindi il nostro pattern è presente in Ans-len(P)-1 = 7. -1 sta per $ carattere.

Ora perché $ o qualsiasi carattere speciale di questo tipo è importante. Considera P = "aaa" e T = "aaaaaaa". Senza il carattere speciale, tutti i z(i) avranno valori incrementali. Si può ancora trovare la posizione del pattern 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 dei caratteri speciali.

Commenti

• Potresti spiegarlo tu stesso qui? Avere collegamenti a siti esterni può essere utilizzato per elaborare, ma il nucleo di una risposta dovrebbe essere nella risposta stessa piuttosto che dover seguire un collegamento a un altro sito.
• Lalgoritmo z è fondamentalmente lo stesso di kmp. Dubito che sia molto più veloce.
• Sono daccordo con @ThomasAhle. Lelaborazione di z è pre-elaborazione. Tuttavia, è ‘ una buona spiegazione. Ho messo a punto un O(n) modo per convertire dalla pre-elaborazione KMP alla pre-elaborazione Z, a causa di questa risposta. Qui

Usa memoria indirizzabile dei 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 modelli contemporaneamente, fino a circa 128 caratteri (se sono ASCII; se sono solo 64 Unicode). Ed è una chiamata per lunghezza di lettera nella stringa a cui si desidera abbinare e una lettura casuale dalla memoria per lunghezza della lunghezza massima del pattern. Quindi, se stessi analizzando una stringa di 100.000 lettere, con un massimo di 90.000.000 di pattern simultaneamente (il che richiederebbe circa 128 GiB per memorizzare un conteggio di pattern così grande), occorrerebbero 12.800.000 letture casuali dalla RAM, quindi avverrebbe in 1 ms.

Ecco come funziona lindirizzamento virtuale.

Se inizio con 256 indirizzi di partenza, che rappresentano la prima lettera, queste lettere puntano a 256 delle lettere successive. Se uno schema è inesistente, non lo memorizzi.

Quindi, se continuo a collegare lettere a lettere, è come avere 128 porzioni di indirizzamento virtuale che puntano a indirizzi virtuali.

funziona — ma per arrivare a 900.000.000 di pattern che corrispondono simultaneamente, cè un ultimo trucco da aggiungere — e sta sfruttando del fatto che inizi con un sacco di riutilizzo di questi buffer di lettere, ma in seguito si disperde.Se elenchi il contenuto, invece di allocare tutti i 256 caratteri, rallenta molto poco e otterrai un aumento di capacità di 100 volte, perché alla fine ottieni solo 1 lettera usata in ogni buffer del puntatore di lettera (che ho soprannominato ” escape “).

Se vuoi ottenere una corrispondenza di stringa del vicino più vicino, ne hai molte in esecuzione in parallelo e raccogli in una gerarchia, quindi distribuisci il tuo errore in modo imparziale. se provi a vicino più vicino con uno solo, allora sei “sbilanciato verso linizio dellalbero.

Commenti

• @MagnusRobertCarlWoot dato che hai lo stesso gavatar come roucer81, o è una coincidenza astronomica di collisione del codice hash o hai lo stesso indirizzo email. Se sei la stessa persona dietro entrambi gli account, dovresti utilizzare il modulo ” contattaci ” per unirli in modo da ottenere il giusto credito per la reputazione guadagnata grazie a voti positivi su questa risposta.