Palindromipuu

palindromipuu

Englanti puu

palindromi puu merkkijono eertree

Tyyppi

tietorakenne

Keksintövuosi

2015

Tekijä

Mihail Rubinchik [d]

Monimutkaisuus O - symboleissa

	Pahimmillaan
Rakennus	$O(n\log \sigma )$
Muistin kulutus	$Päällä)$

Mediatiedostot Wikimedia Commonsissa

Palindromipuu ( eng. palindromipuu , myös overtree [1] , eng. eertree ) on tietorakenne, joka on suunniteltu tallentamaan ja käsittelemään merkkijonon palindromisia osajonoja . Uralin liittovaltion yliopiston tutkijat Mikhail Rubinchik ja Arseny Shur ehdottivat sitä vuonna 2015. Edustaa kahta etuliitepuuta , jotka on koottu parillisen ja parittoman pituisten palindromisten osamerkkijonojen oikeasta "puolikkaasta". Rakenne vie muistia ja voidaan rakentaa ajassa , jossa on merkkijonon pituus ja siinä olevien eri merkkien lukumäärä. Palindromipuun avulla voidaan tehokkaasti ratkaista sellaisia ongelmia, kuten eri palindromisten osajonojen lukumäärän laskeminen, merkkijonon jaon löytäminen pienimmäksi palindromimääräksi, tarkistaminen, onko osamerkkijono palindromi ja muut. $Päällä)$ $O(n\log \sigma )$ $n$ $\sigma$

Merkintä

Olkoon jokin merkkijono ja käänteinen merkkijono . Kun kuvataan merkkijonon palindromipuuta , käytetään seuraavaa merkintää [2] : ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1))$ $S$ $S$

Merkkijonoa kutsutaan palindromiksi , jos se lukee saman vasemmalta oikealle ja oikealta vasemmalle, eli jos . $S$ ${\displaystyle S=S^{R))$

Osamerkkijono on merkkijonon jatkuva osajono , jota merkitään . $S$ ${\displaystyle S_{l,r}=s_{l}s_{l+1}\dots s_{r))$

Erityisesti sitä osamerkkijonoa, jolla on, kutsutaan merkkijonon etuliitteeksi ja sitä alimerkkijonoa, jolla on , kutsutaan merkkijonoliitteeksi . $l = 1$ $S$ $r=n$ $S$

Palindrominen osamerkkijono ( alipalindromi ) on osamerkkijono , joka on palindromi. Jos tämä osamerkkijono on myös merkkijonon etuliite tai pääte , sitä kutsutaan vastaavasti etuliite- tai suffiksipalindromiksi . $S$ $S$

Etuliitepuu on juurisuuntautunut puu , jonka kaaret on merkitty symboleilla siten, että vain yksi tietyllä symbolilla merkitty reuna tuleetämänpuun mistään kärjestä . $v$

Jokainen etuliitepuun kärki vastaa merkkijonoa, joka vastaa merkkien ketjutusta polulla puun juuresta tähän kärkeen.

Puurakenne

Yllä olevassa merkinnässä merkkijonon palindromipuu on suunnattu graafi , jonka kukin kärki vastaa jotakin merkkijonon ainutlaatuista alipalindromia ja tunnistetaan siihen. Jos merkkijonossa on osapalindromeja ja jossa on jokin aakkosmerkki , niin palindromipuussa on kaari , joka on merkitty symbolilla , pistettä vastaavasta kärjestä vastaavaan kärkeen . Tällaisessa graafissa missä tahansa kärjessä voi olla vain yksi sisääntuleva kaari. Mukavuuden vuoksi on myös otettu käyttöön kaksi apupistettä, jotka vastaavat pituuspalindromeja ( tyhjä merkkijono ) ja ("kuvitteellinen" merkkijono), vastaavasti. Kaaret tyhjästä merkkijonosta johtavat muodon palindromeja vastaaviin kärkipisteisiin ja "kuvitteellisesta merkkijonosta" muodon (eli yhdestä merkistä koostuvia) palindromeja vastaaviin pisteisiin. Huippua kutsutaan , vaikka sillä olisi parillinen palindromi, ja muuten pariton . Määritelmästä seuraa, että kaaret palindromipuussa kulkevat vain saman pariteetin kärkien välillä. Etuliitepuiden näkökulmasta tätä rakennetta voidaan kuvata seuraavasti [3] : $S$ $t$ $ctc$ $c$ $c$ $t$ $ctc$ $0$ $-yksi$ $cc$ $c$

