Skip to main content

Huffman

Huffman coding

The secret of huffman compression lies in the fact that not all characters are equally common. For instance, in typical English text the letter 'e' is much more common than the letter 'z'. If we could encode the letter 'e' with less number of bits and the least common letter 'z' with more bits, it makes a sense and that is the idea behind huffman coding.

Theseveral steps in huffman coding are:

  • Examine text to be compressed to determine the relative frequencies of individual letters.
  • Assign a binary code to each letter using shorter codes for the more frequent letters.
  • Encode normal text into its compressed form as a string of '0's and '1's.
  • Recover the original text from the compressed.

The complete javascript code for huffman compression is available here.



Enter the string to encode



Decoded text

Comments

Post a Comment

Popular posts from this blog

Backbone.js - An Introduction

Backbone.js is a lightweight JavaScript library that adds structure to your client-side code.  Developers commonly use libraries like Backbone.js to create single-page applications (SPAs).  What is a Single-Page-Application? A single page Web App is a website that attempts to recreate the experience of a native desktop or mobile application. On a Single Page Web App you are less likely to see page refreshes, the browser navigation within the app is often overridden and  there will usually be some offline capabilities. To a user their interaction with a Single Page Web App will be almost identical to how they interact with a full native application. Backbone has many advantages over other js frameworks. Backbone is mature, popular, and has a number  of plugins and extensions available that build upon it. It has been used to create non-trivial applications by companies such as Disqus, Walmart, SoundCloud and LinkedIn. Backbone organizes its whole code under t...
Post a Comment
Read more

Elements of Programming in Scheme

A powerful programming language provides a framework to interpret our ideas of processes. It generally combines small procedures to complex ones. Usually there are three steps to accomplish this. primitive expressions , which represent the simplest entities the language is concerned with, means of combination , by which compound elements are built from simpler ones, and means of abstraction , by which compound elements can be named and manipulated as units. Some very basic ideas in manipulating with the data are given below. Expressions   A very simple expression is a number. Simple expressions are combined to form complex ones. For example:                   (+ 2  3  4) is an expression where + is the operation and 2,3,4 are the oparents. The expression can be made more complex by combining simple expressions as given below:              ...
Post a Comment
Read more

Abstraction Using Higher Order Procedures

Procedures are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers. Yet even in numerical processing we will be severely limited in our ability to create abstractions if we are restricted to procedures whose parameters must be numbers. Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures as arguments Procedures are often used as the arguments of an another procedure. This provides a higher level of abstraction in programming. For example consider a procedure to find out the sum of squares of numbers between a range. The procedures inc and square are used as the arguments of the procedure sum, which is generalised as follows.                 (define (inc...
Post a Comment
Read more