Palindromfa

palindromfa

angol fa

palindrom fa húr eertree számára

Típusú

adatszerkezet

Feltalálás éve

2015

Szerző

Mihail Rubincsik [d]

Bonyolultság az O-szimbólumokban

	Legrosszabb esetben
Épület	$O(n\log \sigma )$
Memória fogyasztás	$Tovább)$

Médiafájlok a Wikimedia Commons oldalon

A palindrom fa ( eng. palindrom fa , szintén overtree [1] , eng. eertree ) egy olyan adatstruktúra , amely egy karakterlánc palindrom részstringjeinek tárolására és feldolgozására szolgál . Az Uráli Szövetségi Egyetem tudósai, Mikhail Rubinchik és Arseny Shur javasolták 2015-ben. Két előtagfát jelöl, amelyek páros, illetve páratlan hosszúságú palindrom részstringek jobb "feleiből" vannak összeállítva. A struktúra memóriát foglal és időben felépíthető , ahol a karakterlánc hossza és a benne lévő különböző karakterek száma. A palindromfa segítségével hatékonyan megoldható olyan problémák, mint a különböző palindrom részkarakterláncok számának megszámlálása, egy karakterlánc felosztásának megtalálása a legkisebb számú palindromra, annak ellenőrzése, hogy egy részkarakterlánc palindrom-e, stb. $Tovább)$ $O(n\log \sigma )$ $n$ $\sigma$

Jelölés

Legyen valamilyen karakterlánc és legyen a fordított karakterlánc . Egy karakterlánc palindróma fájának leírásakor a következő jelölést használjuk [2] : ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1))$ $S$ $S$

Egy karakterláncot palindromnak nevezünk , ha balról jobbra és jobbról balra ugyanazt olvassa, vagyis ha . $S$ ${\displaystyle S=S^{R))$

A részkarakterlánc egy karakterlánc folyamatos részsorozata , amelyet jelöl . $S$ ${\displaystyle S_{l,r}=s_{l}s_{l+1}\dots s_{r))$

Konkrétan azt a részkarakterláncot, amelyiknek van , karakterlánc előtagnak , a rendelkező részstringet pedig string utótagnak nevezzük . $l=1$ $S$ $r=n$ $S$

A palindrom részkarakterlánc ( subpalindrome ) egy olyan részkarakterlánc , amely palindrom. Ha ez a részkarakterlánc a karakterlánc előtagja vagy utótagja is , akkor előtag- vagy utótag-palindromnak nevezzük . $S$ $S$

Az előtagfa egy gyökérorientált fa , amelynek ívei szimbólumokkal vannak megjelölve úgy, hogy a fa bármely csúcsából legfeljebbegy adott szimbólummal jelölt él származzon . $v$

Az előtagfa minden csúcsa egy karakterláncnak felel meg, amely megegyezik a fa gyökerétől ehhez a csúcshoz vezető útvonalon lévő karakterek összefűzésével.

Fa szerkezete

A fenti jelölésben egy karakterlánc palindromfája egy irányított gráf , amelynek minden csúcsa megfelel a karakterlánc valamilyen egyedi alpalindromjának, és azzal azonosítható. Ha a karakterlánc alpalindromokat tartalmaz , és ahol valamilyen alfabetikus karakter van , akkor a palindromfának van egy szimbólummal jelölt íve a -nak megfelelő csúcstól a -nek megfelelő csúcsig . Egy ilyen gráfban bármely csúcsnak csak egy bejövő íve lehet. A kényelem kedvéért két segédcsúcsot is bevezetünk, amelyek megfelelnek a hosszúságú palindromoknak ( üres karakterlánc ), illetve ("képzetes" string). Az üres karakterláncból az ívek a forma palindromjainak megfelelő csúcsokhoz vezetnek, a „képzetes karakterlánctól” pedig a forma palindromjainak megfelelő (vagyis egyetlen karakterből álló) csúcsokhoz. A csúcsot akkor is nevezzük , ha páros hosszúságú palindromja van, egyébként pedig páratlan . A definícióból következik, hogy a palindromfában az ívek csak azonos paritású csúcsok között haladnak át. Az előtagfák szempontjából ez a struktúra a következőképpen írható le [3] : $S$ $t$ $ctc$ $c$ $c$ $t$ $ctc$ $0$ $-egy$ $cc$ $c$

