Arbore palindrom

arbore palindrom

Engleză copac

arbore palindrom pentru string eertree

Tip de

structură de date

Anul inventiei

2015

Autor

Mihail Rubinchik [d]

Complexitatea în simbolurile O

	În cel mai rău caz
Clădire	$O(n\log \sigma )$
Consumul de memorie	$Pe)$

Fișiere media la Wikimedia Commons

Un arbore palindromic ( eng. palindromic tree , de asemenea overtree [1] , eng. eertree ) este o structură de date concepută pentru a stoca și procesa subșiruri palindromice ale unui șir . A fost propus de oamenii de știință de la Universitatea Federală Ural Mikhail Rubinchik și Arseny Shur în 2015. Reprezintă doi arbori de prefix , asamblați din „jumătățile” din dreapta ale subșirurilor palindromice de lungime pară și, respectiv, impară. Structura ocupă memorie și poate fi construită în timp , unde este lungimea șirului și este numărul de caractere diferite din acesta. Cu ajutorul unui arbore palindrom, se pot rezolva în mod eficient probleme precum numărarea numărului de subșiruri palindromice diferite, găsirea împărțirii unui șir în cel mai mic număr de palindrom, verificarea dacă un subșir este un palindrom și altele. $Pe)$ $O(n\log \sigma )$ $n$ $\sigma$

Notație

Să fie un șir și să fie șirul inversat . Când descriem arborele palindrom al unui șir , se utilizează următoarea notație [2] : $S=s_{1}s_{2}\dots s_{n)$ $S^{R}=s_{n}s_{n-1}\dots s_{1)$ $S$ $S$

Un șir se numește palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga, adică dacă . $S$ $S=S^{R)$

Un subșir este o subsecvență continuă a unui șir și notat cu . $S$ $S_{l,r}=s_{l}s_{l+1}\dots s_{r)$

În special, subșirul care are se numește prefix șir , iar subșirul care are se numește sufixul șir . $l=1$ $S$ $r=n$ $S$

Un subșir palindromic ( subpalindrom ) este un subșir care este un palindrom. Dacă acest subșir este, de asemenea, un prefix sau sufix al șirului , atunci se numește prefix- sau , respectiv, sufix-palindrom . $S$ $S$

Un arbore de prefix este un arbore orientat spre rădăcină, ale cărui arcuri sunt etichetate cu simboluri astfel încât nu mai mult de o margine etichetată cu un simbol dat provine de la orice vârf alacestui arbore . $v$

Fiecare vârf al arborelui de prefix îi corespunde unui șir egal cu concatenarea caracterelor pe calea de la rădăcina arborelui la acest vârf.

Structura arborelui

În notația de mai sus, arborele palindrom al unui șir este un grafic direcționat , fiecare vârf al căruia îi corespunde și este identificat cu un subpalindrom unic al șirului. Dacă șirul are subpalindromuri și , unde este vreun caracter alfabetic , atunci arborele palindrom are un arc marcat cu simbolul , de la vârful corespunzător lui , până la vârful corespunzător lui . Într-un astfel de grafic, orice vârf poate avea doar un arc de intrare. Pentru comoditate, sunt introduse și două vârfuri auxiliare, care corespund palindromurilor de lungime ( șir goală ) și respectiv șir („imaginar”). Arcurile din șirul gol conduc la vârfuri corespunzătoare palindromurilor de forma , iar din „șirul imaginar” la vârfuri corespunzătoare palindromurilor formei (adică formate dintr-un singur caracter). Un vârf este numit chiar dacă are un palindrom de lungime pară, iar în caz contrar impar . Din definiție rezultă că arcurile dintr-un arbore palindrom trec numai între vârfuri cu aceeași paritate. Din punctul de vedere al arborilor de prefix, această structură poate fi descrisă după cum urmează [3] : $S$ $t$ $ctc$ $c$ $c$ $t$ $ctc$ $0$ $-unu$ $cc$ $c$

Vârfurile și arcurile arborelui palindrom formează doi arbori de prefix ale căror rădăcini sunt situate la vârfurile care definesc șirurile goale, respectiv „imaginare”. În acest caz, primul arbore de prefix este compus din jumătățile drepte ale subpalindromurilor de lungime pară, iar al doilea din cele impare.

Numărul de vârfuri din arborele palindrom nu depășește , ceea ce este o consecință directă a următoarei leme [4] : $n+2$

