Mikä merkkijonohakualgoritmi on oikeastaan nopein?

Se riippuu suoritettavan haun tyypistä. Kukin algoritmeista toimii erityisen hyvin tietyntyyppisissä hauissa, mutta et ole ilmoittanut hakujen kontekstia.

Tässä on joitain tyypillisiä ajatuksia hakutyypeistä:

• Boyer-Moore: toimii analysoimalla kuvio ennalta ja vertaamalla sitä oikealta vasemmalle. Jos esiintyy ristiriitaa, alkuanalyysin avulla määritetään, kuinka pitkälle kuviota voidaan siirtää w.r.t. haettava teksti. Tämä toimii erityisen hyvin pitkillä hakumalleilla. Erityisesti se voi olla alalineaarinen, koska sinun ei tarvitse lukea tekstisi jokaista merkkiä.

• Knuth-Morris-Pratt: myös analysoi mallin ennakolta , mutta yrittää käyttää uudelleen mitä tahansa, joka oli jo sovitettu mallin alkuosaan, jotta sitä ei tarvitsisi uudistaa. Tämä voi toimia varsin hyvin, jos aakkosesi on pieni (esim. DNA-emäkset), kun saat suuremman mahdollisuuden, että hakumallisi sisältävät uudelleenkäytettäviä alamalleja.

• Aho- Corasick: Tarvitsee paljon esikäsittelyä, mutta tekee niin useille malleille. Jos tiedät, että etsit samoja hakumalleja uudestaan ja uudestaan, tämä on paljon parempi kuin toinen, koska sinun on analysoitava kuvioita vain kerran, ei kerran hakua kohti.

Näin ollen, kuten CS: ssä tavallisesti, kaiken parhaaseen ei ole tarkkaa vastausta. Kyse on pikemminkin oikean työkalun valitsemisesta käsiteltävään työhön.

Toinen huomautus pahimman tapauksenne perusteluista: Harkitse, minkä tyyppisiä hakuja tarvitaan kyseisen pahimman tapauksen luomiseen ja mietittekää perusteellisesti nämä ovat todella merkityksellisiä tapauksessasi. Esimerkiksi Boyer-Moore-algoritmin O(mn) pahimman tapainen monimutkaisuus johtuu hakukuviosta ja tekstistä, joissa kukin käyttää vain yhtä merkkiä (kuten aaa kielellä aaaaaaaaaaaaaaaaaaaaa) – tarvitsetko todella nopeita tällaisia hakuja?

Kommentit

• Minulla on käytettävissään koko englannin aakkoset, joten päivitin kysymyksen, anteeksi, että en aloittanut tätä kerjäämisen yhteydessä.
• Ja kyllä, minun on oltava nopea myös sellaisissa hauissa, kuten että
• voitko palata Z ’ s -algoritmiin ja manachariin?

Vaikka olen vasta myöhässä vastaamaan tähän kysymykseen, luulen, että Z-Algorithm on paljon nopeampi kuin muut kollegat.Sen pahimmassa tapauksessa monimutkaisuus on O (m + n), eikä se vaadi kuvion / tekstin esikäsittelyä. Se on myös erittäin helppo koodata muihin algoritmeihin verrattuna.

Se toimii seuraavalla tavalla.

Esimerkiksi on merkkijono S ="abaaba". Meidän on löydettävä z(i) -arvot kohteelle i=0 to len(S)-1. Ennen kuin selitän asiaa, anna minun laittaa ensin joitain määritelmiä.

z(i) = ei. merkkien S etuliitteen merkkejä, jotka vastaavat s(i) -etuliitettä.

s(i) = ith pääte S.

Seuraavat ovat s(i) arvot kohteelle s = "abaaba".

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

Z-arvot ovat vastaavasti

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

Yksityiskohtainen käsitys algoritmista on seuraavissa linkeissä.

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

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

Nyt O: lta (N) tarvitaan kaikkien z -arvojen löytäminen ilman esikäsittelykuluja. Voisi nyt miettiä, kuinka voit käyttää tätä logiikkaa vastaamaan tietyn merkkijonon mallia?

Katsotaanpa esimerkki. Kuvio (P): aba, Teksti (T): aacbabcabaad.

Laita tämä muotoon P $ T. ($ – mikä tahansa merkki, jota ei näy kuviossa tai tekstissä. Tulen $ -merkin tärkeyteen hetken kuluttua.)

P$T = aba$aacbabcabaad