A palindromfa csúcsai és ívei két előtagfát alkotnak, amelyek gyökerei az üres, illetve a "képzetes" karakterláncokat meghatározó csúcsokban helyezkednek el. Ebben az esetben az első előtag fa a páros hosszúságú alpalindromok jobb feléből, a második pedig a páratlanokból áll.

A palindromfában a csúcsok száma nem haladja meg a -t, ami a következő lemma [4] egyenes következménye : $n+2$

Egy hosszúságú karakterláncnak legfeljebb különálló, nem üres palindrom részkarakterláncai lehetnek. Ezenkívül, miután egy karaktert egy karakterlánc végéhez rendelünk, a karakterlánc különböző alpalindromjainak száma legfeljebb . $S$ $n$ $n$ $c$ $egy$

Bizonyíték

Ez az állítás a következő tényekből következik:

Ha a palindrom egy palindrom utótagja , akkor az előtagja is; $u$ $v$
Ha a palindromok és az és a karakterlánc utótagjai , akkor legalább kétszer fordul elő (előtagként és utótagként ); $u$ $v$ $w$ $|u|<|v|$ $u$ $w$ $v$
Bármely karakterláncnak legfeljebb egy egyedi ( csak egyszer előforduló) palindrom utótagja lehet. $w$ $w$

Az utolsó tulajdonság lényegében ekvivalens a lemmával, mivel minden új részstringnek, amely a következő karakter hozzáadásakor jelenik meg, a karakterlánc utótagjának kell lennie [5] . ■

A szokásos íveken kívül, amelyek az előtagfa átmeneteiként szolgálnak, a palindromfa minden csúcsához egy utótag hivatkozás van definiálva, amely a csúcstól a legnagyobb (nem egyenlő a teljes karakterlánccal ) utótagnak megfelelő csúcshoz vezet. palindrom . Ugyanakkor az utótag hivatkozás a „képzeletbeli” csúcsból nincs definiálva, hanem definíció szerint egy üres csúcsból a „képzetes” csúcsba vezet. Az utótag hivatkozások egy "képzetes" csúcsban gyökerező fát alkotnak, és fontos szerepet játszanak a palindromfa felépítésében [3] . $v$ $u$ $v$ $v$

Épület

Sok más húrszerkezethez hasonlóan a palindromfa is iteratív módon épül fel . Kezdetben csak az üres és képzeletbeli karakterláncoknak megfelelő csúcsokból áll. A struktúra ezután fokozatosan újjáépül, ahogy a karakterlánc egyenként növekszik. Mivel egy karakter hozzáadásakor legfeljebb egy új palindrom jelenik meg egy karakterláncban, a fa újraépítéséhez a legrosszabb esetben egy új csomópont és egy utótag hivatkozás hozzáadása szükséges. Egy lehetséges új csomópont meghatározásához a fa építése során egy utolsó mutató a jelenlegi palindrom utótagok közül a legnagyobbnak megfelelő csomópontra [3] megmarad .

A karakterlánc összes utótag-palindromja elérhető a last utótag hivatkozásaival , ezért egy új utótag-palindrom meghatározásához (az új csúcsnak felel meg, ha van ilyen) addig kell követni az utolsó utótag hivatkozásait, amíg meg nem találjuk, hogy az aktuális utótag-palindrom előtti karakter megegyezik a karakterlánchoz rendelt karakterrel. Formálisabban legyen a karakterlánc maximális palindrom utótagja , majd vagy , vagy , ahol valamilyen palindrom utótag . Így a last utótag hivatkozásai között iterálva megállapítható, hogy a karakterek és a karakterek összehasonlításával kibővíthető-e . Ha megtalálta a megfelelő palindrom utótagot , ellenőrizze, hogy a palindromfa tartalmaz-e átmenetet a megfelelő csúcstól a [3] szimbólummal . $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))$

Ha van ilyen átmenet, akkor már korábban találkoztunk a sorban, és megfelel annak a csúcsnak, ahová ez az átmenet vezet. Ellenkező esetben létre kell hoznia egy új csúcsot, és át kell lépnie a -ból . Ezután adjon meg egy utótag hivatkozást, amely megfelel a második leghosszabb palindrom utótagnak . Annak érdekében, hogy megtaláljuk, folytatni kell az utolsó utótag hivatkozások megkerülését, amíg a második csúcsot meg nem találjuk , így ; ez a csúcs lesz az utótag hivatkozás . Ha a felülről való átmenetet szimbólummal jelöljük , akkor az egész folyamat a következő pszeudokóddal leírható [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)$

