Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Run-Length Encoding in a Finite Universe
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-9295-3508
2019 (English)In: String Processing and Information Retrieval: 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings, Springer, 2019, p. 355-371Conference paper, Published paper (Refereed)
Abstract [en]

Text compression schemes and succinct data structures usually combine sophisticated probability modes with basic coding methods whose average codeword length closely match the entropy of known distributions. In the frequent case where basic coding represents run-lengths of outcomes with probability p, i.e. geometric distribution Pr(i)=pⁱ(1-p), a Golomb code is an optimal instantaneous code, which has the additional advantage that codewords can be computed using only an integer parameter calculated from p, without need for a large or sophisticated data structure. Golomb coding does not, however, gracefully handle the case where run-lengths are bounded by a known integer n, where codewords allocated for the case i>n are wasted. While negligible for large n, this makes Golomb coding unattractive in situations where n is recurrently small, e.g., when representing many short lists, or when the range of n is narrowed down by a recursive algorithm.

Place, publisher, year, edition, pages
Springer, 2019. p. 355-371
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11811
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mau:diva-36990DOI: 10.1007/978-3-030-32686-9_25ISBN: 978-3-030-32685-2 (print)ISBN: 978-3-030-32686-9 (electronic)OAI: oai:DiVA.org:mau-36990DiVA, id: diva2:1504129
Conference
26th International Symposium on String Processing and Information Retrieval (SPIRE 2019, Segovia, Spain, October 7–9, 2019
Available from: 2020-11-26 Created: 2020-11-26 Last updated: 2022-08-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Larsson, N. Jesper

Search in DiVA

By author/editor
Larsson, N. Jesper
By organisation
Department of Computer Science and Media Technology (DVMT)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 114 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf