|
Hey guys-girls,I have been looking to find a good huffman tree example but i cant seem to find a code example of one that is in a language i know (C#, i can kinda desipher C/C++, they are all in java that i have found). I have no problem understanding the logic of the huffman tree algorithm but my problem lies in visualizing how to code it into C#. i want to write it in C# to see if i can do it. does anyone know of a good example or have any of you coded on before in a high level object language. I can kinda do it...i just dont know how to build the actuall tree portion of the Algorithm, any examples on that would help too. Thanks alot.
Jesse M.
The Code Project Is Your Friend...
|
|
|
|
|
Hi, I know this probably wont help, but have you tried using the Java conversion assistant?
|
|
|
|
|
I'm kind of puzzled: java and C# are very similar. If you've found a java example of creating a huffman tree than it should be easy to convert it into C#.
To build a huffman tree you'll need two basic classes: the tree and a priority queue. (You need the latter to easily get the nodes or partial trees with the smallest weights every time.)
A huffman tree consists of node objects. Each node object will have a left child node and a right child node, and will have a weight value (the weight being the count of characters in the node and its children). You'll also store the byte value in the node.
So, first do it without regard to performance. Create an array of nodes, one for each possible byte in the input stream (i.e. 256 of them). Read through the input stream, for each byte you update the weight in the relevant node object.
Push all the nodes with non-zero weights in the priority queue.
Pop the top two off. Create a new parent node with weight equal to the sum of the two nodes' weights. The children of this parent are the two nodes popped off.
Push the parent node into the priority queue.
Perform the previous two steps until there is only one node in the queue. This is the huffman tree.
Cheers, Julian
Program Manager, C#
This posting is provided "AS IS" with no warranties, and confers no rights.
|
|
|
|
|
i think i can visualize writing the code for it.but how do i setup the decompressor ?
Jesse Murcray.
The Code Project Is Your Friend...
|
|
|
|
|
It depends on where the decompressor gets its input from.
For instance, if your Huffman Tree compressed a clear text file into a compressed file, then the decompressor would get the compressed file to generate the clear file. Right?
If so, remember that the compressed file should include in its header a serialized version of the HuffmanTree itself. Thus, the decompressor would first read this "symbol table" in the compressed file, and build the corresponding HuffmanTree from it (i.e. de-serializing the HuffmanTree).
Once that is done, the decompressor should just read the rest of the compressed file, get the corresponding character from the HuffmanTree, and place this character in the output file.
HTH,
FOR
|
|
|
|
|
So it's more than just building the tree, then?
Building the tree is the standard well-understood algorithm. Using the tree is where things diverge and get really tough. To compress using a huffman tree, you have to remember to pass an encoding of the tree to the decompressor, followed of course by the compressed data.
There are various ways to encode the tree: pass along 256 int values, each containing the calculated weights. The decomnpressor can then use these in exactly the same way as you used to build the tree in the first place. Unfortunately 256 ints would be 1K, which is a lot to add to a compressed file.
You can analyze the weights and compress out zero values. For example, compressing a text file would result in a lot of byte values (characters, if you like) being unused and hence having a zero weight. You could devise an RLE (run length encoding) scheme that replaces runs of zero bytes in the weights table.
You could use a variable length encoding. Say you analyze the weights as you write them out. You output 2 bits before every wieght. If the bits are 00, the next weight will be 8 bits long. If the bits are 01, the next weight will be 16 bits long. If 10, the next weight will be 24 bits. If 11, a full 32 bits.
And so on. You could of course try out all these possibilities and pass along the smallest result (along with an indicator to tell the decompressor which variety was used).
Compressing and decompressing the data is the standard algorithm again. You would need to write a class that was a bit stream (to get the really nasty stuff out of the way), otherwise you're going to be writing a lot of bit manipulation code in the middle of your compression and decompression code.
Cheers, Julian
Program Manager, C#
This posting is provided "AS IS" with no warranties, and confers no rights.
|
|
|
|
|
jtmtv18 wrote:
i just dont know how to build the actuall tree portion of the Algorithm
I would develope the tree as a Huffman Tree class all by itself.
It is basically a Binary tree:
<br />
public class HuffmanTree<br />
{<br />
private HuffmanNode node = null;<br />
private HuffmanTree rightChild = null;<br />
private HuffmanTree leftChild = null;<br />
}<br />
with the Node being
<br />
public class HuffmanNode<br />
{<br />
private char c;
private int f;
}<br />
You can implement the joining of two trees (when you are building the Huffman tree
based on the charactrs' frequencies) in the HuffmanTree class, or you can implement it
outside the HuffmanTree class. In this second case, the HuffmanTree becomes a simple
binary tree containing HuffmanNodes (you could generalize this and make your own
BinaryTree class containing Objects instead of Huffmannodes).
HTH,
FOR
PS: If I was at home, I'd pass along my C++ HuffmanTree code,
but -alas- I am working 
|
|
|
|
|
Thanks alot for your time. ill have to work on it later. I stayed up all night last night and got the tree down to a single node i.e they are all connected.
One question though, since each new "tree" contains the weight of the previous 2 children combined, should the weight at the top of my tree be equal to the length of the string?
Jesse M
The Code Project Is Your Friend...
|
|
|
|
|
That's right. The weight (or frequency) for leaf nodes is merely the count of that particular character at the leaf in the source file; the weight for internal nodes, which are parents, is the count of all the characters in the children nodes.
Cheers, Julian
Program Manager, C#
This posting is provided "AS IS" with no warranties, and confers no rights.
|
|
|
|
|
jtmtv18 wrote:
should the weight at the top of my tree be equal to the length of the string?
After the whole tree is built, yes, the weight of the root will be equal to the length of the text to be compressed.
HTH,
FOR
|
|
|
|
|
Hello,
I am working in a multithreaded application and I need to find the best solution to handle this:
I have several threads running in parallel doing very similar things against different objects.
My problem is that some objects may sometimes be too long to wait for or may have disappear (this is a network application).
I would like to be able to make a thread wait for the object no longer than a certain time (30 seconds for example) after calling it. I want to sleep my thread for this period of time and let the others threads work.
My concern is that a thread.sleep(30000) is not right because time is taken also be the others threads. A thread.sleep(30000) doesn't mean this thread will wait 30 seconds of its running time, but 30 seconds of real shared time. The reality is that the thread will maybe run only for 10 seconds in this 30 seconds.
My question is: what kind of solution exists to effectively make a thread wait for 30 seconds of its running time ?
Thanks,
R. LOPES
Just programmer.
|
|
|
|
|
You could use something like this.
I should allow all threads to run apox 30 seconds then abort them
if they have not completed.
class Program
{
private static AutoResetEvent e = new AutoResetEvent(false);
//No delay
public static void DoWork1()
{
Console.WriteLine("DoWork1 Completed");
e.Set();
}
//Long but completes
public static void DoWork2()
{
Thread.Sleep(new TimeSpan(0, 0, 25));
Console.WriteLine("DoWork2 Completed");
e.Set();
}
//runs too long
public static void DoWork3()
{
Thread.Sleep(new TimeSpan(0, 0, 60));
Console.WriteLine("DoWork3 Completed");
e.Set();
}
static void Main(string[] args)
{
//Create array of worker threads
Thread[] workers = new Thread[3];
(workers[0] = new Thread(new ThreadStart(DoWork1))).Start();
(workers[1] = new Thread(new ThreadStart(DoWork2))).Start();
(workers[2] = new Thread(new ThreadStart(DoWork3))).Start();
DateTime abortTime = DateTime.Now.AddSeconds(30);
//Wait until timout expires or all all thread are
//completed.
while (DateTime.Now < abortTime)
{
//Waits for 10 seconds on until any thread completes
e.WaitOne(new TimeSpan(0, 0, 10));
int running = 0;
foreach (Thread t in workers)
{
if (t.ThreadState != System.Threading.ThreadState.Stopped)
{
running++;
}
}
if (running == 0)
{
break;
}
else
{
Console.WriteLine("Running threads {0}", running);
}
}
//Kill off the threads that have not stopped
foreach (Thread t in workers)
{
try
{
t.Abort();
}
catch
{
Console.WriteLine("Aborted");
}
}
}
}
|
|
|
|
|
I use the MethodInfo Invoke() Method. The Invoked Method is a drawing routine.
Is it right that the MethodInfo Invoke() Method is extremly slow?
|
|
|
|
|
Compared to a direct call, yes, it's very slow.
What are you trying to do, and can you do it with an interface? Making calls through interfaces is fast.
|
|
|
|
|
I thought I had an "extremly cunning plan" but hope you can tell me a better solution:
I'm programming a little game with a lot of UserControls. These UserControls are filled with Data. But I don't like to pass DataAccess references to all of these Controls, so I thought I do it like in C++. MFC C++ Prgs are splitted in UI Views and Documents. Each View can have a document. From this document it's very simple to update the views
(GetDocument().UpdateView(Name)) with new data.
In this scenario I wouldn't have to pass references to the DataSet; I just have to programm a document class which handles adding Document Items (Controls, which are "listening" to changes of the document) and the Controls Update Methods. I made it like this:
object array for the document items
String array for the Update Method Name of the Control
DocumentType, so I can Update only specific controls.
MyDocument.AddDocumentItem(this.AreaControl1, "AreaCtrlUpdate", DocumentTypes.AreaControl)
The Document has a DataSet and properties.
So when the documents data changed with the set method of a property this will Update my Document Items. To Invoke a Method of a object I needed MethodInfo.Invoke() Method. Each DocumentItem have to implement a method like CtrlUpdate(Document pDoc). I add as a passing parameter of the CtrlUpdate method the Document itsself.
What I found very good was first that Data is only stored at one place (in the document) and there is even no need to store IDs in the UserControls. Second there's no need to pass DataSet or DataAccess Object References because the DataSet is passed with the Document to the Controls Update Method. In the document I fix which Controls to Update if a property or the dataset changed. That's good because I can fix which Controls to update at only one place, in the document and there's no need that a control has object references to other controls which have to actualisize when the data was changed by the control. I just set the new property in the document and this will cause the Update Method of the other Controls.
I made a mistake and so I meant that MethodInfo.Invoke() is very slow (Seconds to Invoke).
So what do you mean with calling Methods through an interface? Is there a better solution for this scenario? Could you give me an example?
I think about to use databinding with these UserControls but I couldn't find examples how to set a datasource, datamember for a UserControl. Do you know how to set datasource of usercontrols?
Thank you!
Stefan
|
|
|
|
|
Here's what I suggest:
Define an interface:
interface IDocumentItem
{
void CtrlUpdate(Document pDoc);
}
and then implement it in each of the DocumentItem classes. Then, when you want to do the update, you can cast the DocumentItem to an IDocumentItem, and then call CtrlUpdate() through that reference. That will be fast fast.
Does that make sense?
|
|
|
|
|
This does really make sense! Yes that's what I searched. The problem was always that a casted object "looses" the classes methods...So now I see...
Thank you very much!
Stefan
|
|
|
|
|
STW wrote:
I use the MethodInfo Invoke() Method. The Invoked Method is a drawing routine.
Is it right that the MethodInfo Invoke() Method is extremly slow?
Someone once said that if you need to ask how big is the cost of Reflection, you can't afford it.
But there are much faster alternatives, like interfaces or delegates.
Acting as a substitute for God, he becomes a dispenser of justice. - Alexandre Dumas
|
|
|
|
|
I explained my scenario to Eric Gunnerson. Hope you could help me to find a faster solution with interfaces.
Thank you!
Stefan
|
|
|
|
|
Can i access a function from a file which is not in an active project in a workspace????
Meaning, if i have 11 projects in a workspace and i want to access a function from a project that is currently not set as active one, can i do that?
|
|
|
|
|
If it is a DLL, yes, just add a reference in your current project. When the window pops up, select the .NET tab and "Browse" for the dll.
Rocky Moore <><
|
|
|
|
|
Hello,
I'm trying to bring to top an application. I followed several examples that I've founded but it doesn't work.
I have the instance of my application registered in the computer and I have access to it via Remoting. I've got a method (ShowMyWindow) that I want to call to show the main window of my application:
public void ShowMyWindow()
{
if (IsIconic(hWnd))
{
ShowWindowAsync(hWnd, 3);
}
SetForegroundWindow(hWnd);
}
Now, for example, I've got a instance of my application running in my computer and I try to execute another one from the console. I obtain the already running instance and execute the ShowMyWindow method. The problem is that the result of this is I've got the console window on top and the icon of my application flashing in the task bar (I want to show it a the top of my screen!!!!! ) Instead, if my application is minimized, it works.... Any suggestion???
Thanks,
Iván Fernández
|
|
|
|
|
Did you try BringWindowToTop instead of SetForegroundWindow
"...hasn't really been well accepted ... as the ratings tell us so far " - Nishant S
|
|
|
|
|
Yes, I tried but it doesn't work anyway...
Iván Fernández
|
|
|
|
|
It's strange, because "The BringWindowToTop function brings the specified window to the top of the Z order"
"...hasn't really been well accepted ... as the ratings tell us so far " - Nishant S
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
