Hvilken strengesøgealgoritme er faktisk den hurtigste?

Det afhænger af, hvilken type søgning du vil udføre. Hver af algoritmerne klarer sig særligt godt for visse typer søgninger, men du har ikke angivet sammenhængen for dine søgninger.

Her er nogle typiske tanker om søgetyper:

• Boyer-Moore: fungerer ved at præanalisere mønsteret og sammenligne fra højre mod venstre. Hvis der opstår en uoverensstemmelse, bruges den indledende analyse til at bestemme, hvor langt mønsteret kan forskydes w.r.t. den tekst, der søges i. Dette fungerer især godt ved lange søgemønstre. Især kan det være sublinjært, da du ikke behøver at læse hvert enkelt tegn i din tekst.

• Knuth-Morris-Pratt: analyserer også mønsteret , men forsøger at genbruge det, der allerede var matchet i den indledende del af mønsteret, for at undgå at skulle gentage det. Dette kan fungere ganske godt, hvis dit alfabet er lille (f.eks. DNA-baser), da du får en større chance for, at dine søgemønstre indeholder genbrugelige undermønstre.

• Aho- Corasick: Har brug for meget forbehandling, men gør det for en række mønstre. Hvis du ved, at du vil kigge efter de samme søgemønstre igen og igen, så er dette meget bedre end det andet, fordi du kun skal analysere mønstre en gang, ikke en gang pr. Søgning.

Derfor er der som normalt i CS ikke noget bestemt svar på det samlede bedste . Det handler snarere om at vælge det rigtige værktøj til det aktuelle job.

En anden bemærkning om dit værst tænkelige argument: Overvej de slags søgninger, der kræves for at skabe det værste tilfælde, og tænk grundigt over disse er virkelig relevante i dit tilfælde. F.eks. Stammer O(mn) worst-case kompleksiteten af Boyer-Moore-algoritmen fra et søgemønster og en tekst, der hver kun bruger et tegn (som at finde aaa i aaaaaaaaaaaaaaaaaaaaa) – skal du virkelig være hurtig til sådanne søgninger?

Kommentarer

• Jeg har hele det engelske alfabet eller deromkring at bruge, og jeg opdaterede spørgsmålet, undskyld for ikke at starte med dette ved tiggeriet.
• Og ja, jeg skal være hurtig selv for søgninger som at
• kan du venligst forklare Z ‘ s algoritme og manachar også?

Selvom jeg er lidt forsinket med at besvare dette spørgsmål, men jeg tror Z-Algorithm er meget hurtigere end nogen af dets kolleger.Dens worst-case kompleksitet er O (m + n), og det kræver ingen forbehandling af mønsteret / teksten. Det er også meget let at kode sammenlignet med de andre algoritmer.

Det fungerer på følgende måde.

For eksempel er der en streng S ="abaaba". Vi skal finde z(i) værdier for i=0 to len(S)-1. Før jeg går ind i forklaringen, lad mig lægge nogle definitioner først.

z(i) = nej. af tegn i præfikset for S, der matcher præfikset for s(i).

s(i) = ith suffiks for S.

Følgende er s(i) værdier for s = "abaaba".

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

Z-værdierne er henholdsvis

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

For detaljeret forståelse af algoritmen henvises til følgende links.

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

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

Nu tager det O (N) at finde alle z værdier uden nogen forbehandlingsomkostninger. Man vil undre sig over, hvordan kan man bruge denne logik til at matche mønster i en given streng?

Lad os se med et eksempel. Mønster (P): aba, Tekst (T): aacbabcabaad.

Sæt dette i form P $ T. ($ – ethvert tegn, der ikke vises i hverken mønster eller tekst. Jeg kommer til vigtigheden af $ om lidt.)

P$T = aba$aacbabcabaad

Vi kender len(P) = 3.

Alle z-værdier for P$T er

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 

Nu hvilken z(i) = len(P). Ans = 11. Så vores mønster er til stede ved Ans-len(P)-1 = 7. -1 er til $ tegn.

Nu hvorfor $ eller en sådan speciel karakter er vigtig. Overvej P = "aaa" og T = "aaaaaaa". Uden specialtegnet vil alle z(i) have trinvise værdier. Man kan stadig finde mønsterpositionen i tekst med nedenstående formler:

Tilstand: z(i)> = len(P) og position: Ans-len(P). Men tilstanden i dette tilfælde bliver lidt vanskelig og forvirrende. Jeg foretrækker personligt at bruge den specielle karakterteknik.

Kommentarer

• Kan du selv forklare det her? At have links til eksterne websteder kan bruges til at uddybe, men kernen i et svar skal være i selve svaret i stedet for at skulle følge et link til et andet websted.
• Z-algoritmen er dybest set den samme som kmp. Jeg tvivler på, at det er meget hurtigere.
• Jeg er enig med @ThomasAhle. Beregning af z er forbehandling. Det ‘ er dog en god forklaring. Jeg lagde en O(n) måde at konvertere fra KMP-forbehandling til Z-forbehandling på grund af dette svar. Her

Brug indholdsadresserbar hukommelse , implementeret i software i form af virtuel adressering (peger bogstaver til bogstaver).

Det er lidt overflødigt med en gennemsnitlig strengtilpasningsalgoritme.

CAM kan matche et stort antal mønstre samtidigt, op til ca. 128 bogstaver (hvis de er ASCII; hvis de kun er Unicode 64). Og det er et opkald pr. Bogstavlængde i den streng, du vil matche og en tilfældig læsning fra hukommelsen pr. Længde af den maksimale mønsterlængde. Så hvis du analyserede en streng på 100.000 bogstaver med op til 90.000.000 mønstre samtidigt (hvilket ville tage cirka 128 GiB for at gemme et antal mønstre, der var så store), ville det tage 12.800.000 tilfældige læsninger fra RAM, så det ville ske i 1 ms. / p>

Sådan fungerer den virtuelle adressering.

Hvis jeg starter med 256 startoff-adresser, som repræsenterer det første bogstav, peger disse bogstaver på 256 af de næste bogstaver. Hvis et mønster ikke findes, gemmer du det ikke.

Så hvis jeg fortsætter med at linke bogstaver til bogstaver, er det som at have 128 skiver virtuel adressering, der peger på virtuel adressering.

Det vil arbejde — men for at komme til 900.000.000 mønstre, der matcher samtidigt, er der et sidste trick at tilføje til det —, og det drager fordel af det faktum, at du starter med en masse genbrug af disse brevbuffere, men senere spreder det ud.Hvis du viser indholdet, i stedet for at tildele alle 256 tegn, sænkes det meget lidt, og du får en kapacitetsforøgelse på 100 gange, fordi du i bund og grund kun får 1 bogstav brugt i hver bogstavpegerbuffer (som jeg kaldte ” escape “).

Hvis du vil få en nærmeste nabo-streng match, så har du mange af disse kører parallelt, og du samler i et hierarki, så du spreder din fejl ud upartisk. hvis du prøver at nærmeste nabo med kun en, så er du forudindtaget i starten af træet.

Kommentarer

• @MagnusRobertCarlWoot i betragtning af at du har det samme gavatar som roucer81, det er enten en astronomisk sammenfald af hash-kodekollision, eller du har den samme e-mail-adresse. Hvis du er den samme person bag begge konti, skal du bruge ” kontakt os ” til at fusionere dem, så du får den rette kredit for omdømmet opnået gennem opstemninger om dette svar.