Huffman coding: Difference between revisions

Revision as of 11:10, 13 June 2024

Revision as of 11:51, 13 June 2024

Line 1:

{{Short description|Technique to compress data}}{{Use dmy dates|date=May 2019|cs1-dates=y}}

[[Image:Huffman tree 2.svg|thumb|Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". Encoding the sentence with this code requires 135 (or 147) bits, as opposed to 288 (or 180) bits if 36 characters of 8 (or 5) bits were used. (This assumes that the code tree structure is known to the decoder and thus does not need to be counted as part of the transmitted information.) The frequencies and codes of each character are shown in the accompanying table.]]

{| class="wikitable sortable"

!Char!!Freq!!Code

|-

|A |18|

|-

|B |10|

|-

|C |2|

|-

|D |2|

|-

|E |3|

|-

|F |1|

|-

|G |5|

|-

|H |4|<ref><ref></ref></ref>

|}]]

In [[computer science]] and [[information theory]], a '''Huffman code''' is a particular type of optimal [[prefix code]] that is commonly used for [[lossless data compression]]. The process of finding or using such a code is '''Huffman coding''', an algorithm developed by [[David A. Huffman]] while he was a [[Doctor of Science|Sc.D.]] student at [[Massachusetts Institute of Technology|MIT]], and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".<ref>{{Cite journal | last1 = Huffman | first1 = D. |author-link1=David A. Huffman| title = A Method for the Construction of Minimum-Redundancy Codes | doi = 10.1109/JRPROC.1952.273898 | journal = [[Proceedings of the IRE]]| volume = 40 | issue = 9 | pages = 1098–1101 | year = 1952 | url = http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf}}</ref>