473,325 Members | 2,872 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Huffman Encoding.

Hiya guys.
im after a bit of guidance to be honest

My task:
Create a program that generates huffman codewords for a 16 symbol alphabet, the input should be the probabilities of each symbol occurring.
Im gonna use 6 for ease of programming for now

Im unsure where to go... Ive created a basic "take user input - assign to an array" program.(userinput[])

Heres my thoughts.. copy userinput[] to huffmanarray[0,i] using a for loop, and bubble sort it
then take huffmanarray[0,6] add [0,5] (result)
then copy huffmanarray[0,i-2] to huffmanarray[1,i]
The put (result) into huffmanarray[1,5] and bubblesort again

rinse and repeat
This will create a huffman coding table in the array
Thats the only way i can think of doing it, but it seems terribly inefficient.

Ive seen some object orientated approaches programming the trees, and nodes, but i dont really understand how they do it. And i don't really have any experience with graphical programming (applets n suchlike)

(It is uni work, but as i say, I'm more after guidance as to how it can be done, id rather understand it and program it myself, rather that rip off someone else work)
any help would be greatly appreciated
Mar 29 '08 #1
1 2172
JosAH
11,448 Expert 8TB
Never ever sort anything yourself for Huffman encoding; use a SortedSet instead.
The set should store nodes of the Huffman tree and every node in this tree can
be ordered according to its frequency. If two frequencies are equal design a small
artificial ordering to make the two nodes different.

For the tree building just do this: get the two smallest nodes from the set, remove
them from the set, combine them and add them back again to the set. Do this
until there are less than two elements in the set.

kind regards,

Jos
Mar 29 '08 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

3
by: dot | last post by:
Hi all, I have written a Python huffman Encoding Module, for my own amusement. I thought it might be educational/entertaining for other people, so I've put it on my website and wrote about it a...
8
by: dirgesh | last post by:
I am having a hard time making a Program in C/C++ that uses the Huffman Compression to compress a file. I have a file "Hello World" That i need to compress. can someone please give me an...
8
by: james | last post by:
I have ran into a little snag on an old database application I am converting. Out of 63 tables(all seperate files) , two of them are compressed using Huffman Compression. I have been searching all...
15
by: aarklon | last post by:
Hi all, this is the program which I saw in my colleagues book. the program was run on turbo C++ 3.0 compiler /*beginning of header file huff.h*/ #ifndef _HUFF_H_ #define _HUFF_H_
4
by: A_StClaire_ | last post by:
hi all, I'm trying to implement Huffman coding on letters of a string. I've written functions to define the initial leaf nodes (letters and their frequencies) and to sort them. I've also put...
3
by: Udhay | last post by:
Sir, I am udhay. I am a student and i am working on Audio compression for my exam. I want to know how does the compression take place in audio?? Can anyone suggest a link for the novice to...
11
by: KWSW | last post by:
The other thread got too long so decided to start a new one. Got my huffman tree working and am now moving onto encoding and decoding my given text file. My idea now is to print out all the leaf...
5
by: recordlovelife | last post by:
So i have written a code to encode a string of a select amount of letters into huffman code. #include <iostream> #include <string> using namespace std; string Huffman(char letter);...
0
by: coucchy | last post by:
Hello everyone, i'm writing a C program that will read a text file and then encode the characters using huffman algorithm. So far i've read the files, built a tree, and now I'm building the strings...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.