ARCA è l'archivio istituzionale ad accesso aperto della ricerca dell'Università Ca' Foscari Venezia e nasce nel 2014 con lo scopo di raccogliere, diffondere e conservare la produzione scientifica dell'Università. Costituisce di fatto il catalogo della ricerca di Ateneo.ARCA è un sistema Open Access: è non solo consultabile da tutti e visibile nei motori di ricerca, ma anche interoperabile con il portale cerCa. In questo modo vengono valorizzate la produzione scientifica dell'Ateneo e la visibilità dei ricercatori.
EnglishLet T be a text of length n on an alphabet Σ of size σ, and let H0 be the zero-order empirical entropy of T. We show that the LZ77 factorization of T can be computed in nH0+o(nlogσ)+O(σlogn) bits of working space with an online algorithm running in O(nlogn) time. Previous space-efficient online solutions either work in compact space and O(nlogn) time, or in succinct space and O(nlog3n) time.
| Autori: | ||
| Data di pubblicazione: | 2015 | |
| Titolo: | Fast online Lempel-Ziv factorization in compressed space | |
| Titolo del libro: | String Processing and Information Retrieval 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-319-23826-5_2 | |
| Appare nelle tipologie: | 4.1 Articolo in Atti di convegno |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| lz77.pdf | N/A | Riservato |
http://hdl.handle.net/10278/3729832
Copyright © 2021