Constructing Binary Huffman Tree

Hiroyuki Okazaki; Yuichi Futa; Yasunari Shidama

Formalized Mathematics (2013)

  • Volume: 21, Issue: 2, page 133-143
  • ISSN: 1426-2630

Abstract

top
Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.

How to cite

top

Hiroyuki Okazaki, Yuichi Futa, and Yasunari Shidama. "Constructing Binary Huffman Tree." Formalized Mathematics 21.2 (2013): 133-143. <http://eudml.org/doc/267388>.

@article{HiroyukiOkazaki2013,
abstract = {Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.},
author = {Hiroyuki Okazaki, Yuichi Futa, Yasunari Shidama},
journal = {Formalized Mathematics},
keywords = {formalization of Huffman coding tree; source coding},
language = {eng},
number = {2},
pages = {133-143},
title = {Constructing Binary Huffman Tree},
url = {http://eudml.org/doc/267388},
volume = {21},
year = {2013},
}

TY - JOUR
AU - Hiroyuki Okazaki
AU - Yuichi Futa
AU - Yasunari Shidama
TI - Constructing Binary Huffman Tree
JO - Formalized Mathematics
PY - 2013
VL - 21
IS - 2
SP - 133
EP - 143
AB - Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.
LA - eng
KW - formalization of Huffman coding tree; source coding
UR - http://eudml.org/doc/267388
ER -

References

top
  1. [1] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990. 
  2. [2] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990. Zbl06213858
  3. [3] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  4. [4] Grzegorz Bancerek. Introduction to trees. Formalized Mathematics, 1(2):421-427, 1990. 
  5. [5] Grzegorz Bancerek. K¨onig’s lemma. Formalized Mathematics, 2(3):397-402, 1991. 
  6. [6] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Formalized Mathematics, 3(2):195-204, 1992. 
  7. [7] Grzegorz Bancerek. Joining of decorated trees. Formalized Mathematics, 4(1):77-82, 1993. 
  8. [8] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990. 
  9. [9] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on binary trees. Formalized Mathematics, 5(1):9-13, 1996. 
  10. [10] Czesław Bylinski. Finite sequences and tuples of elements of a non-empty sets. Formalized Mathematics, 1(3):529-536, 1990. 
  11. [11] Czesław Bylinski. Functions and their basic properties. Formalized Mathematics, 1(1): 55-65, 1990. 
  12. [12] Czesław Bylinski. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  13. [13] Czesław Bylinski. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  14. [14] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990. 
  15. [15] Krzysztof Hryniewiecki. Recursive definitions. Formalized Mathematics, 1(2):321-328, 1990. 
  16. [16] D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the I.R.E, 1952. Zbl0137.13605
  17. [17] Andrzej Kondracki. Basic properties of rational numbers. Formalized Mathematics, 1(5): 841-845, 1990. 
  18. [18] Andrzej Nedzusiak. σ-fields and probability. Formalized Mathematics, 1(2):401-407, 1990. 
  19. [19] Hiroyuki Okazaki and Yasunari Shidama. Probability on finite set and real-valued random variables. Formalized Mathematics, 17(2):129-136, 2009. doi:10.2478/v10037-009-0014-x.[Crossref] Zbl1281.60006
  20. [20] Andrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1): 115-122, 1990. 
  21. [21] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1 (2):329-334, 1990. 
  22. [22] Andrzej Trybulec. On the sets inhabited by numbers. Formalized Mathematics, 11(4): 341-347, 2003. 
  23. [23] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990. 
  24. [24] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  25. [25] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73-83, 1990. 
  26. [26] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.