Palindromipuun kärjet ja kaaret muodostavat kaksi etuliitepuuta, joiden juuret sijaitsevat pisteissä, jotka määrittävät tyhjät ja "imaginaariset" merkkijonot, vastaavasti. Tässä tapauksessa ensimmäinen etuliitepuu koostuu parillisen pituisten osapalindromien oikeasta puoliskosta ja toinen parittomista puoliskoista.

Palindromipuun kärkien lukumäärä ei ylitä , mikä on suora seuraus seuraavasta lemmasta [4] : $n+2$

Pituusmerkkijonossa voi olla korkeintaan erillisiä ei-tyhjiä palindromisia osamerkkijonoja . Lisäksi sen jälkeen, kun merkkijonon loppuun on määritetty tietty merkki , tämän merkkijonon eri alipalindromien määrä voi kasvaa enintään . $S$ $n$ $n$ $c$ $yksi$

Todiste

Tämä lausunto seuraa seuraavista tosiseikoista:

Jos palindromi on palindromin pääte , se on myös sen etuliite; $u$ $v$
Jos palindromit ja ovat merkkijonon jälkiliitteitä ja , niin se esiintyy vähintään kahdesti (etuliitteenä ja jälkiliitteenä ); $u$ $v$ $w$ $|u|<|v|$ $u$ $w$ $v$
Jokaisella merkkijonolla voi olla korkeintaan yksi ainutlaatuinen ( vain kerran) palindromi-liite. $w$ $w$

Viimeinen ominaisuus vastaa olennaisesti lemmaa, koska kaikki uudet osamerkkijonot, jotka ilmestyvät, kun merkkijonoon lisätään seuraava merkki, on oltava sen jälkiliitteitä [5] . ■

Tavallisten kaarien lisäksi, jotka toimivat etuliitepuun siirtymänä, kullekin palindromipuun kärjelle määritellään suffiksilinkki , joka johtaa kärjestä suurinta varsinaista (ei koko merkkijonoa vastaavaa ) kärkeen palindromi . Samanaikaisesti "imaginaarisesta" kärjestä tulevaa suffiksilinkkiä ei ole määritelty, vaan se johtaa määritelmän mukaan tyhjästä kärjestä "imaginaariseen". Suffiksilinkit muodostavat puun, jonka juuret ovat "kuvitteellisessa" kärjessä, ja niillä on tärkeä rooli palindromipuun rakentamisessa [3] . $v$ $u$ $v$ $v$

Rakentaminen

Kuten monet muutkin merkkijonorakenteet, palindromipuu rakennetaan iteratiivisesti . Aluksi se koostuu vain pisteistä, jotka vastaavat tyhjiä ja kuvitteellisia merkkijonoja. Rakennetta rakennetaan sitten vähitellen uudelleen, kun merkkijono kasvaa merkki kerrallaan. Koska merkkijonoon ilmestyy enintään yksi uusi palindromi, kun lisäät yhden merkin, puun uudelleenrakentaminen vaatii pahimmassa tapauksessa yhden uuden solmun ja liitelinkin lisäämisen siihen. Mahdollisen uuden solmun määrittämiseksi puun rakentamisen aikana ylläpidetään viimeistä osoitinta solmuun, joka vastaa suurinta nykyisistä palindromiliitteistä [3] .

Kaikki merkkijonon suffiksi-palindromit ovat saavutettavissa suffiksilinkeillä viimeisestä , joten uuden suffiksi-palindromin määrittämiseksi (se vastaa uutta kärkeä, jos sellainen on) on seurattava viimeisen suffiksilinkkejä, kunnes havaitaan, että nykyistä suffixi-palindromia edeltävä merkki vastaa merkkijonolle määritettyä merkkiä. Muodollisemmin anna olla merkkijonon suurin palindromiliite , sitten joko , tai , jossa on jokin palindromipääte . Siten iteroitaessa viimeisimmän suffiksilinkkejä , voidaan määrittää, voidaanko se laajentaa vertaamalla merkkejä ja . Kun vastaava palindromiliite on löydetty, kannattaa tarkistaa symbolilla [3] , sisältääkö palindromipuu siirtymän vastaavasta kärjestä . $P$ ${\displaystyle S_{1,k}=s_{1}s_{2}\dots s_{k))$ ${\displaystyle P=s_{k))$ $P=s_{k}Qs_{k}$ $K$ $S_{1,k-1}$ $K$ $P$ $s_{k-|Q|-1}$ ${\displaystyle s_{k))$ $K$ ${\displaystyle s_{k))$