Un șir de lungime poate avea cel mult subșiruri palindromice nevide distincte. Mai mult, după atribuirea unui anumit caracter la sfârșitul unui șir, numărul de subpalindromuri diferite ale acestui șir poate crește cu cel mult . $S$ $n$ $n$ $c$ $unu$

Dovada

Această afirmație rezultă din următoarele fapte:

Dacă un palindrom este un sufix al unui palindrom , atunci este și prefixul acestuia; $u$ $v$
Dacă palindromurile și sunt sufixe ale șirului și , atunci apare de cel puțin două ori (ca prefix și ca sufix ); $u$ $v$ $w$ $|u|<|v|$ $u$ $w$ $v$
Orice șir poate avea cel mult un sufix palindrom unic (care apare o singură dată). $w$ $w$

Ultima proprietate este în esență echivalentă cu lema, deoarece toate subșirurile noi care apar la adăugarea următorului caracter la șir trebuie să fie sufixele acestuia [5] . ■

Pe lângă arcurile obișnuite care servesc drept tranziții pentru arborele de prefix, pentru fiecare vârf al arborelui palindrom este definită o legătură sufixă care duce de la vârf la vârful corespunzător celui mai mare sufix propriu (nu este egal cu întregul șir). palindrom . În același timp, legătura sufixului de la vârful „imaginar” nu este definită, dar prin definiție duce de la un vârf gol la cel „imaginar”. Legăturile sufixelor formează un arbore înrădăcinat la un vârf „imaginar” și joacă un rol important în construcția unui arbore palindrom [3] . $v$ $u$ $v$ $v$

Clădire

La fel ca multe alte structuri de șir, un arbore palindrom este construit iterativ . Inițial, este format doar din vârfuri corespunzătoare șirurilor goale și imaginare. Structura este apoi reconstruită treptat pe măsură ce șirul crește câte un caracter. Deoarece cel mult un nou palindrom apare într-un șir la adăugarea unui caracter, reconstruirea arborelui în cel mai rău caz va necesita adăugarea unui nou nod și a unei legături de sufix la acesta. Pentru a determina un posibil nou nod în timpul construcției arborelui, se menține un ultim indicator către nodul corespunzător celui mai mare dintre sufixele palindromului actual [3] .

Toate sufixele-palindromele șirului sunt accesibile prin legături sufixe de la last , așa că pentru a determina un nou sufix-palindrom (va corespunde noului vârf, dacă există) este necesar să urmați legăturile sufixe ale ultimului până se constată că caracterul care precede sufixul-palindrom curent se potrivește cu caracterul care a fost atribuit șirului. Mai formal, fie sufixul maxim palindrom al șirului , apoi fie , fie , unde este un sufix palindrom . Astfel, iterând printre legăturile sufixe ale lui last , se poate determina dacă acesta poate fi extins prin compararea caracterelor și . Când a fost găsit sufixul palindrom corespunzător , ar trebui să verificați dacă arborele palindrom conține o tranziție de la vârful corespunzător prin simbolul [3] . $P$ $S_{1,k}=s_{1}s_{2}\dots s_{k)$ $P=s_{k)$ $P=s_{k}Qs_{k}$ $Q$ $S_{1,k-1}$ $Q$ $P$ $s_{k-|Q|-1}$ $s_{k)$ $Q$ $s_{k)$

Dacă există o astfel de tranziție, atunci aceasta a fost deja întâlnită în linie mai devreme și corespunde vârfului la care duce această tranziție. În caz contrar, trebuie să creați un nou vârf pentru acesta și să faceți o tranziție de la . Apoi, definiți o legătură de sufix pentru care se potrivește cu al doilea cel mai lung sufix palindrom . Pentru a-l găsi, ar trebui să continuați să ocoliți ultimele legături sufixe până când este întâlnit al doilea vârf , astfel încât ; acest vârf va fi legătura sufixului . Dacă notăm tranziția de la vârf prin simbol ca , întregul proces poate fi descris prin următorul pseudocod [3] : $P$ $s_{k)$ $Q$ $P$ $S_{1,k)$ $Q$ $s_{k-|Q|-1}=s_{k)$ $P$ $v$ $c$ $\delta(v,c)$

