6 Replies - 732 Views - Last Post: 17 August 2016 - 02:38 PM

#1 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 18-June 16

Confused about the uses of Huffman Coding

Posted 16 August 2016 - 08:22 PM

I know that it is used for compression and you need to construct a tree. But I don't understand where the compression is used. From lectures and what I've found by googling, it seems everything stops after the tree is constructed with binary values assigned.

But when do you compress? Or is the binary value the compression?
Is This A Good Question/Topic? 0
  • +

Replies To: Confused about the uses of Huffman Coding

#2 timdrivendev  Icon User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 21
  • Joined: 27-October 15

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 03:05 AM

The binary value is the compression.

If you compare the space required to represent the original data, and the encoded data, you'll find that the encoded data requires less space. Hence, the original data has been compressed.
Was This Post Helpful? 0
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 08:24 AM

gzip uses Huffman encoding: https://en.wikipedia.org/wiki/Gzip


the trick is to write bits rather than bytes. By encoding your data as a string of bits you get compression.
Was This Post Helpful? 0
  • +
  • -

#4 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 18-June 16

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 09:25 AM

So using gzip as an example. Let's say I write some code to take an input file (e.g text file), do I read the letters in the file and construct the tree with those letters? Once the tree is complete, what do I output as the compressed file?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 01:23 PM

The tree gives you a function to encode your string. Each letter maps to a binary string. You construct the binary string by starting at the root and searching for your letter. You append a 0 for visiting the left child and a 1 for visiting the right child. The path to the desired letter is the corresponding encoding of that letter.

So now given your input string, you encode each letter using the above procedure. To decode a binary string, you simply start at the root and follow the prescribed path (0 for left, 1 for right) until you hit a leaf. That leaf is the corresponding letter. You then start at the root with the next available binary digit.

The Huffman Coding Algorithm is really for prefix-free encoding of letters. That is, any two binary strings will be uniquely determined for the given Huffman tree. There is no ambiguity if you have an 'a' vs. 'e' for example.
Was This Post Helpful? 1
  • +
  • -

#6 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 18-June 16

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 02:19 PM

View Postmacosxnerd101, on 17 August 2016 - 01:23 PM, said:

The tree gives you a function to encode your string. Each letter maps to a binary string. You construct the binary string by starting at the root and searching for your letter. You append a 0 for visiting the left child and a 1 for visiting the right child. The path to the desired letter is the corresponding encoding of that letter.

So now given your input string, you encode each letter using the above procedure. To decode a binary string, you simply start at the root and follow the prescribed path (0 for left, 1 for right) until you hit a leaf. That leaf is the corresponding letter. You then start at the root with the next available binary digit.

The Huffman Coding Algorithm is really for prefix-free encoding of letters. That is, any two binary strings will be uniquely determined for the given Huffman tree. There is no ambiguity if you have an 'a' vs. 'e' for example.

I completely understand every you said. What I don't understand is what happens after the tree is constructed.

Like gzip for example. It compresses a file and gives you a zipped file. So that's my main question, do I output the binary values into a file after? What kind of file do I output etc.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Confused about the uses of Huffman Coding

Posted 17 August 2016 - 02:38 PM

You would need to output an encoding of the tree and your encoded word so that the original string can be recovered.

Quote

What kind of file do I output etc.

A text file works. The Huffman algorithm doesn't specify a file type. This is an abstract algorithm, and details about what to do with the output are left for those implementing the algorithm.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1