Freecodecamp: Adding Huffman Coding to Data Structures and Algorithms

[Pogayo]

Hello,

I was looking through the data structures projects and I think it would be a good addition to learners to have Huffman coding. Please let me know if this is possible so that I can start working on it.

[RandellDawson]

Can you provide more details about what the challenge Description and Instructions sections would entail?. Once you figure out what the scope of the challenge is, then we can figure out how to best test the user's code.

[Pogayo]

Data Structures and Algorithms Programming
Huffman Coding
Binary Trees are not always used for searching. It can also be used to compress data. Using binary trees to compress data is called the Huffman code. Data compression is important in many situations. An example is sending data over the Internet, where, especially over a dial-up connection, transmission can take a long time.
In this exercise, you will write a program to implement Huffman coding and decoding. It should do the following:
● Accept a text message, possibly of more than one line.
● Create a Huffman tree for this message.
● Create a code table. (This is a table showing the encoded bit sequence for each character in the message)
● Encode the message into binary.
● Decode the message from binary back to text. You can use String variables to store binary numbers as arrangements of the characters 1 and 0. Don’t worry about doing actual bit manipulation unless you really want to. You may present your solution in Java or Python. Your solution should have the following; ● A method that reads a file. It takes the path of the file as an input string and returns the contents of the file as a String.
● A method that writes to a file. It takes the String message to write to file and the pathname of the file as inputs. This method has no return value.
● A method the takes in a String message as an input and returns a frequency table for the input message.
○ What is the time complexity, space complexity and auxiliary space of this method?
● A method that takes in a String message and returns a Huffman Tree as output. This method should make use of the method that creates a frequency table from a String message. When creating your Huffman Tree, if there are more than two characters with the same frequency, extract the two characters that appear earliest in the message making sure the earliest appearing character is extracted first and made the left node of the new node being created. Also, if a character has the same frequency as multiple internal nodes, extract the node with the character first.
○ You may also want to write a method that generates a Huffman tree when given only a frequency table as input. ○ What is the time complexity, space complexity and auxiliary space of this method?
● A method that takes a Huffman tree as input and generates a code table as output. ○ What is the time complexity, space complexity and auxiliary space of this method?
● A method that takes a code table and an original message as input and encodes the message. This method returns a String of the encoded message. ○ What is the time complexity, space complexity and auxiliary space of this method?
● A method that takes a Huffman Tree and an encoded message as input and decodes the message. This method returns a String of the Decoded message. ○ What is the time complexity, space complexity and auxiliary space of this method? Feel free to create any other classes/methods you deem helpful to complete any of the given tasks.
<…tester class….>
Still figuring how to do the instructions and writing the test code and files for this part
You should a write a separate class and call this class Tester. This class should be in a separate file.
➔ This class will be used to test the program you have written, hence it will only have a main function. ➔ In this class, test the following features of your program.

[Pogayo]

@RandellDawson that is a rough sketch of the instruction

For testing, I am thinking we will provide an encoded message and expect them to decode it. If they built their trees well and followed all the instructions, they should be able to decode the original message exactly as it was.

I also didn't see a lot on trees and probably this challenge might require a discussion about trees.
Let me know what you think.

[hilliarj]

@Pogayo Are you going to work on this? Or would we be able to help you with this issue in any way?

[RandellDawson]

After looking at what you are wanting to accomplish here, there may need to be some other challenges before it. The general rule of thumb for any challenge is that it should not take more than 2 minutes to read through and understand what is required of the user. You have laid out many requirements, so you will have to figure out a way to "waterdown" the existing requirements or break this challenge up into 2-3 smaller challenges.

[Pogayo]

@RandellDawson that is a good idea. I think I can break it down into smaller challenges, with the various requirements being a challenge.

[Pogayo]

@hilliarj any help will be appreciated. I think the challenge for me will be to break it down to mini-challenges. If you can help with that it will be appreciated

[hilliarj]

@Pogayo Where do you think these challenges would fit in the Data Structures area of the curriculum? Do you think it should go under "_Javascript Algorithms And Data Structures -> Data Structures_"? I was talking to @chaomt and @Fordco about this, and we think that it could go under "_Coding Interview Prep -> Data Structures_" towards the end after binary search trees.

[Pogayo]

@hilliarj That's a good idea. Then it makes work easier coz the flow will be better

[Pogayo]

@hilliarj and @RandellDawson Can I try a draft now?

[hilliarj]

@pogayo Sounds good to me!

[Pogayo]

Okay... I will share something by the end of Friday for your review

[addv12345]

Hi, I would like contribute as well. @Pogayo can you send me the draft as well so I could review it too?

[moT01]

Any progress here?

[Pogayo]

