Abstract
Text compression schemes and compact data structures usually combine sophisticated probability models 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 that have probability p, i.e. the geometric distribution \(\Pr (i)=p^i(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. In this case, 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 of integers drawn from limited ranges, or when the range of n is narrowed down by a recursive algorithm.
We address the problem of choosing a code for this case, considering efficiency from both information-theoretic and computational perspectives, and arrive at a simple code that allows computing a codeword using only O(1) simple computer operations and O(1) machine words. We demonstrate experimentally that the resulting representation length is very close (equal in a majority of tested cases) to the optimal Huffman code, to the extent that the expected difference is practically negligible. We describe efficient branch-free implementation of encoding and decoding.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Golomb’s formulation partitions values into groups of equal codeword length, which is a slightly less convenient take on the same family of codes.
- 2.
Many authors use the term binary code. However, this clashes with the fact that all codes we address are binary in a wider sense.
References
Capurro, I., Lecumberry, F., Martín, Á., Ramírez, I., Rovira, E., Seroussi, G.: Efficient sequential compression of multichannel biomedical signals. IEEE J. Biomed. Health Inform. 21(4), 904–916 (2017)
Choi, J.A., Ho, Y.S.: Efficient residual data coding in CABAC for HEVC lossless video compression. Signal Image and Video Process. 9(5), 1055–1066 (2015)
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley-Blackwell, Hoboken (2006)
Gallager, R.G., van Voorhis, D.C.: Optimal source codes for geometrically distributed integer alphabets. IEEE Trans. Inf. Theory 21(2), 228–230 (1975)
Golin, M.J.: A combinatorial approach to Golomb forests. Theor. Comput. Sci. 263(1–2), 283–304 (2001)
Golomb, S.W.: Run-length encodings. IEEE Trans. Inf. Theory 12(3), 399–401 (1966)
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841–850, January 2003
Horibe, Y.: An improved bound for weight-balanced tree. Inf. Control 34(2), 148–151 (1977)
Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. Inst. Electr. Radio Eng. 40(9), 1098–1101 (1952)
Jiang, Z., Pan, W.D., Shen, H.: Universal Golomb-Rice coding parameter estimation using deep belief networks for hyperspectral image compression. IEEE J. Sel. Top. Appl. Earth Obs. Remote. Sens. 11(10), 3830–3840 (2018)
Knuth, D.E.: Combinatorial Algorithms, Part 1, The Art of Computer Programming, vol. 4A. Addison-Wesley, Boston (2011)
Külekci, M.O.: Enhanced variable-length codes: improved compression with efficient random access. In: Proceedings of the Data Compression Conference, pp. 362–371, March 2014
Larsson, N.J.: Integer set compression and statistical modeling. Preprint, February 2014. arXiv:1402.1936 [cs.IT]
Moffat, A., Stuiver, L.: Exploiting clustering in inverted file compression. In: Proceedings of the IEEE Data Compression Conference, pp. 82–91, April 1996
Navarro, G.: Compact Data Structures. Cambridge University Press, Cambridge (2016)
Rice, R.F.: Some practical universal noiseless coding techniques. Technical report, Jet Propulsion Laboratory, California Institute of Technology Pasadena, CA, United States, March 1979
Rissanen, J.: Bounds for weight balanced trees. IBM J. Res. Dev. 17(2), 101–105 (1973)
Rissanen, J.J.: Generalized kraft inequality and arithmetic coding. IBM J. Res. Dev. 20(3), 198–203 (1976)
Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7(3), 166–169 (1964)
Shen, J.P., Lipasti, M.H.: Modern Processor Design. McGraw-Hill, New York (2005)
Tate, J.E.: Preprocessing and Golomb-Rice encoding for lossless compression of phasor angle data. IEEE Trans. Smart Grid 7(2), 718–729 (2016)
Teuhola, J.: Tournament coding of integer sequences. Comput. J. 52(3), 368–377 (2009)
Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, San Francisco (1999)
Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2) (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendix 1: Straightforward Python Implementation
Appendix 2: Branch-Free C Implementation
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Larsson, N.J. (2019). Run-Length Encoding in a Finite Universe. In: Brisaboa, N., Puglisi, S. (eds) String Processing and Information Retrieval. SPIRE 2019. Lecture Notes in Computer Science(), vol 11811. Springer, Cham. https://doi.org/10.1007/978-3-030-32686-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-030-32686-9_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32685-2
Online ISBN: 978-3-030-32686-9
eBook Packages: Computer ScienceComputer Science (R0)