Care algoritm de căutare de șiruri este de fapt cel mai rapid?

Depinde de tipul de căutare pe care doriți să îl efectuați. Fiecare dintre algoritmi funcționează deosebit de bine pentru anumite tipuri de căutare, dar nu ați indicat contextul căutărilor dvs.

Iată câteva gânduri tipice despre tipurile de căutare:

• Boyer-Moore: funcționează preanalizând modelul și comparând de la dreapta la stânga. Dacă apare o nepotrivire, analiza inițială este utilizată pentru a determina cât de mult poate fi deplasat tiparul w.r.t. textul fiind căutat. Acest lucru funcționează deosebit de bine pentru tiparele de căutare lungi. În special, poate fi sub-liniar, deoarece nu este nevoie să citiți fiecare caracter al textului dvs.

• Knuth-Morris-Pratt: de asemenea, pre-analizează modelul , dar încearcă să reutilizeze orice a fost deja asortat în partea inițială a modelului, pentru a evita să fie nevoit să revanșeze acest lucru. Acest lucru poate funcționa destul de bine, dacă alfabetul dvs. este mic (f.ex. baze ADN), deoarece aveți șanse mai mari ca modelele dvs. de căutare să conțină sub-modele reutilizabile.

• Aho- Corasick: Are nevoie de multă prelucrare, dar o face pentru mai multe tipare. Dacă știți că veți căuta aceleași modele de căutare din nou și din nou, atunci acest lucru este mult mai bun decât celălalt, deoarece trebuie să analizați modelele o singură dată, nu o dată pe căutare.

Prin urmare, ca de obicei în CS, nu există un răspuns clar la global best . Este mai degrabă o chestiune de a alege instrumentul potrivit pentru locul de muncă.

O altă notă asupra raționamentului dvs. în cel mai rău caz: luați în considerare tipurile de căutări necesare pentru a crea acel caz cel mai rău și gândiți-vă bine dacă acestea sunt cu adevărat relevante în cazul dumneavoastră. De exemplu, O(mn) cea mai rea complexitate a algoritmului Boyer-Moore provine dintr-un model de căutare și un text care utilizează fiecare un singur caracter (cum ar fi găsirea aaa în aaaaaaaaaaaaaaaaaaaaa) – chiar trebuie să fiți rapid pentru astfel de căutări?

Comentarii

• Am tot alfabetul englez de folosit și am actualizat întrebarea, îmi pare rău că nu am început cu asta la cerșit.
• Și da, trebuie să fiu rapid chiar și pentru căutări precum că
• poți vă rog să eloborați algoritmul Z ‘ și manachar?

Deși am întârziat să răspund la această întrebare, dar cred că Z-Algorithm este mult mai rapid decât oricare dintre omologii săi.Complexitatea sa în cel mai rău caz este O (m + n) și nu necesită preprocesare a modelului / textului. De asemenea, este foarte ușor de codat în comparație cu ceilalți algoritmi.

Funcționează în modul următor.

De exemplu, există un șir S ="abaaba". Trebuie să găsim valori z(i) pentru i=0 to len(S)-1. Înainte de a intra în explicație, permiteți-mi să stabilesc mai întâi câteva definiții.

z(i) = nu. de caractere ale prefixului S care se potrivește cu prefixul s(i).

s(i) = ith sufixul lui S.

Următoarele sunt s(i) valori pentru s = "abaaba".

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

Valorile z sunt respectiv

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

Pentru înțelegerea detaliată a algoritmului, consultați următoarele linkuri.

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

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

Acum este nevoie de O (N) pentru a găsi toate valorile z fără nicio cheltuială de pre-procesare. Ne-am întreba acum cum poți folosi această logică pentru a se potrivi cu un șablon dat?

Să vedem cu un exemplu. Șablon (P): aba, Text (T): aacbabcabaad.

Puneți acest lucru în forma P $ T. ($ – orice caracter care nu apare nici în model, nici în text. Voi ajunge la importanța $ peste puțin timp.)

