search

Tirent-user / Easy-DSA-and-Algo

This is a public repo, Whoever willing to explain DSA and Algo. topic in easier way can contribute to this repository
https://github.com/Aka-pider34/AlgoEverwhere
MIT License
6 stars 11 forks source link

Greedy Algorithm : Huffman Coding in C++ #29

Closed Ps1231 closed 1 year ago

Ps1231 commented 1 year ago

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are the best fit for Greedy. For example consider the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item. One of the Standard Greedy Algorithms is the Huffman Coding Algorithm. The Huffman Coding Algorithm is a lossless data compression mechanism. It is also known as data compression encoding. It is widely used in image (JPEG or JPG) compression. We know that each character is a sequence of 0's and 1's and stores using 8-bits. The mechanism is called fixed-length encoding because each character uses the same number of fixed-bit storage. It is possible to reduce the amount of space required to store a character by using variable-length encoding. In this mechanism, we exploit some characters that occur more frequently in comparison to other characters. In this encoding technique, we can represent the same piece of text or string by reducing the number of bits.

Ps1231 commented 1 year ago

Hey @Tirent-user please review my PR and suggest changes if any.