Funcția find_link(v): în timp ce s k -len(v)-1 ≠ s k : atribuiți v = link(v) return v funcția add_letter(c): atribuiți k = k + 1 define s k = c define q = find_link(last) dacă δ(q, c) nu este definit: define p = new_vertex() define len(p) = len(q ) + 2 definesc link(p) = δ(find_link(link(q)), c) defines δ(q, c) = p atribui ultimul = δ(q, c)

Se presupune aici că inițial arborele este descris doar de două vârfuri cu lungimi și, în consecință, cu o legătură sufixă de la primul vârf la al doilea. Ultima variabilă stochează vârful corespunzător celui mai mare sufix palindrom al liniei curente, inițial indică vârful liniei zero. De asemenea, se presupune că inițial este egal cu și în care este scris un caracter de serviciu, care nu apare în șirul . $0$ $-unu$ $k$ $0$ $s_{0)$ $s_{1}s_{2}\dots s_{k)$

Complexitate computațională

Complexitatea algoritmului poate varia în funcție de structurile de date care stochează tabelul de salt în arbore. În cazul general, când se folosește o matrice asociativă , timpul petrecut pentru accesare ajunge la , unde este dimensiunea alfabetului din care este construit șirul. Este de remarcat faptul că fiecare iterație a primului apel la find_link reduce lungimea last , iar a celui de-al doilea, lungimea link(last) , care poate crește doar cu unul între apelurile succesive la add_letter . Astfel, timpul total al find_link nu depășește , iar timpul total necesar pentru a executa apelurile add_letter poate fi estimat ca [3] . Consumul de memorie al acestei structuri este liniar în cel mai rău caz, totuși, dacă luăm în considerare dimensiunea medie a structurii pe toate șirurile de o lungime dată , consumul mediu de memorie va fi de ordinul [6] . $\delta(q,c)$ $O(\log \sigma )$ $\sigma$ $Pe)$ $n$ $O(n\log \sigma )$ $n$ $O({\sqrt {n\sigma )))$

Modificări

Concomitent cu introducerea acestei structuri de date, Rubinchik și Shur au propus și o serie de modificări care permit extinderea domeniului de aplicare a sarcinilor rezolvate de un arbore palindrom. În special, a fost propusă o metodă care permite construirea unui arbore palindrom general pentru un set de șiruri cu aceleași asimptotice . O astfel de modificare ne permite să rezolvăm aceleași probleme considerate în contextul unui set de șiruri - de exemplu, să găsim cel mai mare subpalindrom comun dintre toate șirurile sau numărul de subpalindromuri diferite ale tuturor șirurilor în agregat. O altă modificare propusă a fost o variantă de construcție a arborelui, în care adăugarea unui caracter necesită timp în cel mai rău caz (și nu amortizată , așa cum se întâmplă în construcția standard) și memorie. Această abordare face posibilă asigurarea persistenței parțiale a arborelui, în care este posibil să se anuleze adăugarea ultimului caracter în momente arbitrare. În plus, a fost propusă o versiune complet persistentă a arborelui, care vă permite să accesați și să adăugați un caracter la oricare dintre versiunile salvate anterior în timp și memorie în cel mai rău caz [7] . $S_{1},S_{2},\dots,S_{k)$ $O(\log n)$ $O(\log \sigma )$ $O(1)$ $O(\log n)$

În 2019, Watanabe și colegii au dezvoltat o structură de date bazată pe un arbore palindrom, numit e 2 rtre 2 , pentru a lucra cu subpalindromuri de șiruri date prin codificare run-length [4] , iar în 2020, aceeași echipă de autori, împreună cu Mieno, a dezvoltat doi algoritmi, care să permită menținerea unui arbore palindrom pe o fereastră glisantă de dimensiune . Primul dintre acești algoritmi necesită timp și memorie, iar al doilea necesită timp și memorie [8] . $d$ $O(n\log \sigma )$ $O(d)$ $O(n+d\sigma)$ $O(d\sigma )$

Aplicații

Arborele palindrom oferă numeroase aplicații posibile pentru obținerea de algoritmi teoretic rapid și practic ușor de implementat pentru rezolvarea unui număr de probleme combinatorii în programare și cibernetică matematică [9] .