P$T = aba$aacbabcabaad

Știm len(P) = 3.

Toate valorile z ale P$T sunt

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 

Acum z(i) = len(P). Ans = 11. Deci modelul nostru este prezent la Ans-len(P)-1 = 7. -1 este pentru caracterul $.

Acum de ce $ sau orice astfel de caracter special este important. Luați în considerare P = "aaa" și T = "aaaaaaa". Fără caracterul special, toate z(i) vor avea valori incrementale. Poți găsi în continuare poziția modelului în text cu formulele de mai jos:

Stare: z(i)> = len(P) și Poziție: Ans-len(P). Dar starea în acest caz devine puțin dificilă și confuză. Personal prefer să folosesc tehnica specială a personajelor.

Comentarii

• Ați putea să o explicați singur aici? A avea linkuri către site-uri externe poate fi folosit pentru a elabora, dar nucleul unui răspuns ar trebui să fie în răspunsul în sine, mai degrabă decât să urmeze un link către un alt site.
• Algoritmul z este practic același cu kmp. Mă îndoiesc că este mult mai rapid.
• Sunt de acord cu @ThomasAhle. Calculul z este preprocesare. Totuși, ‘ este o explicație bună. Am creat o modalitate O(n) de conversie de la pre-procesare KMP la pre-procesare Z, datorită acestui răspuns. Aici

Utilizați memorie adresabilă conținut , implementată în software sub formă de adresare virtuală (indicând litere către litere).

Este cam superflu pentru un algoritm mediu de potrivire a șirurilor.

CAM poate potrivi simultan un număr mare de modele, până la aproximativ 128 de litere (dacă sunt ASCII; dacă sunt numai Unicode 64). Și este un apel pentru fiecare lungime a literei în șirul cu care doriți să se potrivească și o citire aleatorie din memorie pentru fiecare lungime a lungimii maxime a modelului. Deci, dacă ați analiza un șir de 100.000 de litere, cu până la 90.000.000 de modele simultan (care ar dura aproximativ 128 GiB pentru a stoca un număr de modele atât de mari), ar fi nevoie de 12.800.000 de citiri aleatorii din RAM, deci s-ar întâmpla în 1 ms.

Iată cum funcționează adresarea virtuală.

Dacă încep cu 256 de adrese de pornire, care reprezintă prima literă, aceste litere indică 256 din literele următoare. Dacă un model este inexistent, nu-l stocați.

Deci, dacă continuu să leg literele cu literele, este ca și cum ați avea 128 de felii de adresare virtuală care indică adresarea virtuală.

funcționează — dar pentru a ajunge la 900.000.000 de modele care se potrivesc simultan, există un ultim truc pentru a-l adăuga — și profită a faptului că începeți cu multă reutilizare a acestor tampoane de scrisori, dar mai târziu se împrăștie.Dacă enumerați conținutul, în loc să alocați toate cele 256 de caractere, atunci acesta încetinește foarte puțin și veți obține o creștere a capacității de 100 de ori, deoarece în cele din urmă veți primi doar 1 literă utilizată în fiecare buffer de pointer pentru litere (pe care l-am numit ” escape „).

Dacă doriți să obțineți o potrivire de șir cu cel mai apropiat vecin, atunci aveți multe dintre acestea rulând în paralel și le colectați într-o ierarhie, astfel încât să vă răspândiți eroarea în mod imparțial. dacă încercați să cel mai apropiat vecin cu doar unul, apoi „ești părtinitor spre începutul copacului.

Comentarii

• @MagnusRobertCarlWoot având în vedere că ai același lucru gavatar ca roucer81, este fie o coincidență astronomică a coliziunii codului hash, fie aveți aceeași adresă de e-mail. Dacă sunteți același individ din spatele ambelor conturi, ar trebui să utilizați formularul ” contactați-ne ” pentru a le îmbina, astfel încât să obțineți un credit adecvat pentru reputația câștigată prin voturi pozitive asupra acestui răspuns.