Palindrom træ

palindrom træ

engelsk træ

palindromtræ til string eertree

Type

datastruktur

Opfindelsens år

2015

Forfatter

Mikhail Rubinchik [d]

Kompleksitet i O-symboler

	I værste fald
Bygning	$O(n\log \sigma )$
Hukommelsesforbrug	$På)$

Mediefiler på Wikimedia Commons

Et palindromisk træ ( eng. palindromic tree , også overtree [1] , eng. eertree ) er en datastruktur designet til at lagre og behandle palindromiske delstrenge af en streng . Det blev foreslået af forskere fra Ural Federal University Mikhail Rubinchik og Arseny Shur i 2015. Repræsenterer to præfikstræer , samlet fra højre "halvdele" af palindromiske understrenge af henholdsvis lige og ulige længder. Strukturen optager hukommelse og kan bygges i tid , hvor er længden af strengen, og er antallet af forskellige tegn i den. Ved hjælp af et palindromtræ kan man effektivt løse sådanne problemer som at tælle antallet af forskellige palindromiske delstrenge, finde opdelingen af en streng i det mindste antal palindromer, kontrollere om en delstreng er et palindrom og andre. $På)$ $O(n\log \sigma )$ $n$ $\sigma$

Notation

Lad være en streng og være den omvendte streng . Når palindromtræet i en streng beskrives , bruges følgende notation [2] : ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1))$ $S$ $S$

En streng kaldes et palindrom , hvis den læser det samme fra venstre mod højre og højre mod venstre, altså hvis . $S$ ${\displaystyle S=S^{R))$

En understreng er en kontinuerlig undersekvens af en streng og betegnet med . $S$ ${\displaystyle S_{l,r}=s_{l}s_{l+1}\dots s_{r))$

Især den understreng, der har, kaldes strengpræfikset , og den understreng, der har , kaldes strengsuffikset . $l=1$ $S$ $r=n$ $S$

En palindromisk understreng ( subpalindrom ) er en understreng , der er et palindrom. Hvis denne understreng også er et præfiks eller suffiks af strengen , så kaldes det henholdsvis et præfiks- eller suffiks-palindrom . $S$ $S$

Et præfikstræ er et rodorienteret træ , hvis buer er mærket med symboler på en sådan måde, at ikke mere end én kant mærket med et givet symbol kommer fra nogetafdette træs toppunkt . $v$

Hvert toppunkt i præfikstræet svarer til en streng svarende til sammenkædningen af tegn på stien fra træets rod til dette toppunkt.

Træstruktur

