Mostrar o rexistro simple do ítem
Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes
dc.contributor.author | Fariña, Antonio | |
dc.contributor.author | Gagie, Travis | |
dc.contributor.author | Manzini, Giovanni | |
dc.contributor.author | Navarro, Gonzalo | |
dc.contributor.author | Ordóñez, Alberto | |
dc.date.accessioned | 2017-02-23T16:20:04Z | |
dc.date.available | 2017-02-23T16:20:04Z | |
dc.date.issued | 2016-09-21 | |
dc.identifier.citation | 60 | es_ES |
dc.identifier.issn | 0302-9743 | |
dc.identifier.issn | 1611-3349 | |
dc.identifier.uri | http://hdl.handle.net/2183/18174 | |
dc.description | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_5 | es_ES |
dc.description.abstract | [Abstract] For many kinds of prefix-free codes there are efficient and compact alternatives to the traditional tree-based representation. Since these put the codes into canonical form, however, they can only be used when we can choose the order in which codewords are assigned to characters. In this paper we first show how, given a probability distribution over an alphabet of σσ characters, we can store a nearly optimal alphabetic prefix-free code in o(σ)o(σ) bits such that we can encode and decode any character in constant time. We then consider a kind of code introduced recently to reduce the space usage of wavelet matrices (Claude, Navarro, and Ordóñez, Information Systems, 2015). They showed how to build an optimal prefix-free code such that the codewords’ lengths are non-decreasing when they are arranged such that their reverses are in lexicographic order. We show how to store such a code in O(σlogL+2ϵL)O(σlogL+2ϵL) bits, where L is the maximum codeword length and ϵϵ is any positive constant, such that we can encode and decode any character in constant time under reasonable assumptions. Otherwise, we can always encode and decode a codeword of ℓℓ bits in time O(ℓ)O(ℓ) using O(σlogL)O(σlogL) bits of space. | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-P | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2015-69951-R | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; ITC-20151305 | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; ITC-20151247 | es_ES |
dc.description.sponsorship | Xunta de Galicia; GRC2013/053 | es_ES |
dc.description.sponsorship | Chile. Núcleo Milenio Información y Coordinación en Redes; ICM/FIC.P10-024F | es_ES |
dc.description.sponsorship | COST. IC1302 | es_ES |
dc.description.sponsorship | Academy of Finland; 268324 | es_ES |
dc.description.sponsorship | Academy of Finland; 250345 | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Springer | es_ES |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/690941 | |
dc.relation.uri | http://link.springer.com/chapter/10.1007%2F978-3-319-46049-9_5 | es_ES |
dc.subject | Efficient and Compact Representations | es_ES |
dc.subject | Some Non-canonical Prefix-Free Codes | es_ES |
dc.subject | Tree-based representation | es_ES |
dc.title | Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes | es_ES |
dc.type | info:eu-repo/semantics/conferenceObject | es_ES |
dc.rights.access | info:eu-repo/semantics/openAccess | es_ES |
UDC.journalTitle | Lecture Notes in Computer Science | es_ES |
UDC.volume | 9954 | es_ES |
UDC.endPage | 50 | es_ES |
dc.identifier.doi | 10.1007/978-3-319-46049-9_5 | |
UDC.conferenceTitle | 23rd International Symposium, SPIRE (String Processing and Information Retrieval) 2016, Beppu, Japan, October 18-20, 2016, | es_ES |
Ficheiros no ítem
Este ítem aparece na(s) seguinte(s) colección(s)
-
GI-LBD - Congresos, conferencias, etc. [26]
-
OpenAIRE [357]