Archivio istituzionale della ricerca dell'Università degli Studi di Palermo
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, pubblicazioni, progetti, attività) adottato dall’Università di Palermo, e ha lo scopo di raccogliere, conservare, documentare, e diffondere ad accesso aperto le informazioni relative alla produzione scientifica degli autori afferenti all’Ateneo.
EnglishIn this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in O(n) time using O(n) words of working space, where n is the length of the text and is the alphabet size. Our result improves the previous best space requirement for linear time computation of the Lyndon array. In fact, all the known linear algorithms for Lyndon array computation use suffix sorting as a preprocessing step and use O(n) words of working space in addition to the Lyndon array and suffix array. Experimental results with real and synthetic datasets show that our algorithm is not only space-efficient but also fast in practice.
| Data di pubblicazione: | 2019 |
| Titolo: | Inducing the Lyndon Array |
| Autori: | |
| Citazione: | Louza, F., Mantaci, S., Manzini, G., Sciortino, M., & Telles, G. (2019). Inducing the Lyndon Array. In N.R. Brisaboa, & S.J. Puglisi (a cura di), String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings (pp. 138-151). Springer. |
| Abstract: | In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in O(n) time using O(n) words of working space, where n is the length of the text and is the alphabet size. Our result improves the previous best space requirement for linear time computation of the Lyndon array. In fact, all the known linear algorithms for Lyndon array computation use suffix sorting as a preprocessing step and use O(n) words of working space in addition to the Lyndon array and suffix array. Experimental results with real and synthetic datasets show that our algorithm is not only space-efficient but also fast in practice. |
| URL: | https://link.springer.com/chapter/10.1007/978-3-030-32686-9_10 |
| ISBN: | 978-3-030-32685-2 978-3-030-32686-9 |
| Digital Object Identifier (DOI): | 10.1007/978-3-030-32686-9_10 |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica Settore ING-INF/05 - Sistemi Di Elaborazione Delle Informazioni |
| Appare nelle tipologie: | 2.07 Contributo in atti di convegno pubblicato in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| camera-ready.pdf | Post-print | Open Access Visualizza/Apri |
Copyright © 2020