Jos tällainen siirtymä on olemassa, se on jo tavattu rivillä aiemmin ja se vastaa kärkeä, johon tämä siirtymä johtaa. Muussa tapauksessa sinun on luotava sille uusi kärkipiste ja tehtävä siirtymä osoitteesta . Määritä seuraavaksi suffiksilinkki, joka vastaa toiseksi pisintä palindromipäätettä . Sen löytämiseksi tulee jatkaa viimeisten suffiksilinkkien ohittamista, kunnes löydetään toinen kärki , jolloin ; tämä kärki on suffiksilinkki . Jos merkitsemme siirtymistä ylhäältä symbolilla , koko prosessi voidaan kuvata seuraavalla pseudokoodilla [3] : $P$ ${\displaystyle s_{k))$ $K$ $P$ ${\displaystyle S_{1,k))$ $K$ ${\displaystyle s_{k-|Q|-1}=s_{k))$ $P$ $v$ $c$ $\delta(v,c)$

Find_link(v) -funktio: while s k -len(v)-1 ≠ s k : assign v = link(v) return v funktio add_letter(c): määritä k = k + 1 määrittele s k = c määrittele q = etsi_linkki(viimeinen) , jos δ(q, c) ei ole määritelty: define p = uusi_vertex() define len(p) = len(q) ) + 2 määrittele linkki(p) = δ(etsi_linkki(link(q)), c) määrittele δ(q, c) = p määritä viimeinen = δ(q, c)

Tässä oletetaan, että alun perin puuta kuvaa vain kaksi kärkeä pituuksilla ja vastaavasti suffiksilinkillä ensimmäisestä kärjestä toiseen. Muuttuja viimeiseksi tallentaa nykyisen rivin suurinta suffiksipalindromia vastaavan kärjen, aluksi se osoittaa nollaviivan kärkeen. Oletetaan myös, että alun perin se on yhtä suuri kuin ja siihen kirjoitetaan jokin palvelumerkki, jota ei esiinny merkkijonossa . $0$ $-yksi$ $k$ $0$ ${\displaystyle s_{0))$ ${\displaystyle s_{1}s_{2}\dots s_{k))$

Laskennallinen monimutkaisuus

Algoritmin monimutkaisuus voi vaihdella riippuen tietorakenteista, jotka tallentavat hyppytaulukon puuhun. Yleisessä tapauksessa assosiatiivista taulukkoa käytettäessä pääsyyn käytetty aika saavuttaa , missä on aakkosten koko, josta merkkijono on rakennettu. On syytä huomata, että jokainen iteraatio ensimmäisen kutsun find_link pituutta lyhentää lastin pituutta ja toisen pituutta link(last) , joka voi kasvaa vain yhdellä peräkkäisten add_letter -kutsujen välillä. Siten Find_linkin kokonaisaika ei ylitä , ja add_letter- kutsujen suorittamiseen tarvittava kokonaisaika voidaan arvioida [3] . Tämän rakenteen muistinkulutus on pahimmassa tapauksessa lineaarinen, mutta jos tarkastellaan rakenteen keskimääräistä kokoa kaikissa tietynpituisissa merkkijonoissa , keskimääräinen muistinkulutus on luokkaa [6] . ${\näyttötyyli \delta(q,c)}$ $O(\log \sigma )$ $\sigma$ $Päällä)$ $n$ $O(n\log \sigma )$ $n$ $O({\sqrt {n\sigma )))$

Muutokset

