Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 3/2021

25-06-2020

Forward Looking Huffman Coding

Authors: Shmuel T. Klein, Shoham Saadia, Dana Shapira

Published in: Theory of Computing Systems | Issue 3/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Huffman coding is known to be optimal, yet its dynamic version may yield smaller compressed files. The best known bound is that the number of bits used by dynamic Huffman coding in order to encode a message of n characters is at most larger by n bits than the size of the file required by static Huffman coding. In particular, dynamic Huffman coding can also generate a larger encoded file than the static variant, though in practice the file might sometimes be smaller. We propose here a new variant of Huffman encoding, that provably always performs better than static Huffman coding by at least m − 1 bits, where m denotes the size of the alphabet, and may be better than the standard dynamic Huffman coding for certain files. The algorithm is based on reversing the direction for the references of the encoded elements, from pointing backwards into the past to looking forward into the future.
previous article Unpopularity Factor in the Marriage and Roommates Problems
next article On Tseitin Formulas, Read-Once Branching Programs and Treewidth

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
The numbers differ slightly from those in [12], not only because of the different representation but also since dynamic Huffman coding has been implemented here exactly as suggested by Vitter [31], while a more optimized variant of Nelson [23], which repeatedly performs rescaling of the frequencies, has been used in [12].
 
Literature
1.
Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. IEEE Data Compression Conference DCC–92, pp 279–288 (1992)
2.
Baruch, G., Klein, S.T., Shapira, D.: A space efficient direct access data structure. Journal of Discrete Algorithms 43, 26–37 (2017)MathSciNetCrossRef
3.
Baruch, G., Klein, S.T., Shapira, D.: Applying compression to hierarchical clustering. In: Similarity Search and Applications - 11th International Conference, SISAP 2018, Lima, Peru, October 7-9, 2018, Proceedings, pp 151–162 (2018)
4.
Cleary, J., Witten, I.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396–402 (1984)CrossRef
5.
Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194–203 (1975)MathSciNetCrossRef
6.
Faller, N.: An adaptive system for data compression. In: Record of the 7th Asilomar Conference on Circuits, Systems and Computers, pp 593–597 (1973)
7.
Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inf. Theory 30(4), 687–693 (1984)MathSciNetCrossRef
8.
9.
Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40(9), 1098–1101 (1952)CrossRef
10.
Jacobson, G.: Space efficient static trees and graphs. In: Proceedings of FOCS, pp 549–554 (1989)
11.
Klein, S.T., Opalinsky, E., Shapira, D.: Selective dynamic compression. In: Proceedings of the Prague Stringology Conference 2019, Czech Technical University in Prague, Czech Republic (2019)
12.
Klein, S.T., Saadia, S., Shapira, D.: Forward looking Huffman coding. In: The 14th Computer Science Symposium in Russia, CSR, Novosibirsk, Russia, July 1-5, LNCS 11532, pp 203–214 (2019)
13.
Klein, S.T., Shapira, D.: A new compression method for compressed matching. In: Data Compression Conference, DCC Snowbird, Utah, USA, March 28-30, 2000, pp 400–409 (2000)
14.
Klein, S.T., Shapira, D.: Compressed pattern matching in JPEG images. Int. J. Found Comput. Sci. 17(6), 1297–1306 (2006)MathSciNetCrossRef
15.
16.
Klein, S.T., Shapira, D.: On improving Tunstall codes. Inf. Process. Manage. 47(5), 777–785 (2011)CrossRef
17.
18.
19.
Klein, S.T., Shapira, D.: Integrated encryption in dynamic arithmetic compression. In: Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings, pp 143–154 (2017)
20.
21.
Moffat, A.: Word-based compression. Softw. Pract. Exper. 19(2), 185–198 (1989)CrossRef
22.
Navarro, G.: Compact Data Structures: a Practical Approach. Cambridge University Press, Cambridge (2016)CrossRef
23.
Nelson, M., Gailly, J.-L.: The Data Compression Book. 2nd edn. M & T Books (1996)
24.
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)MathSciNetCrossRef
25.
Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7, 166–169 (1964)CrossRef
26.
Shapira, D., Daptardar, A.H.: Adapting the knuth-morris-pratt algorithm for pattern matching in huffman encoded texts. Inf. Process. Manage. 42(2), 429–439 (2006)CrossRef
27.
Singh, A., Gilhotra, R.: Data security using private key encryption system based on arithmetic coding. International Journal of Network Security & Its Applications (IJNSA) 3(3), 58–67 (2011)CrossRef
28.
Storer, J.A., Szymanski, T.G.: Data compression via textural substitution. J. ACM 29(4), 928–951 (1982)CrossRef
29.
Tunstall, B.P.: Synthesis of noiseless compression codes. Georgia Institute of Technology (1967)
30.
Véronis, J., Langlais, P.: Evaluation of parallel text alignment systems: the arcade project. In: Véronis, J. (ed.) Parallel Text Processing. Kluwer Academic Publishers, Dordrecht, Chapter 19, pp. 369–388 (2000)
31.
32.
Wen, J., Kim, H., Villasenor, J.: Binary arithmetic coding with key based interval splitting. IEEE Trans. on Signal Processing Letters 13(2), 69–72 (2006)CrossRef
33.
Witten, I.H., Neal, Radford M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30(6), 520–540 (1987)CrossRef
34.
Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 6 (2006)CrossRef
Metadata
Title
Forward Looking Huffman Coding
Authors
Shmuel T. Klein
Shoham Saadia
Dana Shapira
Publication date
25-06-2020
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 3/2021
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-020-09992-7

Other articles of this Issue 3/2021

Theory of Computing Systems 3/2021 Go to the issue

EditorialNotes

Special Issue on Computer Science Symposium in Russia (2019)

OriginalPaper

The Non-hardness of Approximating Circuit Size

OriginalPaper

On Decidability of Theories of Regular Languages

OriginalPaper

Belga B-Trees

OriginalPaper

Parameterized Complexity of Conflict-Free Set Cover

OriginalPaper

On Tseitin Formulas, Read-Once Branching Programs and Treewidth

Premium Partner

    Image Credits