I notationen ovenfor er palindromtræet i en streng en rettet graf , hvor hvert toppunkt svarer til og er identificeret med et unikt subpalindrom af strengen. Hvis strengen har subpalindromer og , hvor er en eller anden alfabetisk karakter , så har palindromtræet en bue markeret med symbolet , fra toppunktet svarende til , til toppunktet svarende til . I en sådan graf kan ethvert toppunkt kun have én indkommende bue. For nemheds skyld introduceres også to hjælpespidser, som svarer til henholdsvis længdepalindromer ( tom streng ) og ("imaginær" streng. Buer fra den tomme streng fører til toppunkter svarende til palindromer af formen , og fra den "imaginære streng" til toppunkter svarende til palindromer af formen (det vil sige bestående af et enkelt tegn). Et vertex kaldes selv hvis det har et lige længde palindrom, og ellers ulige . Det følger af definitionen, at buer i et palindromtræ kun passerer mellem hjørner med samme paritet. Fra et præfikstræs synspunkt kan denne struktur beskrives som følger [3] : $S$ $t$ $ctc$ $c$ $c$ $t$ $ctc$ $0$ $-en$ $cc$ $c$

Toppunkterne og buerne på palindromtræet danner to præfikstræer, hvis rødder er placeret ved de hjørner, der definerer henholdsvis de tomme og "imaginære" strenge. I dette tilfælde er det første præfikstræ sammensat af de højre halvdele af subpalindromer af lige længde, og det andet af ulige.

Antallet af toppunkter i palindromtræet overstiger ikke , hvilket er en direkte konsekvens af følgende lemma [4] : $n+2$

En længdestreng kan højst have distinkte ikke-tomme palindromiske understrenge. Efter at have tildelt et bestemt tegn til slutningen af en streng, kan antallet af forskellige subpalindromer i denne streng desuden ikke stige med mere end . $S$ $n$ $n$ $c$ $en$

Bevis

Denne erklæring følger af følgende fakta:

Hvis et palindrom er et suffiks af et palindrom , så er det også dets præfiks; $u$ $v$
Hvis palindromer og er suffikser af strengen og , så forekommer det mindst to gange (som et præfiks og som et suffiks ); $u$ $v$ $w$ $|u|<|v|$ $u$ $w$ $v$
Enhver streng kan højst have ét unikt ( kun én gang) palindrom-suffiks. $w$ $w$

Den sidste egenskab svarer i det væsentlige til lemmaet, da alle nye understrenge, der dukker op, når det næste tegn tilføjes til strengen, skal være dets suffikser [5] . ■

Ud over de sædvanlige buer, der tjener som overgange for præfikstræet, er der for hvert vertex af palindromtræet defineret et suffiksled , der fører fra toppunktet til toppunktet svarende til det største egentlige (ikke lig med hele strengen ) suffiks palindrom . Samtidig er suffiksleddet fra det "imaginære" toppunkt ikke defineret, men per definition fører det fra et tomt toppunkt til det "imaginære". Suffiksled danner et træ med rod i et "imaginært" toppunkt og spiller en vigtig rolle i konstruktionen af et palindromtræ [3] . $v$ $u$ $v$ $v$

Konstruktion

Som mange andre strengstrukturer er et palindromtræ bygget iterativt . I starten består den kun af toppunkter svarende til de tomme og imaginære strenge. Strukturen genopbygges derefter gradvist, efterhånden som strengen vokser et tegn ad gangen. Da der højst dukker ét nyt palindrom op i en streng, når man tilføjer ét tegn, vil genopbygning af træet i værste fald kræve tilføjelse af én ny node og et suffikslink til det. For at bestemme en mulig ny knude under trækonstruktion, opretholdes en sidste pointer til knudepunktet svarende til det største af de nuværende palindrom-suffikser [3] .

Alle suffiks-palindromer i strengen kan nås med suffikslinks fra sidste , så for at bestemme et nyt suffiks-palindrom (det vil svare til det nye toppunkt, hvis nogen) er det nødvendigt at følge suffiksleddet fra sidste , indtil det konstateres, at tegnet, der går forud for det aktuelle suffiks-palindrom , matcher det tegn, der blev tildelt strengen. Mere formelt, lad være strengens maksimale palindrom-suffiks , så enten , eller , hvor er et eller andet palindrom-suffiks . Således itererer man blandt suffikslinkene i last , kan man afgøre, om det kan udvides til ved at sammenligne tegnene og . Når det tilsvarende palindrom-suffiks er fundet, bør du kontrollere, om palindromtræet indeholder en overgang fra det tilsvarende toppunkt ved symbolet [3] . $P$ ${\displaystyle 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}$ ${\displaystyle s_{k))$ $Q$ ${\displaystyle s_{k))$

Hvis der er en sådan overgang, er den allerede stødt på i linjen tidligere og svarer til det toppunkt, som denne overgang fører til. Ellers skal du oprette et nyt toppunkt til det og lave en overgang fra . Dernæst skal du definere et suffikslink for , der matcher det næstlængste palindrom-suffiks . For at finde det, bør man fortsætte med at omgå de sidste suffiksforbindelser, indtil det andet vertex stødes på , sådan at ; det er dette toppunkt, der vil være suffikslinket . Hvis vi betegner overgangen fra toppen med symbol som , kan hele processen beskrives med følgende pseudokode [3] : $P$ ${\displaystyle s_{k))$ $Q$ $P$ ${\displaystyle S_{1,k))$ $Q$ ${\displaystyle s_{k-|Q|-1}=s_{k))$ $P$ $v$ $c$ $\delta(v,c)$

find_link(v)-funktion: mens s k -len(v)-1 ≠ s k : assign v = link(v) return v funktion add_letter(c): tildel k = k + 1 definer s k = c definer q = find_link(sidste) hvis δ(q, c) ikke er defineret: definer p = new_vertex() definer len(p) = len(q ) + 2 definere link(p) = δ(find_link(link(q)), c) definere δ(q, c) = p tildele sidste = δ(q, c)

Det antages her, at træet i første omgang kun er beskrevet af to toppunkter med længder og følgelig med en suffiksforbindelse fra det første toppunkt til det andet. Variablen sidst gemmer toppunktet svarende til det største suffiks palindrom af den aktuelle linje, indledningsvis peger det på toppunktet på den nulte linje. Det antages også, at det oprindeligt er lig med, og der er skrevet et eller andet tjenestetegn ind, som ikke forekommer i strengen . $0$ $-en$ $k$ $0$ $s_{0}$ ${\displaystyle s_{1}s_{2}\dots s_{k))$

Beregningsmæssig kompleksitet

Kompleksiteten af algoritmen kan variere afhængigt af de datastrukturer, der lagrer springtabellen i træet. I det generelle tilfælde, når du bruger et associativt array , når den tid, der bruges på at få adgang , , hvor er størrelsen på det alfabet, som strengen er bygget af. Det er værd at bemærke, at hver iteration af det første kald til find_link reducerer længden af last , og af den anden, længden af link(last) , som kun kan øges med én mellem successive kald til add_letter . Den samlede tid for find_link overstiger således ikke , og den samlede tid, der kræves for at udføre add_letter- kald , kan estimeres til [3] . Hukommelsesforbruget af denne struktur er lineært i værste fald, men hvis vi betragter strukturens gennemsnitlige størrelse over alle strenge af en given længde , vil det gennemsnitlige hukommelsesforbrug være i størrelsesordenen [6] . $\delta(q,c)$ $O(\log \sigma )$ $\sigma$ $På)$ $n$ $O(n\log \sigma )$ $n$ $O({\sqrt {n\sigma )))$

Ændringer

Samtidig med introduktionen af denne datastruktur foreslog Rubinchik og Shur også en række modifikationer, der gør det muligt at udvide omfanget af opgaver løst af et palindromtræ. Især blev der foreslået en metode, der gør det muligt at konstruere et generelt palindromtræ for et sæt strenge med de samme asymptoter . En sådan modifikation giver os mulighed for at løse de samme problemer, der betragtes i sammenhæng med et sæt strenge - for eksempel at finde det største fælles subpalindrom af alle strenge eller antallet af forskellige subpalindromer af alle strenge i aggregatet. En anden foreslået ændring var en variant af trækonstruktion, hvor tilføjelsen af et tegn tager tid i værste fald (og ikke amortiseres , som det sker i standardkonstruktionen) og hukommelse. Denne tilgang gør det muligt at give delvis persistens af træet, hvor det er muligt at rulle tilføjelsen af det sidste tegn tilbage på vilkårlige tidspunkter. Derudover blev der foreslået en fuldt persistent version af træet, som giver dig mulighed for at få adgang til og tilføje et tegn til enhver af de tidligere gemte versioner i tid og hukommelse i værste fald [7] . ${\displaystyle S_{1},S_{2},\dots ,S_{k))$ $O(\log n)$ $O(\log \sigma )$ $O(1)$ $O(\log n)$

I 2019 udviklede Watanabe og kolleger en datastruktur baseret på et palindromtræ, kaldet e 2 rtre 2 , til at arbejde med subpalindromer af strenge givet ved run- length- kodning [4] , og i 2020, det samme team af forfattere, sammen med Mieno udviklede to algoritmer, der gør det muligt at opretholde et palindromtræ på et glidende vindue af størrelse . Den første af disse algoritmer kræver tid og hukommelse, og den anden kræver tid og hukommelse [8] . $d$ $O(n\log \sigma )$ $O(d)$ $O(n+d\sigma )$ $O(d\sigma )$

Ansøgninger

Palindromtræet giver mange mulige anvendelsesmuligheder til at opnå teoretisk hurtige og praktisk taget let implementerede algoritmer til løsning af en række kombinatoriske problemer inden for programmering og matematisk kybernetik [9] .

En af de opgaver, som denne struktur blev udviklet til, er at tælle forskellige subpalindromer i en streng online . Det kan indstilles som følger: Et tegn ad gangen tildeles et tegn ad gangen til den oprindeligt tomme streng. Ved hvert trin skal du udskrive antallet af forskellige subpalindromer i den givne streng. Fra palindromtræets synspunkt svarer dette til at udskrive antallet af ikke-trivielle hjørner i strukturen ved hvert trin. En lineær løsning til offlineversionen af dette problem blev præsenteret i 2010 [10] , og den optimale løsning med eksekveringstid for onlineversionen blev fundet i 2013 [11] . Den angivne løsning brugte dog to "tunge" datastrukturer - en analog af Manaker-algoritmen samt et suffikstræ . Palindromtræet har på den ene side samme asymptotik i værste fald, og på den anden side er det en meget mere let struktur [3] . $O(n\log \sigma )$

En anden mulig anvendelse af denne struktur er opregningen af palindromrige binære strenge [12] . Tidligere blev det vist, at et ord af længde ikke kan indeholde mere end forskellige palindromer; ord, som dette skøn opnås på, kaldes palindrom-rige. Begrebet palindromiske ord blev introduceret af Amy Glen og kolleger i 2008 [13] . Rubinchik og Shur viste, at man ved hjælp af et palindromtræ kan detektere alle palindromiske ord, hvis længde ikke overstiger , hvor er antallet af sådanne ord. Dette resultat gjorde det muligt at øge antallet af kendte medlemmer af A216264 -sekvensen i OEIS fra 25 til 60. De opnåede data viste, at sekvensen vokser meget langsommere end tidligere antaget, nemlig at den er afgrænset ovenfra som [14] . $n$ $n+1$ $n$ $O(R)$ $R$ $O(1.605^{n})$

Noter

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

Litteratur

Rubinchik M. Beregningsmæssig kompleksitet af nogle strengbehandlingsopgaver - Jekaterinburg : UrFU , 2016. - 83 s.
Droubay X., Justin J., Pirillo G. Episturmiske ord og nogle konstruktioner af de Luca og Rauzy (engelsk) // Theoretical Computer Science - Elsevier BV , 2001. - Vol. 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. Tælling af distinkte palindromer i et ord i lineær tid // Inform . behandle. 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 (engelsk) // Prague Stringology Conference - Czech Technical University in Prague : 2013. - S. 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 (engelsk) // ArXiv.org - 2020. - 14 om eftermiddagen. — ISSN 2331-8422 — arXiv:2006.02134
Rubinchik M., Shur A. M. Antallet af distinkte subpalindromer i tilfældige ord (engelsk) // Fund. meddele. - 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 (engelsk) : En effektiv datastruktur til behandling af palindromer i strenge // 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. - 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. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings // Lect . Bemærk Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [etc.] : 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. Palindromisk rigdom (engelsk) // 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. - S. 510-531. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2008.04.006 - arXiv:0801.1656
Rukavicka J. Om antallet af rige ord (engelsk) // Lect. Bemærk Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [etc.] : Springer , 2017. - S. 345-352. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-62809-7_26 - arXiv:1701.07778

Links

Palindromtræet . ITMO Wiki Abstracts . (ubestemt)

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng