Lyndon maleri

I kombinatorik og især i ordkombinatorik og tekstalgoritme er Lyndon-arrayet for en streng wet array af samme størrelse, hvis poster indeholder længderne på de maksimale Lyndon-ord, der starter i de respektive positioner. Denne tabel er nyttig til at bestemme og tælle gentagelser af faktorer i ordet. $L$

Beskrivelse

Lyndon maleri

Den Lyndon array af en streng er et array af samme størrelse, således at er længden af den længste faktor starter i position , som er en Lyndon ord. Formelt: $L$ $w$ ${\ displaystyle L [i]}$ $w$ $jeg$

{\ displaystyle L [i] = \ max \ {h: w [i, i + h-1] {\ text {er et Lyndon-ord}} \}.}

Eksempel

Tabellerne er nummererede med start fra 0. Enten . Lyndons diagram over ordet er givet i den sidste kolonne nedenfor: ${\ displaystyle w = 00011001}$

Indeks	Lyndon	L
0	00011001	8
1	0011	4
2	011	3
3	1	1
4	1	1
5	001	3
6	01	2
7	1	1

Lyndons maleri er

{\ displaystyle L = (8,4,3,1,1,3,2,1)}

Andre tabeller

To andre arrays er knyttet til Lyndons ordtabel, på den ene side suffikstabellen og på den anden side den såkaldte tabel med følgende lavere værdier :

Den nedenstående tabel følgende værdier (på engelsk næste mindre værdi matrix ) er indstillet til et heltal matrix ; det indeholder for det indeks det mindste indeks for en værdi, der er mindre end ; hvis en sådan værdi ikke findes, indeholder arrayet den maksimale værdi for dette indeks . Formelt, ${\ displaystyle N = N_ {A}}$ ${\ displaystyle A [1, n]}$ $jeg$ ${\ displaystyle A [i + 1, n]}$ ${\ displaystyle A [i]}$ $ikke$

{\ displaystyle N_ {A} [i] = \ min {\ {n \} \ cup \ {j \ mid j> i {\ text {and}} A [j] <A [i] \}}.}

For eksempel til bordet

{\ displaystyle A = (8,4,3,1,1,3,2,1)}

tabellen med følgende lavere værdier er

{\ displaystyle N = N_ {A} = (1,2,3,8,8,6,7,8)}

Forholdet mellem disse tabeller

Franek et al. har vist, at Lyndons array let beregnes i lineær tid ved at anvende konstruktionen af den næste mindre værdi array til det inverse af suffiks array: hvis vi betegner ordet suffiks array og det inverse af denne array (så end ssi ), så er Lyndons array givet med formlen $S$ $U$ ${\ displaystyle S [i] = j}$ ${\ displaystyle U [j] = i}$

{\ displaystyle L [i] = N_ {U} [i] -i}

.Eksempel

For ordet er suffiksetabellen - som giver længderne på suffikserne i leksikografisk rækkefølge - ${\ displaystyle w = 00011001}$

{\ displaystyle S = S (w) = (0,5,1,6,2,7,4,3)}

og tabellen med omvendte er

{\ displaystyle U = (0,2,4,7,6,1,3,5)}

Den følgende tabel med lavere værdier for U er

{\ displaystyle N = N_ {U} = (8,5,5,4,5,8,8,8)}

Formlen giver ${\ displaystyle L [i] = N_ {U} [i] -i}$

{\ displaystyle N_ {U} -I = (8,4,3,1,1,3,3,1) = L}

Kompleksitet i beregningen

Andre algoritmer er givet: en in-place kvadratisk algoritme baseret på Duval's itererede algoritme til Lyndon-faktorisering og et lineært algoritmisk skema baseret på lineær suffiksortering, beregning af det inverse suffiksarray og anvendelse af det. Algoritme til beregning af følgende lavere værdier. Disse algoritmer kører i værste fald i kvadratisk tid, en tredjedel tager lineær tid på bekostning af en foreløbig beregning af suffiksarrayet og det inverse suffiksarray for strengen. To varianter af en algoritme givet af Frantisek Franek og Michael Liut undgår den foreløbige beregning af globale datastrukturer og udføres i værste fald i tide . $n \ log n$

Ifølge Felipe Louza og hans medforfattere bruger alle algoritmer, der beregner Lyndons array i lineær tid, suffiks array-beregningen i et forudberegningstrin. En algoritme til sortering af suffikser af en streng blev givet af Nong i 2013. En variant af denne algoritme, der samtidig beregner Lyndon-arrayet og arrayet af suffikser med en streng af længde i yderligere tid og på plads hvor alfabetets størrelse er , blev givet af Louza et al. Eksperimentelle resultater med ægte og syntetiske datasæt viser, at deres algoritme ikke kun er pladseffektiv, men også hurtig i praksis. En effektiv algoritme blev præsenteret i 2020 af Bille et al . $ikke$ $Vi)$ ${\ displaystyle \ sigma + O (1)}$ $\ sigma$

Ansøgninger

En af de applikationer skyldes Bannai et al. De brugte Lyndon rødder af kørsler for at bevise den kører formodninger , at antallet af kørsler i et ord øges med længden af ordet. I samme papir præsenterede de en algoritme til beregning af alle kørsler i et ord i lineær tid, hvilket kræver kendskab til alle de maksimale Lyndon-faktorer til højre for det givne ord, deraf Lyndon-tabellen for ordet til en ordre over alfabet og i omvendt rækkefølge.

Noter og referencer

Frantisek Franek, ASM Sohidull Islam, M. Sohel Rahman og William F. Smyth, ”Algoritmer til beregning af Lyndon Array” , i Prag Stringology Conference , 2016( ISBN 978-80-01-05996-8 , læs online ) , s. 172-184
Felipe A. Louza , WF Smyth , Giovanni Manzini og Guilherme P. Telles , " Lyndon array-konstruktion under Burrows - Wheeler-inversion ", Journal of Discrete Algorithms , bind. 50, 2018, s. 2–9 ( ISSN 1570-8667 , DOI 10.1016 / j.jda.2018.08.001 )
Frantisek Franek og Michael Liut, ”Algoritmer til beregning af Lyndon Array Revisited” , i Prag Stringology Conference , 2019( ISBN 978-80-01-06618-8 , læs online ) , s. 16-28
Uwe Baier, “Sortering af suffikser i lineær tid - En ny tilgang til konstruktion af suffiksarray” , i Roberto Grossi og Moshe Lewenstein (red.), 27. årlige symposium om kombinatorisk mønstermatch , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, koll. "Leibniz International Proceedings in Informatics (LIPIcs)" ( nr . 54), 2016( ISBN 978-3-95977-012-5 , DOI 10.4230 / LIPIcs.CPM.2016.23 , læs online ) , s. 123: 1-23: 12
Frantisek Franek og Michael Liut , “ Computing Maximal Lyndon Substrings of a String ”, Algorithms , vol. 13, nr . 11, 2020, Nr . 294 ( ISSN 1999-4893 , DOI 10.3390 / a13110294 ).
Felipe A. Louza , Sabrina Mantaci , Giovanni Manzini , Marinella Sciortino og Guilherme P. Telles , “Inducing the Lyndon Array” , i strengbehandling og informationssøgning - 26. internationale symposium, SPIRE 2019 ,, Segovia, koll. "Forelæsningsnotater i datalogi", 2019( ISBN 978-3-030-32685-2 , DOI 10.1007 / 978-3-030-32686-9_10 , arXiv 1905.12987 ) , s. 138-151.
Ge Nong , “ Praktisk lineær-time O (1) -workspace-suffiksortering til konstante alfabeter ”, ACM-transaktioner på informationssystemer , bind. 31, nr . 3, 2013, s. 1–15 ( ISSN 1046-8188 , DOI 10.1145 / 2493175.2493180 ).
Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro og Eva Rotenberg, " Rumeffektiv konstruktion af Lyndon-arrays i lineær tid" , i Artur Czumaj, Anuj Dawar og Emanuela Merelli (redaktører), 47. internationale kollokvium om automatik, sprog og programmering (ICALP 2020) , Schloss Dagstuhl-Leibniz-Zentrum für Informatik, koll. "Leibniz International Proceedings in Informatics (LIPIcs)" ( nr . 168),2020( DOI 10.4230 / LIPIcs.ICALP.2020.14 , læs online ) , s. 14: 1-14: 18.
Hideo Bannai , Tomohiro I , Shunsuke Inenaga , Yuto Nakashima , Masayuki Takeda og Kazuya Tsuruta , ” De’Runs’Sætning ”, SIAM Journal on Computing , vol. 46, nr . 5, 2017, s. 1501–1514 ( ISSN 0097-5397 , DOI 10.1137 / 15M1011032 ).

Relaterede artikler