Který algoritmus pro vyhledávání řetězců je ve skutečnosti nejrychlejší?

Záleží na druhu vyhledávání, které chcete provést. Každý z algoritmů funguje zvlášť dobře pro určité typy vyhledávání, ale neuvedli jste kontext svých vyhledávání.

Zde je několik typických myšlenek na typy vyhledávání:

• Boyer-Moore: funguje tak, že předběžně analyzuje vzor a porovnává zprava doleva. Pokud dojde k nesouladu, použije se počáteční analýza k určení, jak daleko lze vzor posunout w.r.t. hledaný text. To funguje zvláště dobře u dlouhých vyhledávacích vzorů. Zejména může být sublineární, protože nemusíte číst všechny jednotlivé znaky textu.

• Knuth-Morris-Pratt: také předběžně analyzuje vzor , ale pokusí se znovu použít vše, co již bylo shodné v počáteční části vzoru, aby se předešlo tomu, že to bude nutné opakovat. To může docela dobře fungovat, pokud je vaše abeceda malá (např. Báze DNA), protože máte větší šanci, že vaše vyhledávací vzory obsahují opakovaně použitelné podvzorky.

• Aho- Corasick: Potřebuje hodně předzpracování, ale dělá to pro řadu vzorů. Pokud víte, že budete znovu a znovu hledat stejné vzory vyhledávání, pak je to mnohem lepší než ostatní, protože je třeba analyzovat vzory pouze jednou, ne jednou pro každé vyhledávání.

Proto, jako obvykle v CS, neexistuje jednoznačná odpověď na celkově nejlepší . Jde spíše o výběr správného nástroje pro danou práci.

Další poznámka k uvažování v nejhorším případě: Zvažte druhy vyhledávání potřebné k vytvoření tohoto nejhoršího případu a důkladně zvažte, zda ve vašem případě jsou skutečně relevantní. Například O(mn) nejhorší složitost Boyer-Moorova algoritmu vychází z vyhledávacího vzoru a textu, který každý používá pouze jeden znak (například nalezení aaa in aaaaaaaaaaaaaaaaaaaaa) – opravdu potřebujete být na takové hledání rychlý?

Komentáře

• Mám k dispozici celou anglickou abecedu a aktualizoval jsem otázku, omlouvám se, že jsem s tím nezačal hned na začátku.
• A ano, musím být rychlý i při vyhledávání jako že
• můžete prosím rozvíjet algoritmus Z ‚ a také manachar?

Ačkoli na odpověď na tuto otázku přicházím trochu pozdě, myslím si, že Z-Algorithm je mnohem rychlejší než kterýkoli z jejích protějšků.Jeho nejhorší složitost je O (m + n) a nevyžaduje žádné předzpracování vzoru / textu. Je také velmi snadné jej kódovat ve srovnání s ostatními algoritmy.

Funguje následujícím způsobem.

Například existuje řetězec S ="abaaba". Najdeme z(i) hodnoty pro i=0 to len(S)-1. Než se pustím do vysvětlení, dovolte mi nejprve stanovit některé definice.

z(i) = no. znaků předpony S, která odpovídá prefixu s(i).

s(i) = ith přípona S.

Následují s(i) hodnoty pro s = "abaaba".

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

Hodnoty z jsou jednotlivě

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

Podrobné porozumění algoritmu naleznete v následujících odkazech.

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

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

Nyní trvá O (N) najít všechny z hodnoty bez jakékoli režie předběžného zpracování. Člověk by si teď říkal, jak můžete pomocí této logiky porovnat vzor v daném řetězci?

Podívejme se na příklad. Vzor (P): aba, Text (T): aacbabcabaad.

Vložte to ve tvaru P $ T. ($ – jakýkoli znak, který se neobjeví ani ve vzoru, ani v textu. Za chvíli přijdu na význam $.)

P$T = aba$aacbabcabaad

Známe len(P) = 3.

Všechny hodnoty z P$T jsou

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 

Nyní z(i) = len(P). Ans = 11. Náš vzor je tedy k dispozici na Ans-len(P)-1 = 7. -1 je pro $ znak.

Proč $ nebo každá taková speciální postava je důležitá. Zvažte P = "aaa" a T = "aaaaaaa". Bez zvláštního znaku budou mít všechny z(i) přírůstkové hodnoty. Pozici vzoru v textu lze stále najít pomocí následujících vzorců:

Podmínka: z(i)> = len(P) and Position: Ans-len(P). Ale podmínka v tomto případě se stává trochu složitější a matoucí. Osobně dávám přednost použití speciální techniky znaků.

Komentáře

• Můžete to zde vysvětlit sami? K rozpracování lze použít odkazy na externí stránky, ale jádro odpovědi by mělo být spíše v samotné odpovědi, než aby bylo nutné následovat odkaz na jinou stránku.
• Algoritmus z je v zásadě stejný jako kmp. Pochybuji, že je to mnohem rychlejší.
• Souhlasím s @ThomasAhle. Výpočet z je předzpracován. ‚ je to však dobré vysvětlení. Kvůli této odpovědi jsem vytvořil O(n) způsob převodu z předběžného zpracování KMP na předběžné zpracování Z. Zde

Použít obsah adresovatelná paměť implementovaná v softwaru ve formě virtuálního adresování (směrování písmen na písmena).

Je to trochu nadbytečné k průměrnému algoritmu shody řetězců.

CAM může odpovídat velkému počtu vzorů současně, až do 128-písmenných vzorů (pokud jsou ASCII; pokud jsou Unicode pouze 64). A je to jedno volání na délku písmene v řetězci, kterému chcete odpovídat, a jedno náhodné čtení z paměti na délku maximální délky vzoru. Pokud byste tedy analyzovali řetězec 100 000 písmen s až 90 000 000 vzory současně (což by trvalo asi 128 GiB, aby se uložil počet tak velkých vzorů), trvalo by to 12 800 000 náhodných čtení z paměti RAM, takže by se to stalo za 1 ms.

Takto funguje virtuální adresování.

Pokud začnu s 256 adresami startoff, které představují první písmeno, tato písmena ukazují na 256 dalších písmen. Pokud vzor neexistuje, neukládáte to.

Takže pokud neustále spojuji písmena s písmeny, je to jako mít 128 plátků virtuálního adresování směřujících na virtuální adresování.

To bude fungujte —, ale abyste získali 900 000 000 vzorů současně, existuje poslední trik, který k tomu můžete přidat — a využívat to skutečnosti, že začnete s velkým množstvím opětovného použití těchto vyrovnávacích pamětí pro dopisy, ale později se to rozptýlí.Pokud uvedete obsah, místo přidělení všech 256 znaků se zpomalí jen velmi málo a „získáte 100násobné zvýšení kapacity, protože v zásadě nakonec získáte pouze jedno písmeno použité v každé vyrovnávací paměti ukazatele na písmeno (kterou jsem zkopíroval“) uniknout „).

Pokud chcete získat shodu řetězce nejbližšího souseda, pak mnoho z nich běží paralelně a shromažďujete v hierarchii, takže svou chybu rozšíříte nezaujatě. pokud se pokusíte nejbližší soused pouze s jedním, pak budete „předpojatí na začátek stromu.

Komentáře

• @MagnusRobertCarlWoot vzhledem k tomu, že máte stejné gavatar jako roucer81, je to buď astronomická náhoda kolize hash kódu, nebo máte stejnou e-mailovou adresu. Pokud za oběma účty stojíte stejná osoba, měli byste použít formulář “ kontaktujte nás “ a sloučit je, abyste získali řádný kredit pro reputace získaná hlasováním o této odpovědi.