Samanaikaisesti tämän tietorakenteen käyttöönoton kanssa Rubinchik ja Shur ehdottivat myös useita muutoksia, jotka mahdollistavat palindromipuun ratkaisemien tehtävien laajentamisen. Erityisesti ehdotettiin menetelmää, jonka avulla voidaan rakentaa yleinen palindromipuu joukolle merkkijonoja, joilla on sama asymptotiikka . Tällaisen muunnelman avulla voimme ratkaista samat ongelmat, joita tarkastellaan merkkijonojoukon yhteydessä - esimerkiksi löytää kaikkien merkkijonojen suurin yhteinen alipalindromi tai kaikkien merkkijonojen eri alipalindromien lukumäärä aggregaatissa. Toinen ehdotettu muunnos oli puurakenteen muunnos, jossa yhden merkin lisääminen vie pahimmassa tapauksessa aikaa (eikä sitä poisteta , kuten tavallisessa rakenteessa tapahtuu) ja muistia. Tämä lähestymistapa mahdollistaa puun osittaisen pysyvyyden , jossa on mahdollista peruuttaa viimeisen merkin lisäys mielivaltaisina aikoina. Lisäksi puusta ehdotettiin täysin pysyvää versiota, jonka avulla voit käyttää ja liittää merkin mihin tahansa aiemmin tallennetuista versioista ajallisesti ja pahimmassa tapauksessa muistissa [7] . ${\displaystyle S_{1},S_{2},\dots ,S_{k))$ $O(\log n)$ $O(\log \sigma )$ $O(1)$ $O(\log n)$

Vuonna 2019 Watanabe ja kollegat kehittivät palindromipuuhun perustuvan tietorakenteen, nimeltään e 2 rtre 2 , työskennelläkseen run-length- koodauksen [4] antamien merkkijonojen alipalindromien kanssa , ja vuonna 2020 sama kirjoittajaryhmä yhdessä Mieno kehitti kaksi algoritmia , jotka mahdollistavat palindromipuun ylläpitämisen kooltaan liukuvalla ikkunalla . Ensimmäinen näistä algoritmeista vaatii aikaa ja muistia ja toinen aikaa ja muistia [8] . $d$ $O(n\log \sigma )$ $O(d)$ $O(n+d\sigma )$ $O(d\sigma )$

Sovellukset

Palindromipuu tarjoaa monia mahdollisia sovelluksia teoreettisesti nopeiden ja käytännössä helposti toteutettavien algoritmien saamiseksi useiden ohjelmoinnin ja matemaattisen kybernetiikan kombinatoristen ongelmien ratkaisemiseen [9] .

Yksi tehtävistä, jota varten tämä rakenne on kehitetty, on laskea eri alipalindromeja merkkijonoon verkossa . Se voidaan asettaa seuraavasti: yksi merkki kerrallaan määritetään yksi merkki kerrallaan alun perin tyhjään merkkijonoon. Jokaisessa vaiheessa sinun on tulostettava tietyn merkkijonon eri alipalindromien määrä. Palindromipuun näkökulmasta tämä vastaa rakenteen ei-triviaalisten kärkien lukumäärän tulostamista jokaisessa vaiheessa. Lineaarinen ratkaisu tämän ongelman offline-versioon esiteltiin vuonna 2010 [10] ja optimaalinen ratkaisu suoritusajalla online-versiolle löydettiin vuonna 2013 [11] . Esitetyssä ratkaisussa käytettiin kuitenkin kahta "raskasta" tietorakennetta - Manaker-algoritmin analogia sekä suffiksipuuta . Palindromipuulla on toisaalta sama asymptotiikka pahimmassa tapauksessa, ja toisaalta se on paljon kevyempi rakenne [3] . $O(n\log \sigma )$

Toinen tämän rakenteen mahdollinen sovellus on palindromirikkaiden binäärijonojen luettelointi [12] . Aikaisemmin on osoitettu, että pitkä sana voi sisältää vain erilaisia palindromeja; sanoja, joilla tämä arvio saavutetaan, kutsutaan palindromirikkaiksi. Amy Glen ja kollegat esittelivät palindromirikkaiden sanojen käsitteen vuonna 2008 [13] . Rubinchik ja Shur osoittivat, että käyttämällä palindromipuuta voidaan havaita kaikki palindromirikkaat sanat, joiden pituus ei ylitä , missä on tällaisten sanojen lukumäärä. Tämä tulos mahdollisti A216264- sekvenssin tunnettujen jäsenten määrän kasvattamisen OEIS :ssä 25:stä 60:een. Saadut tiedot osoittivat, että sekvenssi kasvaa paljon hitaammin kuin aiemmin on ajateltu, eli se on ylhäältä rajoittunut muodossa [14] . $n$ $n+1$ $n$ $O(R)$ $R$ $O(1,605^{n})$

Muistiinpanot

↑ Rubinchik, 2016 , s. 6-9
↑ Rubinchik, Shur, 2018 , s. 1-2
↑ 1 2 3 4 5 6 7 Rubinchik, Shur, 2018 , s. 2-6
↑ 1 2 Watanabe et al., 2019 , s. 432-434
↑ Droubay et ai., 2001 , s. 542-546
↑ Rubinchik, Shur, 2016 , s. yksi
↑ Rubinchik, Shur, 2018 , s. 6-11
↑ Mieso ym., 2020
↑ Rubinchik, 2016 , s. 75-76
↑ Groult, 2010
↑ Kosolobov ym., 2013
↑ OEIS - sekvenssi A216264 _
↑ Glen ym., 2009
↑ Rukavicka, 2017

Kirjallisuus

Rubinchik M. Joidenkin merkkijonojen käsittelytehtävien laskennallinen monimutkaisuus - Jekaterinburg : UrFU , 2016. - 83 s.
Droubay X., Justin J., Pirillo G. Episturmian sanoja ja joitakin de Lucan ja Rauzyn rakenteita (englanniksi) // Theoretical Computer Science - Elsevier BV , 2001. - Voi. 255, Iss. 1-2. - s. 539-553. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(99)00320-5
Groult R., Prieur É., Richomme G. Erillisten palindromien laskeminen sanassa lineaarisessa ajassa // Inform . prosessi. Lett. - Elsevier BV , 2010. - Voi. 110, Iss. 20. - P. 908-912. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/J.IPL.2010.07.018
Kosolobov D., Rubinchik M., Shur A. M. Erillisten subpalindromien löytäminen verkossa (englanniksi) // Prague Stringology Conference - Czech Technical University in Praha : 2013. - P. 63-69. -arXiv :1305.2540
Mieno T., Watanabe K., Nakashima Y., Inenaga S., Bannai H., Takeda M., Ginsparg P. Computing Palindromic Trees for a Sliding Window and Its Applications (englanniksi) // ArXiv.org - 2020. - 14 p.m. — ISSN 2331-8422 — arXiv:2006.02134
Rubinchik M., Shur A. M. Erillisten subpalindromien määrä satunnaisissa sanoissa (englanniksi) // Rahasto. ilmoittaa. - IOS Press , 2016. - Vol. 145, Iss. 3. - s. 371-384. — ISSN 0169-2968 ; 1875-8681 - doi:10.3233/FI-2016-1366 - arXiv:1505.08043
Rubinchik M., Shur A. M. Eertree (englanti) : Tehokas tietorakenne palindromien käsittelyyn merkkijonoissa // European Journal of Combinatorics / P. O. Mendez , P. Rosentiehl , É. C. Verdière , A. Björner , F. Brenti , A. Brouwer , P. Cameron , R. Cordovil , D. Foata , P. Frankl et ai. — Elsevier BV , 2018. — Voi. 68. - s. 249-265. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2017.07.021 - arXiv:1506.04862
Watanabe K., Nakashima Y., Inenaga S., Bannai H., Takeda M. Lyhyimmät ainutlaatuiset palindromiset alijonokyselyt run-Length Encoded Strings -kielillä // Lect . Huomautus Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer , 2019. - S. 430-441. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/ 978-3-030-25005-8_35 - arXiv:1903.06290
Glen A., Justin J., Widmer S., Zamboni L. Q. Palindromic richness (englanti) // European Journal of Combinatorics / P. O. Mendez , P. Rosentiehl , É. C. Verdière , A. Björner , F. Brenti , A. Brouwer , P. Cameron , R. Cordovil , D. Foata , P. Frankl et ai. — Elsevier BV , 2009. — Voi. 30, Iss. 2. - P. 510-531. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2008.04.006 - arXiv:0801.1656
Rukavicka J. Rikkaiden sanojen määrästä (englanniksi) // Luento. Huomautus Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer , 2017. - S. 345-352. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-62809-7_26 - arXiv:1701.07778

Linkit

Palindromipuu . ITMO Wiki Abstracts . (määrätön)

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