Melyik karakterlánc-keresési algoritmus a valójában a leggyorsabb?

Ez a végrehajtandó keresés típusától függ. Mindegyik algoritmus különösen jól teljesít bizonyos típusú kereséseknél, de nem adta meg a keresések összefüggéseit.

Íme néhány tipikus gondolat a kereséstípusokról:

• Boyer-Moore: a minta előzetes elemzésével és jobbról balra történő összehasonlítással működik. Ha eltérés következik be, akkor a kezdeti elemzés alapján meghatározzuk, hogy a minta mennyivel tolható el w.r.t. a keresett szöveg. Ez különösen jól működik hosszú keresési minták esetén. Különösen szub-lineáris lehet, mivel nem kell elolvasnia a szöveg minden egyes karakterét.

• Knuth-Morris-Pratt: a mintát is előre elemzi , de megpróbálja újrafelhasználni azt, ami a minta kezdeti részében már megegyezett, hogy ne kelljen ezt újra megcsinálni. Ez nagyon jól működhet, ha az ábécé kicsi (pl. DNS-alapok), mivel nagyobb az esélye annak, hogy a keresési minták újrafelhasználható almintákat tartalmaznak.

• Aho- Corasick: Sokat igényel előfeldolgozást, de számos mintához ezt teszi. Ha tudja, hogy ugyanazokat a keresési mintákat fogja keresni újra és újra, akkor ez sokkal jobb, mint a másiké, mert a mintákat csak egyszer kell elemeznie, keresésenként nem egyszer.

Ezért, mint a CS-ben szokás, nincs egyértelmű válasz az összességében legjobb ra. Inkább arról van szó, hogy a megfelelő eszközt válasszák ki a szóban forgó munkához.

