Huffman coding | Greedy Algorithm

Steps for the Huffman coding scheme are mentioned below:

  1. Steps for creating Huffman tree algorithm with given input characters and frequencies
  • Step 1- Take two characters with the lowest frequency i.e., newline (\n) and S, and create two leaf nodes for \n and S.
  • Step 2- Their sum of frequencies will be stored in a parent node. So, 4 (sum of \n frequency 1 and S char 3) will be stored in the parent node.
  • Step 3- Taking the next lowest frequency, which is T with frequency 4 will get added beneath and the next parent node will again be the sum of T frequency (4) and the previous parent node (4), making 8.
  • Step 4- Repeat step 3, until we get the highest parent node value compared to other frequencies.
  • Step 5- After the parent node with value 18, create a new subtree following the step-1 and step-2.
  • Step 7- Its frequency will again add to its next parent node.
  • Fill the value of left traversal with value 0 and right traversal with value 1.
  • Traverse down through the character from the main node.

Advantages of Huffman Coding

  • It saves a lot of storage space
  • Generates shorter binary codes for encoding
  • Codes generated are prefix-free

Disadvantages of Huffman Coding

  • The lossless data encoding technique, therefore, is suitable for only encoding text and programming files.
  • A considerably slower process.
  • Differences in binary length codes make it difficult for decoding software to detect whether the data is corrupted or not.

--

--

--

Software Engineering Student

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Making use of indexes in Postgres

Making use of indexes in Postgres

Guide to ElasticSearch Mappings

SDMC unveils brand-new 4K Android TV box powered by Amlogic S905Y4

🕵🏻‍♂️ New Airdrop: Pets Of Elon (New Round)

You don’t need a f****** app

Changes with Certified Kubernetes Administrator (CKA) Certification 2020

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Shruti Sinha

Shruti Sinha

Software Engineering Student

More from Medium

Minimum Insertions to Balance a Parentheses String

Let’s talk about Linked Lists · Data Structures #Part 1/3

A journey into sorting algorithms — Part I

Photo by Tom Swinnen from Pexels

Mastering Recursion For Beginners-(Part 2)