Vilken strängsökalgoritm är egentligen den snabbaste?

Det beror på vilken typ av sökning du vill utföra. Var och en av algoritmerna fungerar särskilt bra för vissa typer av en sökning, men du har inte angett sammanhanget för dina sökningar.

Här är några typiska tankar om söktyper:

• Boyer-Moore: fungerar genom att föranalysera mönstret och jämföra från höger till vänster. Om en oöverensstämmelse inträffar används den initiala analysen för att avgöra hur långt mönstret kan flyttas w.r.t. texten som söks. Detta fungerar särskilt bra för långa sökmönster. I synnerhet kan det vara sublinjärt, eftersom du inte behöver läsa varje enskild karaktär i din text.

• Knuth-Morris-Pratt: föranalyserar också mönstret , men försöker återanvända vad som redan matchades i den inledande delen av mönstret för att undvika att behöva matcha om det. Detta kan fungera ganska bra, om ditt alfabet är litet (t.ex. DNA-baser), eftersom du får större chans att dina sökmönster innehåller återanvändbara delmönster.

• Aho- Corasick: Behöver mycket förbehandling, men gör det för ett antal mönster. Om du vet att du kommer att leta efter samma sökmönster om och om igen är det här mycket bättre än det andra, eftersom du behöver analysera mönster bara en gång, inte en gång per sökning.

Därför, som vanligt i CS, finns det inget definitivt svar på det övergripande bästa . Det handlar snarare om att välja rätt verktyg för jobbet.

Ytterligare en anmärkning om ditt värsta fall: Tänk på vilka typer av sökningar som krävs för att skapa det värsta fallet och tänk noga dessa är verkligen relevanta i ditt fall. Till exempel O(mn) värsta fall-komplexiteten i Boyer-Moore-algoritmen härrör från ett sökmönster och en text som vardera bara använder ett tecken (som att hitta aaa i aaaaaaaaaaaaaaaaaaaaa) – behöver du verkligen vara snabb för sådana sökningar?

Kommentarer

• Jag har hela det engelska alfabetet eller så att använda och jag uppdaterade frågan, jag är ledsen för att jag inte började med detta vid tiggeriet.
• Och ja jag behöver vara snabb även för sökningar att
• kan du tacka för Z ’ s algoritm och manachar också?

Även om jag är lite sen med att svara på den här frågan, men jag tror att Z-Algorithm är mycket snabbare än dess motsvarigheter.Dess värsta fall är O (m + n) och det kräver ingen förbehandling av mönstret / texten. Det är också väldigt enkelt att koda jämfört med andra algoritmer.

Det fungerar på följande sätt.

Det finns till exempel en sträng S ="abaaba". Vi ska hitta z(i) värden för i=0 to len(S)-1. Innan jag går in i förklaringen, låt mig lägga några definitioner först.

z(i) = nej. av tecken i prefixet för S som matchar prefixet för s(i).

s(i) = ith suffix av S.

Följande är s(i) värden för s = "abaaba".

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

Z-värdena är respektive

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

För detaljerad förståelse av algoritmen, se följande länkar.

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

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

Nu tar det O (N) att hitta alla z -värden utan några förbehandlade omkostnader. Man kan undra nu hur kan man använda den här logiken för att matcha mönster i en given sträng?

Låt oss se med ett exempel. Mönster (P): aba, Text (T): aacbabcabaad.

Sätt detta i form P $ T. ($ – alla tecken som inte visas i varken mönster eller text. Jag kommer till vikten av $ om en liten stund.)

P$T = aba$aacbabcabaad

Vi vet len(P) = 3.

Alla z-värden för P$T är

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 vilka z(i) = len(P). Ans = 11. Så vårt mönster finns vid Ans-len(P)-1 = 7. -1 är för $ karaktär.

Nu varför $ eller någon sådan speciell karaktär är viktig. Tänk på P = "aaa" och T = "aaaaaaa". Utan specialtecknet har alla z(i) inkrementella värden. Man kan fortfarande hitta mönstrets position i text med följande formler:

Villkor: z(i)> = len(P) och position: Ans-len(P). Men tillståndet i det här fallet blir lite knepigt och förvirrande. Jag personligen föredrar att använda specialteckentekniken.

Kommentarer

• Kan du själv förklara det? Att ha länkar till externa webbplatser kan användas för att utarbeta, men kärnan i ett svar borde vara i själva svaret snarare än att behöva följa en länk till en annan webbplats.
• Z-algoritmen är i princip samma som kmp. Jag tvivlar på att det är mycket snabbare.
• Jag håller med @ThomasAhle. Att beräkna z är förbehandling. Det ’ är dock en bra förklaring. Jag lade upp ett O(n) sätt att konvertera från KMP-förbehandling till Z-förbehandling på grund av detta svar. Här

Använd innehåll adresserbart minne , implementerat i programvara i form av virtuell adressering (pekar bokstäver mot bokstäver).

Det är ganska överflödigt med en genomsnittlig strängmatchningsalgoritm.

CAM kan matcha ett stort antal mönster samtidigt, upp till cirka 128 bokstäver (om de är ASCII; om de bara är Unicode 64). Och det är ett samtal per bokstavslängd i strängen du vill matcha med och en slumpmässig läsning från minnet per längd på den maximala mönsterlängden. Så om du analyserade en sträng på 100 000 bokstäver, med upp till 90 000 000 mönster samtidigt (vilket skulle ta cirka 128 GiB för att lagra ett antal mönster som är så stora), skulle det ta 12 800 000 slumpmässiga läsningar från RAM, så det skulle hända på 1 ms. / p>

Så här fungerar den virtuella adresseringen.

Om jag börjar med 256 startadresser, som representerar den första bokstaven, pekar dessa bokstäver på 256 av nästa bokstäver. är obefintlig, du lagrar det inte.

Så om jag fortsätter att länka bokstäver till bokstäver är det som att ha 128 skivor virtuell adressering som pekar på virtuell adressering.

Det kommer att arbeta — men för att komma till 900.000.000 mönster som matchar samtidigt finns det ett sista knep att lägga till det — och det drar nytta av det faktum att du börjar med mycket återanvändning av dessa brevbuffertar, men senare sprids det ut.Om du listar innehållet, istället för att fördela alla 256 tecken, saktar det väldigt lite, och du kommer att få 100 gånger kapacitetsökning, för att du i princip så småningom bara får en bokstav som används i varje bokstavsbuffert (som jag kallade Escape ”).

Om du vill få en närmaste grannsträngsmatch så har du många av dessa som körs parallellt och du samlar i en hierarki, så du sprider ditt fel ut objektivt. om du försöker närmaste granne med bara en, då är du partisk mot trädets början.

Kommentarer

• @MagnusRobertCarlWoot med tanke på att du har samma gavatar som roucer81, det är antingen en astronomisk tillfällighet av hashkodkollision eller så har du samma e-postadress. Om du är samma person bakom båda kontona, ska du använda formuläret ” kontakta oss ” för att slå samman dem så att du får rätt kredit för det rykte som uppnåtts genom röster på detta svar.