Hello,

I was waiting for the go-ahead from Randell. I assume I can now start
working on it. Anyone willing to chat with me on this, feel free to hang
out me on [email protected]. Meanwhile, I have been working on doing
graph searches. You can find the link here
https://github.com/Pogayo/Graphs/blob/master/Generic-Search-Algorithm-in-Pseudocode.md
I will appreciate your feedback. It is less than 1 min read.

On Fri, May 3, 2019 at 4:38 PM Tom [e-mail] wrote:

Any progress here?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/freeCodeCamp/freeCodeCamp/issues/35707#issuecomment-489115732,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AJK6LMW22O33733ASB6PQMTPTRE55ANCNFSM4HCK4EOA
.

--

Perez Ogayo

Guest Relations intern| ALU ALIVE Ambassador| Computer Science major

[image: EmailSignature.png]

We're Hiring!

Kigali Heights Business Complex

Kigali| Rwanda

[email protected]

www.alueducation.com

Facebook https://www.facebook.com/alu.education | Twitter
https://twitter.com/ALU_education | Instagram
https://www.instagram.com/alueducation/

[RandellDawson]

@Pogayo Somehow I missed your tag on Apr 3rd. Go ahead and create a first draft and we can take a look at it.

[Pogayo]

Hello all,
I have already started working on it. Please tell me if I am in the right track, so that I can spend the next day making it better. I divided it into two exercises.

https://docs.google.com/document/d/1SwWcIlZhJRM39PqF67Txuu-P3BbhA9H0VV3OLNzNilg/edit?usp=sharing
Huffman Coding
Part 1: Building a Huffman Tree
Binary Trees are not always used for searching. It can also be used to compress data. Using binary trees to compress data is called the Huffman code. Data compression is important in many situations. An example is sending data over the Internet, where, especially over a dial-up connection, transmission can take a long time.
There are mainly two major parts in Huffman Coding:
1) Build a Huffman Tree

The first step will be to build a table of characters and their frequency in the text(Frequency Table). From the frequency table, you can then build a huffman tree.
The following algorithm is followed to build the tree:

1. Create a leaf node for each character and add them to the priority queue.
2. While there is more than one node in the queue:
   a. Remove the two nodes of highest priority (lowest frequency) from the queue
   b. Create a new internal node with these two nodes as children and with
   frequency equal to the sum of the two nodes’ frequencies.
   c. Add the new node to the priority queue.
3. The remaining node is the root node and the tree is complete.
   Source

2) Traverse the Huffman Tree and assign codes to characters.
This implies generating a code table where each character has an associated binary string(the code).

In this exercise and the next one , you will write a program to implement Huffman coding and decoding.

Method Requirements

For now, implement the following methods. The HuffmanNode class has already been implemented for you.

genFreqTable() -A method the takes in a String message as an input and returns a frequency table for the input message
genHuffmanTree(freqTable)- A method that generates and returns a Huffman tree given a frequency table
genCodeTable(huffmanTree)-A method that when given the root of tree, returns a code table
Part 2: Encode and Decode
In this part you will use the code table that you generated from the previous exercise to encode your message. After that you will write another function that will enable you to decode it.

Method Requirements
encode(message, codeTable)- A method that takes a code table and an original message as input and encodes the message. This method returns a String of the encoded message
Decode(encodedMessage, huffManTree)-A method that takes a Huffman Tree and an encoded message as input and decodes the message. This method returns a String of the Decoded message.

[RandellDawson]

@Pogayo Did you mean to close this issue?

[Pogayo]

No , not at all. I think I did so by mistake. Let me correct that.

On Sun, May 5, 2019 at 2:33 AM Randell Dawson [e-mail]
wrote:

@Pogayo https://github.com/Pogayo Did you mean to close this issue?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/freeCodeCamp/freeCodeCamp/issues/35707#issuecomment-489373208,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AJK6LMX7FZBBR45FL7OHSSLPTYMNZANCNFSM4HCK4EOA
.

--

Perez Ogayo

Guest Relations intern| ALU ALIVE Ambassador| Computer Science major

[image: EmailSignature.png]

We're Hiring!

Kigali Heights Business Complex

Kigali| Rwanda

[email protected]

www.alueducation.com

Facebook https://www.facebook.com/alu.education | Twitter
https://twitter.com/ALU_education | Instagram
https://www.instagram.com/alueducation/

[c-logan]

Is this issue still open for contributions/discussion?

[moT01]

Sorry if you didn't get the guidance you needed @Pogayo. I think we would welcome a PR to add this if you're still interested. Since it's been so long, I am going to close this for now. If you are still interested in creating these, feel free to leave a comment and we can reopen this. Thanks and happy coding 🎉