Skip to main content
Erschienen in: Theory of Computing Systems 3/2021

25.06.2020

Forward Looking Huffman Coding

verfasst von: Shmuel T. Klein, Shoham Saadia, Dana Shapira

Erschienen in: Theory of Computing Systems | Ausgabe 3/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
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].
 
Literatur
1.
Zurück zum Zitat Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. IEEE Data Compression Conference DCC–92, pp 279–288 (1992) Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. IEEE Data Compression Conference DCC–92, pp 279–288 (1992)
2.
Zurück zum Zitat Baruch, G., Klein, S.T., Shapira, D.: A space efficient direct access data structure. Journal of Discrete Algorithms 43, 26–37 (2017)MathSciNetCrossRef Baruch, G., Klein, S.T., Shapira, D.: A space efficient direct access data structure. Journal of Discrete Algorithms 43, 26–37 (2017)MathSciNetCrossRef
3.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Cleary, J., Witten, I.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396–402 (1984)CrossRef Cleary, J., Witten, I.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396–402 (1984)CrossRef
5.
Zurück zum Zitat Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194–203 (1975)MathSciNetCrossRef Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194–203 (1975)MathSciNetCrossRef
6.
Zurück zum Zitat Faller, N.: An adaptive system for data compression. In: Record of the 7th Asilomar Conference on Circuits, Systems and Computers, pp 593–597 (1973) 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.
Zurück zum Zitat Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inf. Theory 30(4), 687–693 (1984)MathSciNetCrossRef Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inf. Theory 30(4), 687–693 (1984)MathSciNetCrossRef
9.
Zurück zum Zitat Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40(9), 1098–1101 (1952)CrossRef Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40(9), 1098–1101 (1952)CrossRef
10.
Zurück zum Zitat Jacobson, G.: Space efficient static trees and graphs. In: Proceedings of FOCS, pp 549–554 (1989) Jacobson, G.: Space efficient static trees and graphs. In: Proceedings of FOCS, pp 549–554 (1989)
11.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Klein, S.T., Shapira, D.: Compressed pattern matching in JPEG images. Int. J. Found Comput. Sci. 17(6), 1297–1306 (2006)MathSciNetCrossRef Klein, S.T., Shapira, D.: Compressed pattern matching in JPEG images. Int. J. Found Comput. Sci. 17(6), 1297–1306 (2006)MathSciNetCrossRef
16.
Zurück zum Zitat Klein, S.T., Shapira, D.: On improving Tunstall codes. Inf. Process. Manage. 47(5), 777–785 (2011)CrossRef Klein, S.T., Shapira, D.: On improving Tunstall codes. Inf. Process. Manage. 47(5), 777–785 (2011)CrossRef
17.
18.
Zurück zum Zitat Klein, S.T., Shapira, D.: Random access to Fibonacci encoded files. Discret. Appl. Math. 212, 115–128 (2016)MathSciNetCrossRef Klein, S.T., Shapira, D.: Random access to Fibonacci encoded files. Discret. Appl. Math. 212, 115–128 (2016)MathSciNetCrossRef
19.
Zurück zum Zitat 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) 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)
21.
Zurück zum Zitat Moffat, A.: Word-based compression. Softw. Pract. Exper. 19(2), 185–198 (1989)CrossRef Moffat, A.: Word-based compression. Softw. Pract. Exper. 19(2), 185–198 (1989)CrossRef
22.
Zurück zum Zitat Navarro, G.: Compact Data Structures: a Practical Approach. Cambridge University Press, Cambridge (2016)CrossRef Navarro, G.: Compact Data Structures: a Practical Approach. Cambridge University Press, Cambridge (2016)CrossRef
23.
Zurück zum Zitat Nelson, M., Gailly, J.-L.: The Data Compression Book. 2nd edn. M & T Books (1996) Nelson, M., Gailly, J.-L.: The Data Compression Book. 2nd edn. M & T Books (1996)
24.
Zurück zum Zitat 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 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.
Zurück zum Zitat Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7, 166–169 (1964)CrossRef Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7, 166–169 (1964)CrossRef
26.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Storer, J.A., Szymanski, T.G.: Data compression via textural substitution. J. ACM 29(4), 928–951 (1982)CrossRef Storer, J.A., Szymanski, T.G.: Data compression via textural substitution. J. ACM 29(4), 928–951 (1982)CrossRef
29.
Zurück zum Zitat Tunstall, B.P.: Synthesis of noiseless compression codes. Georgia Institute of Technology (1967) Tunstall, B.P.: Synthesis of noiseless compression codes. Georgia Institute of Technology (1967)
30.
Zurück zum Zitat 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) 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)
32.
Zurück zum Zitat 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 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.
Zurück zum Zitat Witten, I.H., Neal, Radford M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30(6), 520–540 (1987)CrossRef Witten, I.H., Neal, Radford M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30(6), 520–540 (1987)CrossRef
34.
Zurück zum Zitat Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 6 (2006)CrossRef Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 6 (2006)CrossRef
Metadaten
Titel
Forward Looking Huffman Coding
verfasst von
Shmuel T. Klein
Shoham Saadia
Dana Shapira
Publikationsdatum
25.06.2020
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 3/2021
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-020-09992-7

Weitere Artikel der Ausgabe 3/2021

Theory of Computing Systems 3/2021 Zur Ausgabe

OriginalPaper

Belga B-Trees