link(v) függvény: while s k -len(v)-1 ≠ s k : v hozzárendelés = link(v) return v függvény add_betű(c): hozzárendel k = k + 1 define s k = c define q = find_link(last) if δ(q, c) nincs definiálva: define p = new_vertex() define len(p) = len(q ) + 2 link (p) = δ(link(q) keresése), c) δ(q, c) = p hozzárendelés utolsó = δ(q, c) meghatározása

Itt feltételezzük, hogy a fát kezdetben csak két csúcs írja le hosszúsággal , és ennek megfelelően egy utótag hivatkozással az első csúcsból a másodikba. Az utolsó változó az aktuális egyenes legnagyobb utótag palindromának megfelelő csúcsot tárolja, kezdetben a nulladik egyenes csúcsára mutat. Azt is feltételezzük, hogy kezdetben egyenlő és valamilyen szolgáltatás karaktert írunk be, ami nem fordul elő a karakterláncban . $0$ $-egy$ $k$ $0$ $s_{0}$ ${\displaystyle s_{1}s_{2}\dots s_{k))$

Számítási összetettség

Az algoritmus összetettsége az ugrótáblát a fában tároló adatstruktúráktól függően változhat. Általános esetben asszociatív tömb használatakor a hozzáférésre fordított idő eléri a -t , ahol az ábécé mérete, amelyből a karakterlánc épül. Érdemes megjegyezni, hogy az első find_link hívás minden iterációja csökkenti a last hosszát , a másodiké pedig a link(last) hosszát, amely csak eggyel nőhet az add_letter egymást követő hívásai között . Így a find_link teljes ideje nem haladja meg a -t , és az add_letter hívások végrehajtásához szükséges teljes idő [3] -ra becsülhető . Ennek a struktúrának a memóriafogyasztása a legrosszabb esetben lineáris, azonban ha figyelembe vesszük a struktúra átlagos méretét egy adott hosszúságú összes sztringen , akkor az átlagos memóriafogyasztás [6] nagyságrendű lesz . $\delta(q,c)$ $O(\log \sigma )$ $\sigma$ $Tovább)$ $n$ $O(n\log \sigma )$ $n$ $O({\sqrt {n\sigma )))$

Módosítások

Az adatstruktúra bevezetésével egyidejűleg Rubinchik és Shur számos olyan módosítást is javasolt, amelyek lehetővé teszik a palindromfa által megoldott feladatok körének bővítését. Konkrétan egy olyan módszert javasoltak, amely lehetővé teszi egy általános palindróma fa létrehozását azonos aszimptotikus karakterláncok halmazához . Egy ilyen módosítás lehetővé teszi, hogy ugyanazokat a problémákat oldjuk meg, amelyeket egy karakterlánchalmaz kontextusában vizsgálunk – például, hogy megtaláljuk az összes karakterlánc legnagyobb közös alpalindromát vagy az összes karakterlánc különböző alpalindromjainak számát az aggregátumban. Egy másik javasolt módosítás a faszerkezet egy változata volt, amelyben egy karakter hozzáadása a legrosszabb esetben időt vesz igénybe (és nem amortizálódik , mint a szabványos konstrukcióban) és memóriát vesz igénybe. Ez a megközelítés lehetővé teszi a fa részleges perzisztenciájának biztosítását, amelyben lehetséges az utolsó karakter hozzáadását tetszőleges időpontokban visszagörgetni. Ezenkívül javasolták a fa egy teljesen perzisztens verzióját, amely lehetővé teszi, hogy a legrosszabb esetben időben és memóriában bármelyik korábban elmentett verzióhoz hozzáférjen és karaktert fűzjön hozzá [7] . ${\displaystyle S_{1},S_{2},\dots ,S_{k))$ $O(\log n)$ $O(\log \sigma )$ $O(1)$ $O(\log n)$

2019-ben Watanabe és munkatársai kifejlesztettek egy e 2 rtre 2 nevű palindrómfán alapuló adatstruktúrát , amely a futáshosszúságú kódolás által adott karakterláncok alpalindromjaival dolgozott [4] , 2020-ban pedig ugyanez a szerzőcsoport, valamint A Mieno két algoritmust fejlesztett ki, amelyek lehetővé teszik egy palindromfa fenntartását egy méretű tolóablakon . Ezen algoritmusok közül az első idő és memória, a második pedig időt és memóriát igényel [8] . $d$ $O(n\log \sigma )$ $O(d)$ $O(n+d\sigma )$ $O(d\sigma )$

Alkalmazások

A palindromfa számos alkalmazási lehetőséget kínál elméletileg gyors és gyakorlatilag könnyen megvalósítható algoritmusok előállítására számos kombinatorikus probléma megoldására a programozásban és a matematikai kibernetikában [9] .

Az egyik feladat, amelyre ezt a struktúrát kifejlesztették, hogy megszámolja a különböző alpalindromokat egy karakterláncban online . A következőképpen állítható be: a kezdetben üres karakterlánchoz egyszerre egy-egy karakter hozzárendelődik. Minden lépésnél ki kell nyomtatni az adott karakterláncban lévő különböző alpalindromok számát. A palindromfa szempontjából ez egyenértékű azzal, hogy minden lépésben kinyomtatjuk a szerkezet nem triviális csúcsainak számát. A probléma offline verziójára 2010-ben egy lineáris megoldást mutattak be [10] , az online verzióhoz pedig 2013-ban találták meg az optimális megoldást a végrehajtási idővel [11] . A jelzett megoldás azonban két "nehézsúlyú" adatstruktúrát használt - a Manaker algoritmus analógját , valamint egy utótagfát . A palindromfa egyrészt a legrosszabb esetben is ugyanolyan aszimptotikával rendelkezik, másrészt sokkal könnyebb szerkezet [3] . $O(n\log \sigma )$

Ennek a szerkezetnek egy másik lehetséges alkalmazása a palindromban gazdag bináris karakterláncok felsorolása [12] . Korábban kimutatták, hogy egy hosszúságú szó legfeljebb különböző palindromokat tartalmazhat; azokat a szavakat, amelyeken ez a becslés elérhető, palindromban gazdagnak nevezik. A palindromikus szavakban gazdag szavak fogalmát Amy Glen és munkatársai vezették be 2008-ban [13] . Rubinchik és Shur megmutatta, hogy egy palindromfa segítségével minden olyan palindromban gazdag szó kimutatható, amelynek hossza nem haladja meg a -t , ahol az ilyen szavak száma. Ez az eredmény lehetővé tette az A216264 szekvencia ismert tagjainak számának növelését OEIS- ben 25-ről 60-ra. A kapott adatok azt mutatták, hogy a szekvencia sokkal lassabban nő, mint azt korábban gondolták, vagyis felülről a [14] -hez kötődik . $n$ $n+1$ $n$ $O(R)$ $R$ $O(1,605^{n})$

Jegyzetek

↑ 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 et al., 2001 , pp. 542-546
↑ Rubinchik, Shur, 2016 , p. egy
↑ Rubinchik, Shur, 2018 , p. 6-11
↑ Mieso et al., 2020
↑ Rubinchik, 2016 , p. 75-76
↑ Groult, 2010
↑ Kosolobov et al., 2013
↑ OEIS szekvencia A216264 _
↑ Glen et al., 2009
↑ Rukavicka, 2017

Irodalom

Rubinchik M. Néhány karakterlánc-feldolgozási feladat számítási összetettsége - Jekatyerinburg : UrFU , 2016. - 83 p.
Droubay X., Justin J., Pirillo G. Episturmi szavak és de Luca és Rauzy néhány konstrukciója (angol) // Theoretical Computer Science - 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. Különálló palindromok számolása egy szóban lineáris időben // Inform . folyamat. Lett. - Elsevier BV , 2010. - 20. évf. 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 different subpalindromes online (English) // Prague Stringology Conference - Czech Technical University in Prague : 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 (angol) // ArXiv.org - 2020. - 14 délután. — ISSN 2331-8422 — arXiv:2006.02134
Rubinchik M., Shur A. M. The Number of Distinct Subpalindromes in Random Words (angol) // Fund. tájékoztatni. - 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 (angol) : Egy hatékony adatstruktúra palindromok feldolgozásához stringekben // 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 és társai. — Elsevier BV , 2018. — 1. évf. 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. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings // Lect . Megjegyzés Számítás. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [stb.] : 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 (angol) // 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 és társai. — Elsevier BV , 2009. — 20. évf. 30, Iss. 2. - P. 510-531. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2008.04.006 - arXiv:0801.1656
Rukavicka J. A gazdag szavak számáról (angol) // Lect. Megjegyzés Számítás. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [stb.] : Springer , 2017. - P. 345-352. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-62809-7_26 - arXiv:1701.07778

Linkek

A palindromfa . ITMO Wiki Abstracts . (határozatlan)

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Minta illesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc