Suffiksitaulukko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6.11.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Suffiksitaulukko on leksikografisesti lajiteltu taulukko kaikista merkkijonon jälkiliitteistä . Eugene Myers ja Udy Manber suunnittelivat tämän tietorakenteen edullisemmaksi vaihtoehdoksi suffiksipuulle muistivaatimusten suhteen. Sitä käytetään usein silloin, kun tarvitaan nopeita osamerkkijonohakuja, kuten Burrows-Wheeler Transformissa (BWT), ja tietorakenteena hakuhakemistossa .

Esimerkki

Harkitse merkkijonoa "abrakadabra", joka on 11 merkkiä pitkä.

abrakadabra 1 2 3 4 5 6 7 8 9 10 11

Lajiteltu luettelo sen jälkiliitteistä:

a abra abrakadabra acadabra adabra rintaliivit bracadabra cadabra dabra ra racadabra

Tämän merkkijonon päätetaulukko on {11,8,1,4,6,9,2,5,7,10,3}, koska "a"-liite alkaa 11. merkillä ja "abra"-liite alkaa 8. merkki. go ja niin edelleen viimeiseen loppuliitteeseen "racadabra", joka alkaa alkuperäisen sanan kolmannella merkillä.

Nyt käyttämällä tätä taulukkoa voit helposti löytää kaikki alimerkkijonot. Jos esimerkiksi haluat löytää alimerkkijonon "ab", riittää, kun etsit kaikki "ab":lla alkavat päätteet. Lajittelemalla aakkosjärjestykseen ne ovat vierekkäin. Käyttämällä binaarihakua löydämme 2. ja 3. päätteet "abra" ja "abracadabra", jotka vastaavat jälkiliitetaulukon 2. ja 3. elementtiä (8 ja 1). Tämä tarkoittaa, että haettu osamerkkijono "ab" esiintyy alkuperäisen sanan ensimmäisessä ja kahdeksannessa merkissä.

Rakennus

Suffiksitaulukko voidaan rakentaa suffiksipuun kanssa tai ilman sitä lisäämällä merkkijono kahden potenssin sykliseen pituuteen ja soveltamalla siihen tiettyä algoritmia.

Suffiksipuun kautta

Rakennamme päätepuun merkkijonolle T$. Missä T on tekstiä.
Tässä suffiksipuussa suoritamme syvyyshaun, jonka etusijalla on valita leksigrafisesti minimaaliset reunat.
Haun aikana katsomme, että $ (sentinel) on leksikografisesti pienin merkki.
Arkkiin saapuminen saavuttaa jonkin leksikografisesti pienimmän tällä hetkellä harkitsemattoman loppuliitteen, jonka arkin arvo, joka alkaa indeksi sisään, on kirjoitettava suffiksitaulukon nykyiseen soluun.
Tämä johtaa loppuliitteen matriisiin koko tekstille.

Rakenteen monimutkaisuus on , rivi sisältää suffiksipuun rakentamisen ja syvyyshaun. $O(|T|)$

Hae

Haku päätetaulukosta voidaan tehdä binäärihaulla. Hänen huonoin arvosanansa . Mutta voit nopeuttaa . $O(n\log {m})$ $O(n+\log _{2}{m})$

Naiivi binaarihaku

Haun ideana on, että jos kuvio esiintyy tekstissä, niin kaikki suffiksitaulukossa alkavat päätteet sijoittuvat vierekkäin. $P$ $Pos$
Suoritamme binäärihaun suffiksitaulukosta ja löydämme pienimmän indeksi : ei ala ja suurin indeksi : ei ala kummallakaan . $P$ $Pos$ $i$ $Pos(i-1)$ $P$ $minä'$ $Pos(i'+1)$ $P$
Sitten näyte tulee paikoissa aina . $Pos(i)$ $Pos(i')$
Jos kuvion etuliitteitä on useita, pistemäärä laskee arvoon . $O(n\log {m})$

Yksinkertainen kiihtyvyys

$L$ , — hakuvälin rajat. Alussa ,. _ $R$ $L=1$ $R=m$
Muistamme etuliitteiden pituuden , joka on sama kuin etuliite . $Pos(L)$ $Pos(R)$ $P:l,r$
$mlr=min(l,r)$ .
Seuraavassa sijaintivertailussa alamme käsitellä merkkejä ei ensimmäisestä paikasta, vaan alkaen . $M={\frac {L+R}{2))$ $mlr(l,r)+1$
Yleensä työaika , mutta pahin työaika on silti . $O(n+\log {m})$ $O(n\log {m})$

Kiihtyvyys LCP:n kautta

Suurin yhteinen etuliite ( eng. Largest Common Prefix ) - kahdelle merkkijonolle , - suurimman vastaavan etuliite pituus. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

Tässä algoritmissa oletetaan, että kahdelle loppuliitteelle lasketaan . Funktio lasketaan esikäsittelyvaiheessa puuta rakennettaessa. Myös seuraava väite pitää paikkansa : $LCP$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Tämän toiminnon ansiosta voit optimoida päätetaulukon binaarihaun.

Lemma : Jos päätteen ensimmäiset merkit ovat samat vasemmalla ja oikealla rajalla ( vastaavasti suffiksitaulukon indeksit) , niin sama määrä merkkejä vastaa kaikkia segmentin jälkiliitteitä . $L$ $R$ $k$ ${\näyttötyyli [L,R]}$

$L=1$ , , , . Seuraavat tapaukset ovat mahdollisia $R=|T|$ $l=LCP(P,L)$ $r=LCP(P,R)$
1. ${\näyttötyyli l=r}$ .
  1. Vertaa päätettä sisään kuvioon paikoillaan . $M={\frac {L+R}{2))$ $l+1$
  2. Suffiksi on leksikografisesti suurempi tai yhtä suuri ja loppuliitteen kohdassa tapahtui yhteensopimattomuus (jos on leksikografinen vastaavuus ja , niin katsomme sen yhtäläiseksi kuin ), muutamme hakurajoja: . $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M,R=R,l=i-1$
  3. Muutoin muuta reunuksia seuraavasti: . $L=L,R=M,r=i-1$
2. $l>r$ . Tarkistamme . $LCP(L,M),M={\frac {L+R}{2))$
  1. $LCP(L,M)>l$ . Tässä tapauksessa aseman päätteessä olevan sijainnin jälkeen seuraa useita samoja merkkejä kuin kohdassa , jotka eivät vastaa kuviota (jos olisivat, niitä olisi enemmän). Joten sinun on muutettava rajoja seuraavasti: . $l$ $M$ $L$ $l$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , tämä tarkoittaa, että päätteen paikan jälkeen paikkaa seuraa epäsuhta etuliitteen joidenkin merkkien kanssa , ja suurin osa kuvion vastaavuudesta sisältyy segmenttiin - se tarkoittaa , että ei varmasti esiinny segmentin kuvio. Sinun on muutettava reunuksia seuraavasti: . $LCP(L,M)$ $M$ $L$ $L$ ${\näyttötyyli [M,R]}$ $L=L,R=M,r=LCP(L,M)$
  3. $LCP(L,M)=l$ Tämä tarkoittaa, että segmentissä kaikkien päätteiden ensimmäiset merkit ovat samat , ja on mahdotonta sanoa heti, mihin alasegmenttiin mennä. Tämän ratkaisemiseksi on tarpeen verrata kuvioon merkkejä, jotka seuraavat jälkiliitteen sijaintia . Jos se on leksikografisesti pienempi tai yhtä suuri kuin ja siinä on epäsuhta :nnessa paikassa (jos on leksikografinen vastaavuus ja, niin katsotaan yhtäläiseksi ), muutamme rajoja seuraavasti:, ,; muuten ( leksikografisesti suurempi): , ,. ${\näyttötyyli [L,M]}$ $l$ $P$ $l$ $M$ $M$ $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M$ $R=R$ $l=i-1$ $M$ $R=M$ $L=L$ $r=i-1$
3. $l<r$ . Tarkistamme ja vertaamme kuten edellisessä vaiheessa, mutta vaihdamme arvoon ja . $LCP(R,M),M={\frac {L+R}{2))$ $r$ $L$ $R$ $l$ $r$
Algoritmi toimii, kunnes ja tulee yhtä suureksi . Tämä tarkoittaa, että on olemassa osa sattumaa. Jos invarianttia ei täyty , tekstissä ei ole kuviota osamerkkijonona. $l$ $r$ $|P|$ $L<P<R$

Tällainen superkiihtyvyys antaa aikaa , koska suoritetaan iteraatioita suffiksitaulukon yli. $O(|P|+\log _{2}{|T|})$ $\log _{2}{|T|}$

Aiheeseen liittyvät algoritmit

Kasain algoritmi suurimpien yhteisten etuliitteiden joukon muodostamiseksi.

Katso myös

suffiksi puu

Linkit

Kirjallisuus

Gasfield D. Merkkijonot, puut ja sekvenssit algoritmeissa: Informatiikka ja laskennallinen biologia / Per. englannista. I. V. Romanovski. - 2. painos - Pietari. : Nevskin murre, 2003. - 654 s.
Smith B. Methods and algoritms for computing on strings = Computing Patterns in Strings. - M .: Williams, 2006. - 496 s. - ISBN 5-8459-1081-1 , 0-201-39839-7.

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
Muut	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono