Lyndon pittura
In combinatoria , e in particolare in combinatoria di parole e algoritmi di testo , l' array Lyndon di una stringa wè un array della stessa dimensione le cui voci contengono le lunghezze delle parole Lyndon massime che iniziano nelle rispettive posizioni. Questa tabella è utile per determinare e contare le ripetizioni dei fattori nella parola.
L{\ stile di visualizzazione L}
Descrizione
Lyndon pittura
L' array Lyndon di una stringa è un array della stessa dimensione tale che è la lunghezza del fattore più lungo a partire dalla posizione che è una parola Lyndon. Formalmente:
L{\ stile di visualizzazione L}w{\ stile di visualizzazione w}L[io]{\ stile di visualizzazione L [i]}w{\ stile di visualizzazione w}io{\ stile di visualizzazione i}
L[io]=max{h:w[io,io+h-1] è una parola di Lyndon}.{\ displaystyle L [i] = \ max \ {h: w [i, i + h-1] {\ text {è una parola di Lyndon}} \}.}Esempio
Le tabelle sono numerate a partire da 0. O . Il grafico della parola di Lyndon è riportato nell'ultima colonna in basso:
w=00011001{\ stile di visualizzazione w = 00011001}
Indice
|
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
|
Il dipinto di Lyndon è
L=(8,4,3,1,1,3,2,1){\ stile di visualizzazione L = (8,4,3,1,1,3,2,1)}.
Altre tabelle
Altri due array sono collegati alla tabella di una parola di Lyndon, da un lato la tabella dei suffissi e dall'altro la cosiddetta tabella dei seguenti valori inferiori :
La tabella sotto i seguenti valori (in inglese array di valori più piccoli ) è impostata su un array intero ; contiene, per l'indice , l'indice più piccolo di un valore in cui è minore di ; se tale valore non esiste, l'array contiene il valore massimo per questo indice . formalmente,
NON=NONA{\ stile di visualizzazione N = N_ {A}}A[1,non]{\ stile di visualizzazione A [1, n]}io{\ stile di visualizzazione i}A[io+1,non]{\ stile di visualizzazione A [i + 1, n]}A[io]{\ stile di visualizzazione A [i]}non{\ stile di visualizzazione n}
NONA[io]=min{non}∪{j|j>io e A[j]<A[io]}.{\ displaystyle N_ {A} [i] = \ min {\ {n \} \ cup \ {j \ mid j> i {\ text {e}} A [j] <A [i] \}}.}.
Ad esempio, per la tavola
A=(8,4,3,1,1,3,2,1){\ stile di visualizzazione A = (8,4,3,1,1,3,2,1)},
la tabella dei seguenti valori inferiori è
NON=NONA=(1,2,3,8,8,6,7,8){\ stile di visualizzazione N = N_ {A} = (1,2,3,8,8,6,7,8)}.
Relazione tra queste tabelle
Franek et al. hanno mostrato che l'array di Lyndon è facilmente calcolabile in tempo lineare applicando la costruzione dell'array di valori più piccoli all'inverso dell'array di suffissi: se indichiamo l'array di suffissi della parola e l'inverso di questo array (quindi di ssi ), quindi l'array di Lyndon è dato dalla formula
S{\ stile di visualizzazione S}tu{\ stile di visualizzazione U}S[io]=j{\ stile di visualizzazione S [i] = j}tu[j]=io{\ stile di visualizzazione U [j] = i}
L[io]=NONtu[io]-io{\ displaystyle L [i] = N_ {U} [i] -i}.Esempio
Per la parola , la tabella dei suffissi - che dà le lunghezze dei suffissi in ordine lessicografico - è
w=00011001{\ stile di visualizzazione w = 00011001}
S=S(w)=(0,5,1,6,2,7,4,3){\ stile di visualizzazione S = S (w) = (0,5,1,6,2,7,4,3)}e la tavola degli inversi è
tu=(0,2,4,7,6,1,3,5){\ stile di visualizzazione U = (0,2,4,7,6,1,3,5)}.
La seguente tabella di valori inferiori per U è
NON=NONtu=(8,5,5,4,5,8,8,8){\ stile di visualizzazione N = N_ {U} = (8,5,5,4,5,8,8,8)}.
La formula dà
L[io]=NONtu[io]-io{\ displaystyle L [i] = N_ {U} [i] -i}
NONtu-io=(8,4,3,1,1,3,3,1)=L{\ displaystyle N_ {U} -I = (8,4,3,1,1,3,3,1) = L} !
Complessità di calcolo
Sono stati forniti altri algoritmi: un algoritmo quadratico sul posto basato sull'algoritmo iterato di Duval per la fattorizzazione di Lyndon e uno schema algoritmico lineare basato sull'ordinamento lineare dei suffissi, calcolando l'array di suffissi inversi e applicandolo ad esso. . Questi algoritmi funzionano in tempo quadratico nel caso peggiore, un terzo richiede tempo lineare, a costo di un calcolo preliminare dell'array di suffissi e dell'array di suffissi inversi della stringa. Due varianti di un algoritmo fornite da Frantisek Franek e Michael Liut evitano il calcolo preliminare di strutture dati globali e vengono eseguite nel peggiore dei casi nel tempo .
nonlognon{\ displaystyle n \ log n}
Secondo Felipe Louza e i suoi coautori, tutti gli algoritmi che calcolano l'array di Lyndon in tempo lineare utilizzano il calcolo dell'array suffisso in una fase di precalcolo. Un algoritmo per ordinare i suffissi di una stringa è stato fornito da Nong nel 2013. Una variante di questo algoritmo che calcola simultaneamente l'array di Lyndon e l'array di suffissi di una stringa di lunghezza in un tempo aggiuntivo e nel luogo dove è la dimensione dell'alfabeto , è stato fornito da Louza et al. I risultati sperimentali con set di dati reali e sintetici mostrano che il loro algoritmo non è solo efficiente in termini di spazio, ma anche veloce nella pratica. Un algoritmo efficiente è stato presentato nel 2020 da Bille et al .
non{\ stile di visualizzazione n}oh(non){\ stile di visualizzazione O (n)}σ+oh(1){\ displaystyle \ sigma + O (1)}σ{\ displaystyle \ sigma}
Applicazioni
Una delle applicazioni è dovuta a Bannai et al. Hanno usato le radici delle esecuzioni di Lyndon per dimostrare la congettura delle esecuzioni secondo cui il numero di esecuzioni in una parola è aumentato della lunghezza della parola. Nello stesso articolo, hanno presentato un algoritmo per calcolare tutte le esecuzioni in una parola in tempo lineare che richiede la conoscenza di tutti i fattori di Lyndon massimi a destra della parola data, quindi la tabella di Lyndon della parola per a un ordine sul alfabeto e per il suo ordine inverso.
Note e riferimenti
-
Frantisek Franek, ASM Sohidull Islam, M. Sohel Rahman e William F. Smyth, “Algorithms to Compute the Lyndon Array” , alla Conferenza di Stringologia di Praga ,
2016( ISBN 978-80-01-05996-8 , leggi online ) , p. 172-184
-
Felipe A. Louza , WF Smyth , Giovanni Manzini e Guilherme P. Telles , “ Costruzione di array di Lyndon durante Burrows – Wheeler inversion ”, Journal of Discrete Algorithms , vol. 50,
2018, pag. 2–9 ( ISSN 1570-8667 , DOI 10.1016 / j.jda.2018.08.001 )
-
Frantisek Franek e Michael Liut, “Algorithms to Compute the Lyndon Array Revisited” , in Prague Stringology Conference ,
2019( ISBN 978-80-01-06618-8 , leggi in linea ) , p. 16-28
-
Uwe Baier, “Smistamento dei suffissi in tempo lineare - Un nuovo approccio alla costruzione di array di suffissi” , in Roberto Grossi e Moshe Lewenstein (a cura di), 27° Simposio annuale sulla corrispondenza dei modelli combinatori , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, coll. “Leibniz International Proceedings in Informatics (LIPIcs)” ( n o 54),
2016( ISBN 978-3-95977-012-5 , DOI 10.4230 / LIPics.CPM.2016.23 , leggi online ) , p. 123: 1-23: 12
-
Frantisek Franek e Michael Liut , “ Computing Maximal Lyndon Substrings of a String ”, Algorithms , vol. 13, n . 11,
2020, Articolo n ° 294 ( ISSN 1999-4893 , DOI 10.3390 / a13110294 ).
-
Felipe A. Louza , Sabrina Mantaci , Giovanni Manzini , Marinella Sciortino e Guilherme P. Telles , “Inducing the Lyndon Array” , in String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019,, Segovia, coll. "Appunti delle lezioni di Informatica",
2019( ISBN 978-3-030-32685-2 , DOI 10.1007 / 978-3-030-32686-9_10 , arXiv 1905.12987 ) , p. 138–151.
-
Ge Nong , “ Smistamento dei suffissi in tempo lineare pratico O (1) -workspace per alfabeti costanti ”, ACM Transactions on Information Systems , vol. 31, n . 3,
2013, pag. 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 e Eva Rotenberg, “Space Efficient Construction of Lyndon Arrays in Linear Time” , in Artur Czumaj, Anuj Dawar e Emanuela Merelli (a cura di), 47th International Colloquium on Automata, Languages and Programming (ICALP 2020) , Schloss Dagstuhl-Leibniz-Zentrum für Informatik, coll. “Leibniz International Proceedings in Informatics (LIPIcs)” ( n o 168),2020( DOI 10.4230 / LIPics.ICALP.2020.14 , leggi online ) , p. 14:1-14:18.
-
Hideo Bannai , Tomohiro I , Shunsuke Inenaga , Yuto Nakashima , Masayuki Takeda e Kazuya Tsuruta , “ The“ Runs ”Theorem ”, SIAM Journal on Computing , vol. 46, n . 5,
2017, pag. 1501-11514 ( ISSN 0097-5397 , DOI 10.1137 / 15M1011032 ).
Articoli Correlati
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">