Egy másik megjegyzés a legrosszabb esetről: Fontolja meg a legrosszabb eset létrehozásához szükséges keresések fajtáját, és alaposan gondolja át, hogy ezek valóban relevánsak az Ön esetében. Például a Boyer-Moore algoritmus legrosszabb esetének O(mn) bonyolultsága egy keresési mintából és egy olyan szövegből fakad, amelyben mindegyik csak egy karaktert használ (például a >

Bár kissé későn válaszolok erre a kérdésre, de azt hiszem, a Z-Algorithm sokkal gyorsabb, mint bármelyik társa.Legrosszabb komplexitása O (m + n), és nem igényli a minta / szöveg előzetes feldolgozását. Ez a kódolás a többi algoritmushoz képest is nagyon egyszerű.

A következő módon működik.

Például létezik egy S ="abaaba" karakterlánc. Meg kell találnunk a z(i) értékeket a i=0 to len(S)-1 számára. Mielőtt belemennék a magyarázatba, hadd tegyek le néhány meghatározást.

z(i) = nem. a S előtag karaktereinek száma, amely megegyezik a s(i) előtaggal.

s(i) = ith a S utótag.

A következők a s(i) s = "abaaba" értékei.

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

A z értékek rendre

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

Az algoritmus részletes megértéséhez lásd a következő hivatkozásokat.

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

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

Most O (N) kell, hogy megtalálja az összes z értéket előzetes feldolgozás nélkül. Most arra lenne kíváncsi, hogyan lehet ezt a logikát felhasználni az adott karakterlánc mintájának összehangolásához?

Lássuk egy példával. Minta (P): aba, Szöveg (T): aacbabcabaad.

Tegye ezt P $ T formátumba. ($ – olyan karakter, amely nem jelenik meg sem mintában, sem szövegben. Rövid időn belül eljutok a $ fontosságához.)

P$T = aba$aacbabcabaad

Tudjuk, hogy len(P) = 3.

A P$T összes z értéke

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 

Most melyik z(i) = len(P). Ans = 11. Tehát mintánk jelen van a Ans-len(P)-1 = 7 helyen. A -1 a $ karakterhez tartozik.

Most miért $ vagy minden ilyen különleges karakter fontos. Vegye figyelembe a P = "aaa" és T = "aaaaaaa" elemeket. A speciális karakter nélkül az összes z(i) növekményes értékkel rendelkezik. Még mindig megtalálható a minta helyzete a szövegben az alábbi képletekkel:

Feltétel: z(i)> = len(P) és pozíció: Ans-len(P). De az állapot ebben az esetben kissé trükkös és zavaros lesz. Én személy szerint inkább a speciális karaktertechnikát használom.

Megjegyzések

• Magyaráznád itt magad? Külső webhelyekre mutató linkek felhasználhatók a kidolgozáshoz, de a válasz magjának inkább magában a válaszban kell lennie, nem pedig egy másik webhelyre mutató linket kell követnie.
• A z-algoritmus alapvetően megegyezik a kmp. Kétlem, hogy sokkal gyorsabb lenne.
• Egyetértek a @ThomasAhle céggel. A z kiszámítása előfeldolgozás . ‘ azért jó magyarázat. A válasz miatt O(n) módot állítottam fel a KMP előfeldolgozásról Z előfeldolgozásra való áttérésre. Itt

Használja a tartalom címezhető memória , szoftveresen megvalósítva virtuális címzés formájában (betűk betűkre mutatva).

Ez egy átlagos karakterlánc-illesztési algoritmus számára felesleges.

A CAM egyidejűleg rengeteg mintát képes összeilleszteni, körülbelül 128 betűs mintázatig (ha ASCII, ha csak Unicode 64). Ez egy betűhosszonként egy hívás az egyeztetni kívánt karakterláncban, és egy véletlenszerű beolvasás a memóriából a maximális mintahossz hosszánként. Tehát, ha 100 000 betűs karakterláncot elemezne, akár 90 000 000 mintával egyidejűleg (ami körülbelül 128 GiB-re lenne szükség akkora minták számának tárolására), akkor 12 800 000 véletlenszerű olvasmányra lenne szükség a RAM-ból, tehát 1 ms alatt megtörténne. / p>

Így működik a virtuális címzés.

Ha 256 induló címmel kezdem, amelyek az első betűt jelentik, akkor ezek a betűk a következő betűk 256-ra mutatnak. Ha egy minta nem létezik, nem tárolja.

Tehát ha folyamatosan betűket kapcsolok a betűkhöz, akkor olyan, mintha 128 szelet virtuális címzés mutatna a virtuális címzésre.

Ez így lesz dolgozzon —, de hogy 900 000 000 mintát érjen el egyidejűleg, egy utolsó trükköt kell hozzáadni —, és kihasználja annak a ténynek, hogy sok újrakezdéssel kezdi ezeket a levélpuffereket, de később szétszóródik.Ha felsorolja a tartalmat, ahelyett, hogy kiosztaná mind a 256 karaktert, akkor ez nagyon lassan lassul, és “100-szoros kapacitásnövekedést kap, mert alapvetően csak 1 betűt használ minden levélmutató pufferben (amit én átneveztem” escape “).

Ha a legközelebbi szomszéd karakterlánc-egyezést akarod megszerezni, akkor ezek közül sok párhuzamosan fut, és hierarchiában gyűjtesz, így a hibát elfogulatlanul terjeszted. legközelebbi szomszéd csak egy, akkor elfogult vagy a fa kezdete felé.

Megjegyzések

• @MagnusRobertCarlWoot, ha ugyanaz van gavatar, mint a roucer81, vagy a hash-kód ütközésének csillagászati egybeesése, vagy ugyanaz az e-mail címe. Ha ugyanaz a személy áll mindkét fiók mögött, akkor a ” kapcsolatba léphet velünk ” űrlappal egyesítheti őket, hogy megfelelő hitelt kapjon a jó szavazatok révén megszerzett hírnév erre a válaszra.