Hvilken strengesøkealgoritme er faktisk den raskeste?

Det kommer an på hva slags søk du vil utføre. Hver av algoritmene fungerer spesielt bra for visse typer søk, men du har ikke oppgitt sammenhengen for søkene dine.

Her er noen typiske tanker om søketyper:

• Boyer-Moore: fungerer ved å forhåndsanalisere mønsteret og sammenligne fra høyre til venstre. Hvis det oppstår en uoverensstemmelse, brukes den innledende analysen for å bestemme hvor langt mønsteret kan forskyves w.r.t. teksten det søkes etter. Dette fungerer spesielt bra for lange søkemønstre. Spesielt kan det være sublinjært, ettersom du ikke trenger å lese hvert eneste tegn i teksten.

• Knuth-Morris-Pratt: analyserer også mønsteret på forhånd. , men prøver å bruke det som allerede var matchet i den første delen av mønsteret for å unngå å måtte omkampe det. Dette kan fungere ganske bra, hvis alfabetet ditt er lite (f.eks. DNA-baser), da du får større sjanse for at søkemønstrene inneholder gjenbrukbare undermønstre.

• Aho- Corasick: Trenger mye forbehandling, men gjør det for en rekke mønstre. Hvis du vet at du vil lete etter de samme søkemønstrene igjen og igjen, så er dette mye bedre enn det andre, fordi du trenger å analysere mønstre bare en gang, ikke en gang per søk.

Derfor er det, som vanlig i CS, ikke noe definitivt svar på generelt best . Det handler snarere om å velge riktig verktøy for den aktuelle jobben.

En annen merknad om din worst-case resonnement: Vurder hvilke søk du trenger for å lage det verste tilfellet, og tenk grundig over om disse er veldig relevante i ditt tilfelle. For eksempel kommer O(mn) worst-case kompleksiteten til Boyer-Moore-algoritmen fra et søkemønster og en tekst som hver bruker bare ett tegn (som å finne aaa i aaaaaaaaaaaaaaaaaaaaa) – trenger du virkelig å være rask for slike søk?

Kommentarer

• Jeg har hele det engelske alfabetet eller så å bruke, og jeg oppdaterte spørsmålet, beklager at jeg ikke begynte med dette på tiggeriet.
• Og ja jeg trenger å være rask selv for søk som at
• kan du snakke om Z ‘ s algoritme og manachar også?

Selv om jeg er litt sen med å svare på dette spørsmålet, men jeg tror Z-Algorithm er mye raskere enn noen andre.Dens verste fall er O (m + n), og det krever ingen forbehandling av mønsteret / teksten. Det er også veldig enkelt å kode i forhold til de andre algoritmene.

Det fungerer på følgende måte.

Det er for eksempel en streng S ="abaaba". Vi skal finne z(i) verdier for i=0 to len(S)-1. Før jeg går inn i forklaringen, la meg legge noen definisjoner først.

z(i) = nei. av tegn i prefikset til S som samsvarer med prefikset til s(i).

s(i) = ith suffiks av S.

Følgende er s(i) verdier for s = "abaaba".

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

Z-verdiene er henholdsvis

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

For detaljforståelse av algoritmen, se følgende lenker.

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

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

Nå tar det O (N) å finne alle z verdiene uten noen forhåndsbehandlingsomkostninger. Man ville lure på nå, hvordan kan du bruke denne logikken til å matche mønster i en gitt streng?

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

Sett dette i form P $ T. ($ – alle tegn som ikke vises i verken mønster eller tekst. Jeg kommer til viktigheten av $ om en liten stund.)

P$T = aba$aacbabcabaad

Vi vet len(P) = 3.

Alle z-verdiene til 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 

Nå hvilke z(i) = len(P). Ans = 11. Så mønsteret vårt er til stede ved Ans-len(P)-1 = 7. -1 er for $ tegn.

Nå hvorfor $ eller en slik spesiell karakter er viktig. Tenk på P = "aaa" og T = "aaaaaaa". Uten spesialtegnet vil alle z(i) ha inkrementelle verdier. Man kan fremdeles finne posisjonen til mønster i tekst med formlene nedenfor:

Tilstand: z(i)> = len(P) og posisjon: Ans-len(P). Men tilstanden i dette tilfellet blir litt vanskelig og forvirrende. Jeg personlig foretrekker å bruke spesialtegneteknikken.

Kommentarer

• Kan du forklare det selv her? Å ha lenker til eksterne nettsteder kan brukes til å utdype, men kjernen i et svar bør være i selve svaret i stedet for å måtte følge en lenke til et annet nettsted.
• Z-algoritmen er i utgangspunktet den samme som kmp. Jeg tviler på at det er mye raskere.
• Jeg er enig med @ThomasAhle. Databehandling z er forbehandling. Det er ‘ en god forklaring. Jeg la opp en O(n) måte å konvertere fra KMP-forbehandling til Z-forbehandling på grunn av dette svaret. Her

Bruk innhold adresserbart minne , implementert i programvare i form av virtuell adressering (peker bokstaver mot bokstaver).

Det er overflødig for en gjennomsnittlig strengmatchingsalgoritme.

CAM kan matche et stort antall mønstre samtidig, opptil omtrent 128 bokstavsmønstre (hvis de er ASCII; hvis de bare er Unicode 64). Og det er ett anrop per bokstavlengde i strengen du vil matche og en tilfeldig avlesning fra minnet per lengde på maksimal mønsterlengde. Så hvis du analyserte en 100 000 bokstavstreng med opptil 90 000 000 mønstre samtidig (som ville ta omtrent 128 GiB for å lagre et antall mønstre som var så store), ville det ta 12 800 000 tilfeldige avlesninger fra RAM, så det ville skje på 1 ms. / p>

Slik fungerer den virtuelle adresseringen.

Hvis jeg begynner med 256 startadresser, som representerer første bokstav, peker disse bokstavene til 256 av de neste bokstavene. ikke finnes, lagrer du det ikke.

Så hvis jeg fortsetter å knytte bokstaver til bokstaver, er det som å ha 128 stykker virtuell adressering som peker på virtuell adressering.

Det vil arbeid — men for å komme til 900.000.000 mønstre samtidig som samsvarer, er det et siste triks å legge til det — og det utnytter av det faktum at du begynner med mye gjenbruk av disse brevbufferne, men senere sprer den ut.Hvis du lister opp innholdet, i stedet for å tildele alle 256 tegn, reduserer det veldig lite, og du vil få 100 ganger kapasitetsøkning, fordi du i utgangspunktet bare får 1 bokstav brukt i hver bokstavpekerbuffer (som jeg kalt » unnslippe «).

Hvis du vil få en nærmeste nabo-strengkamp, har du mange av disse som kjører parallelt, og du samler deg i et hierarki, så du sprer feilen din ut objektiv. hvis du prøver å nærmeste nabo med bare en, så er du partisk mot starten av treet.

Kommentarer

• @MagnusRobertCarlWoot gitt at du har det samme gavatar som roucer81, er det enten en astronomisk tilfeldighet av hash-kodekollisjon eller du har samme e-postadresse. Hvis du er den samme personen bak begge kontoene, bør du bruke » kontakt oss » for å slå dem sammen slik at du får riktig kreditt for omdømmet oppnådd gjennom oppstemninger om dette svaret.