Tiedämme len(P) = 3.

Kaikki P$T -arvot ovat

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 

Nyt mikä z(i) = len(P). Ans = 11. Joten malli on läsnä kohdassa Ans-len(P)-1 = 7. -1 on tarkoitettu $ -merkille.

Miksi $ tai kaikki tällaiset erikoismerkit ovat tärkeitä. Harkitse P = "aaa" ja T = "aaaaaaa". Ilman erikoismerkkiä kaikilla z(i) on inkrementaaliarvoja. Kuvion sijainti tekstistä löytyy edelleen seuraavien kaavojen avulla:

Ehto: z(i)> = len(P) ja sijainti: Ans-len(P). Mutta tässä tapauksessa tilasta tulee hieman hankala ja hämmentävä. Pidän henkilökohtaisesti mieluummin erikoismerkkitekniikkaa.

kommentit

• Voisitko selittää sen itse täällä? Ulkopuolisten sivustojen linkkien käyttämistä voidaan käyttää tarkentamiseen, mutta vastauksen ytimen tulisi olla itse vastauksessa sen sijaan, että sen pitäisi seurata linkkiä toiselle sivustolle.
• Z-algoritmi on periaatteessa sama kuin kmp. Epäilen, että se on paljon nopeampi.
• Olen samaa mieltä @ThomasAhlen kanssa. Laskeminen z on esikäsittely. Se ’ on kuitenkin hyvä selitys. Laittoin O(n) tavan muuntaa KMP-esikäsittely Z-esikäsittelyksi tämän vastauksen takia. Täällä

Käytä sisällön osoitettava muisti , toteutettu ohjelmistossa virtuaalisen osoitteen muodossa (osoittamalla kirjaimille kirjaimille).

Se on tavallaan tarpeeton keskimääräiselle merkkijonoa vastaavalle algoritmille.

CAM voi sovittaa samanaikaisesti valtavan määrän kuvioita, jopa noin 128 kirjainta (jos ne ovat ASCII; jos ne ovat vain Unicode vain 64). Ja se on yksi kutsu kutakin kirjoituspituutta varten merkkijonossa, johon haluat sovittaa, ja yksi satunnaisesti luettu muistista kutakin kuvion enimmäispituutta kohti. Joten jos analysoit 100 000 kirjainjonoa, jopa 90 000 000 kuviota samanaikaisesti (mikä vie noin 128 GiB: tä, jotta tallentaisi niin suuren määrän kuvioita), se vie 12800000 satunnaislukua RAM-muistista, joten se tapahtuisi 1 ms: ssä. / p>

Näin virtuaalinen osoite toimii.

Jos aloitan 256 aloitusosoitteella, jotka edustavat ensimmäistä kirjainta, nämä kirjaimet osoittavat seuraavien kirjainten 256: een. Jos kuvio ei ole olemassa, et tallenna sitä.

Joten jos jatkan linkittämistä kirjeistä kirjeisiin, on kuin 128 viipaletta virtuaalista osoitusta, jotka osoittavat virtuaaliseen osoitteistoon.

Se toimi —, mutta päästäksesi 900 000 000 malliin samanaikaisesti, siihen on vielä yksi viimeinen temppu lisättävä — ja se hyödyntää tosiasia, että aloitat näiden kirjepuskureiden uudelleenkäytöllä, mutta myöhemmin se hajoaa.Jos luet luettelon sisällön, sen sijaan että jaat kaikki 256 merkkiä, se hidastuu hyvin vähän, ja ”saat 100-kertaisen kapasiteetin kasvun, koska lopulta saat vain yhden kirjaimen käytettäväksi jokaisessa kirjainpuskurissa (jonka kopioin”) paeta ”).

Jos haluat saada lähimmän naapurin merkkijono-ottelun, monet näistä ovat käynnissä rinnakkain ja keräät hierarkiassa, joten levität virhettäsi puolueettomasti. jos yrität lähin naapuri vain yhdellä, olet puolueellinen puun alkuun.

Kommentit

• @MagnusRobertCarlWoot, koska sinulla on sama gavatar kuin roucer81, se on joko hash-koodin törmäyksen tähtitieteellinen sattuma tai sinulla on sama sähköpostiosoite. Jos olet sama henkilö molempien tilien takana, sinun tulee yhdistää ne ” ota yhteyttä meihin ” -lomakkeella, jotta saat asianmukaisen hyvityksen tämän vastauksen myönteisten äänien kautta saatu maine.