Show simple item record

dc.contributor.authorFariña, Antonio
dc.contributor.authorGagie, Travis
dc.contributor.authorManzini, Giovanni
dc.contributor.authorNavarro, Gonzalo
dc.contributor.authorOrdóñez, Alberto
dc.date.accessioned2017-02-23T16:20:04Z
dc.date.available2017-02-23T16:20:04Z
dc.date.issued2016-09-21
dc.identifier.citation60es_ES
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.urihttp://hdl.handle.net/2183/18174
dc.descriptionThe final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_5es_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(σlog⁡L+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(σlog⁡L) bits of space.es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-Pes_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2015-69951-Res_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; ITC-20151305es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; ITC-20151247es_ES
dc.description.sponsorshipXunta de Galicia; GRC2013/053es_ES
dc.description.sponsorshipChile. Núcleo Milenio Información y Coordinación en Redes; ICM/FIC.P10-024Fes_ES
dc.description.sponsorshipCOST. IC1302es_ES
dc.description.sponsorshipAcademy of Finland; 268324es_ES
dc.description.sponsorshipAcademy of Finland; 250345es_ES
dc.language.isoenges_ES
dc.publisherSpringeres_ES
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/690941
dc.relation.urihttp://link.springer.com/chapter/10.1007%2F978-3-319-46049-9_5es_ES
dc.subjectEfficient and Compact Representationses_ES
dc.subjectSome Non-canonical Prefix-Free Codeses_ES
dc.subjectTree-based representationes_ES
dc.titleEfficient and Compact Representations of Some Non-canonical Prefix-Free Codeses_ES
dc.typeinfo:eu-repo/semantics/conferenceObjectes_ES
dc.rights.accessinfo:eu-repo/semantics/openAccesses_ES
UDC.journalTitleLecture Notes in Computer Sciencees_ES
UDC.volume9954es_ES
UDC.endPage50es_ES
dc.identifier.doi10.1007/978-3-319-46049-9_5
UDC.conferenceTitle23rd International Symposium, SPIRE (String Processing and Information Retrieval) 2016, Beppu, Japan, October 18-20, 2016,es_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record