Search for a tool
Huffman Coding

Tool to compress / decompress with Huffman coding. Huffman coding is a data compression algorithm (lossless) which use a binary tree and a variable length code based on probability of appearance.

Results

Huffman Coding -

Tag(s) : Compression

Share
dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Huffman Coding' tool, so feel free to write! Thank you!

Huffman Coding

Huffman Coding Generator

 Characters to encode Alphabetic (A-Z only) Alphanumeric (A-Z0-9 only) Alphanumeric + space All characters
 Output Compressed data in binary 01 Compressed data in hexadecimal The generated huffman tree The generated dictionary The compression ratio

How to encrypt using Huffman Coding cipher?

The Huffman code uses the frequency of appearance of letters in the text, calculate and sort the characters from the most frequent to the least frequent.

Example: The message DCODEMESSAGE contains 3 times the letter E, 2 times the letters D and S, and 1 times the letters A, C, G, M and O.

The Huffman algorithm will create a tree with leaves as the found letters and for value (or weight) their number of occurrences in the message. To create this tree, look for the 2 weakest nodes (smaller weight) and hook them to a new node whose weight is the sum of the 2 nodes. Repeat the process until having only one node, which will become the root (and that will have as weight the total number of letters of the message).

The binary code of each character is then obtained by browsing the tree from the root to the leaves and noting the path (0 or 1) to each node.

Example: DCODEMOI generates a tree where D and the O, present most often, will have a short code. 'D = 00', 'O = 01', 'I = 111', 'M = 110', 'E = 101', 'C = 100', so 00100010010111001111 (20 bits)

How to decrypt Huffman Code cipher?

Decryption of the Huffman code requires knowledge of the matching tree or dictionary (characters <-> binary codes)

To decrypt, browse the tree from root to leaves (usually top to bottom) until you get an existing leaf (or a known value in the dictionary).

Example: Deocde the message 00100010010111001111, search for 0 gives no correspondence, then continue with 00 which is code of the letter D, then 1 (does not exist), then 10 (does not exist), then 100 (code for C), etc.
The plain message is' DCODEMOI'

Why is Huffman used for compression?

By applying the algorithm of the Huffman coding, the most frequent characters (with greater occurrence) are coded with the smaller binary words, thus, the size used to code them is minimal, which increases the compression.

The compression ratio often exceeds 50%

How to recognize Huffman coded text?

The encoded message is in binary format (or in a hexadecimal representation) and must be accompanied by a tree or correspondence table for decryption.

How to decipher Huffman coding without the tree?

By making assumptions about the length of the message and the size of the binary words, it is possible to search for the probable list of words used by Huffman.

It should then be associated with the right letters, which represents a second difficulty for decryption and certainly requires automatic methods.

What are the variants of the Huffman cipher?

There are variants of Huffman when creating the tree / dictionary.

The dictionary can be static: each character / byte has a predefined code and is known or published in advance (so it does not need to be transmitted)

The dictionary can be semi-adaptive: the content is analyzed to calculate the frequency of each character and an optimized tree is used for encoding (it must then be transmitted for decoding). This is the version implemented on dCode

The dictionary can be adaptive: from a known tree (published before and therefore not transmitted) it is modified during compression and optimized as and when. The calculation time is much longer but often offers a better compression ratio.

When Huffman was invented?

It was published in 1952 by David Albert Huffman.

Source code

dCode retains ownership of the online 'Huffman Coding' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any 'Huffman Coding' algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any 'Huffman Coding' function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for 'Huffman Coding' will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!