Una dintre sarcinile pentru care a fost dezvoltată această structură este de a număra diferite subpalindromuri într-un șir online . Poate fi setat după cum urmează: câte un caracter i se atribuie câte un caracter șirului inițial gol. La fiecare pas, trebuie să imprimați numărul de subpalindromuri diferite din șirul dat. Din punctul de vedere al arborelui palindrom, aceasta este echivalentă cu tipărirea numărului de vârfuri non-triviale din structură la fiecare pas. O soluție liniară pentru versiunea offline a acestei probleme a fost prezentată în 2010 [10] , iar soluția optimă cu timp de execuție pentru versiunea online a fost găsită în 2013 [11] . Cu toate acestea, soluția indicată a folosit două structuri de date „greu” - un analog al algoritmului Manaker , precum și un arbore de sufixe . Arborele palindrom, pe de o parte, are aceleași asimptotice în cel mai rău caz, iar pe de altă parte, este o structură mult mai ușoară [3] . $O(n\log \sigma )$

O altă posibilă aplicație a acestei structuri este enumerarea șirurilor binare bogate în palindrom [12] . Mai devreme s-a arătat că un cuvânt de lungime nu poate conține mai mult decât palindromuri diferite; cuvintele pe care se realizează această estimare sunt numite bogate în palindrom. Conceptul de cuvinte bogate în palindromic a fost introdus de Amy Glen și colegii săi în 2008 [13] . Rubinchik și Shur au arătat că folosind un arbore palindrom, se pot detecta toate cuvintele bogate în palindromic a căror lungime nu depășește , unde este numărul acestor cuvinte. Acest rezultat a făcut posibilă creșterea numărului de membri cunoscuți ai secvenței A216264 în OEIS de la 25 la 60. Datele obținute au arătat că secvența crește mult mai lent decât se credea anterior, și anume, este mărginită de sus ca [14] . $n$ $n+1$ $n$ $O(R)$ $R$ $O(1.605^{n})$

Note

↑ Rubinchik, 2016 , p. 6-9
↑ Rubinchik, Shur, 2018 , pp. 1-2
↑ 1 2 3 4 5 6 7 Rubinchik, Shur, 2018 , pp. 2-6
↑ 1 2 Watanabe et al., 2019 , pp. 432-434
↑ Droubay și colab., 2001 , pp. 542-546
↑ Rubinchik, Shur, 2016 , p. unu
↑ Rubinchik, Shur, 2018 , p. 6-11
↑ Mieno și colab., 2020
↑ Rubinchik, 2016 , p. 75-76
↑ Groult, 2010
↑ Kosolobov et al., 2013
↑ Secvența OEIS A216264 _
↑ Glen și colab., 2009
↑ Rukavicka, 2017

Literatură

Rubinchik M. Complexitatea computațională a unor sarcini de procesare a șirurilor - Ekaterinburg : UrFU , 2016. - 83 p.
Droubay X., Justin J., Pirillo G. Cuvinte episturmiane și unele construcții ale lui de Luca și Rauzy (engleză) // Teoretică Informatică - Elsevier BV , 2001. - Vol. 255, Iss. 1-2. - P. 539-553. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(99)00320-5
Groult R., Prieur É., Richomme G. Numărarea palindromurilor distincte într-un cuvânt în timp liniar // Informa . proces. Lett. - Elsevier BV , 2010. - Vol. 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. Finding distinct subpalindromes online (engleză) // Prague Stringology Conference - Czech Technical University din Praga : 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 (engleză) // ArXiv.org - 2020. - 14 p.m. — ISSN 2331-8422 — arXiv:2006.02134
Rubinchik M., Shur A. M. The Number of Distinct Subpalindromes in Random Words (engleză) // Fund. informa. - IOS Press , 2016. - Vol. 145, Iss. 3. - P. 371-384. — ISSN 0169-2968 ; 1875-8681 - doi:10.3233/FI-2016-1366 - arXiv:1505.08043
Rubinchik M., Shur A. M. Eertree (engleză) : O structură de date eficientă pentru procesarea palindromilor în șiruri // 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 al. — Elsevier BV , 2018. — Vol. 68. - P. 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. Cele mai scurte interogări unice de subșiruri palindromice pe șiruri codificate cu lungimea de rulare // Lect . Notă Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer , 2019. - P. 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 (engleză) // 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 al. — Elsevier BV , 2009. — Vol. 30, Iss. 2. - P. 510-531. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2008.04.006 - arXiv:0801.1656
Rukavicka J. Despre numărul de cuvinte bogate (engleză) // Lect. Notă Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer , 2017. - P. 345-352. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-62809-7_26 - arXiv:1701.07778

Link -uri

Arborele palindrom . Rezumate Wiki ITMO . (nedefinit)

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănarea Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun