Re: huffman tree algorithm - C# Discussion Boards

23-Jul-03 13:59

My first thought is that the service is already running on the machine you're installing on.

Cheers, Julian
Program Manager, C#

This posting is provided "AS IS" with no warranties, and confers no rights.

Re: Access Denied

Alexandru Serban23-Jul-03 19:55

Alexandru Serban

23-Jul-03 19:55

No, I`ve uninstalled it before. Wink | ;)

I`ve cleaned up the registry of any information regarding this service and it doesn`t exists on the HDD either. I`ve changed the product and upgrade code and still nothing. I have administrative rights, I even give miself rights to act as a part of the operating sistem Poke tongue | ;-P

.
The entry in the Application log is:

The description for Event ID ( 11001 ) in Source ( MsiInstaller ) cannot be found. The local computer may not have the necessary registry information or message DLL files to display messages from a remote computer. You may be able to use the /AUXSOURCE= flag to retrieve this description; see Help and Support for details. The following information is part of the event: Product: FaxManagementServices -- Error 1001. Access is denied.<br />
, (NULL), (NULL), (NULL), (NULL), (NULL), (NULL).<br />

I`ve activated the security audit and apparenty there is not an authentication faliure during the install process.

huffman tree algorithm

jtmtv1823-Jul-03 11:23

jtmtv18

23-Jul-03 11:23

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...

totig23-Jul-03 13:27

totig

23-Jul-03 13:27

Hi, I know this probably wont help, but have you tried using the Java conversion assistant?

Julian Bucknall [MSFT]23-Jul-03 13:41

23-Jul-03 13:41

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.

jtmtv1823-Jul-03 14:46

jtmtv18

23-Jul-03 14:46

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...

Frank Olorin Rizzi24-Jul-03 4:11

Frank Olorin Rizzi

24-Jul-03 4:11

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

Julian Bucknall [MSFT]24-Jul-03 8:48

24-Jul-03 8:48

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.

Frank Olorin Rizzi24-Jul-03 4:07

Frank Olorin Rizzi

24-Jul-03 4:07

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;  //The character<br />
  private int f;   //The frequency<br />
}<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 Smile | :)

jtmtv1824-Jul-03 7:52

jtmtv18

24-Jul-03 7:52

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...

Julian Bucknall [MSFT]24-Jul-03 8:50

24-Jul-03 8:50

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.

Multithreaded application design question.

Frank Olorin Rizzi24-Jul-03 16:39

Frank Olorin Rizzi

24-Jul-03 16:39

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

GriffonRL23-Jul-03 11:11

GriffonRL

23-Jul-03 11:11

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.

Re: Multithreaded application design question.

wightman_michael22-Dec-09 15:40

wightman_michael

22-Dec-09 15:40

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");
}
}
}
}

MethodInfo Invoke, bad performance?

STW23-Jul-03 9:15

23-Jul-03 9:15

I use the MethodInfo Invoke() Method. The Invoked Method is a drawing routine.
Is it right that the MethodInfo Invoke() Method is extremly slow?

Eric Gunnerson (msft)23-Jul-03 10:02

Eric Gunnerson (msft)

23-Jul-03 10:02

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.

STW26-Jul-03 23:37

26-Jul-03 23:37

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

Eric Gunnerson (msft)27-Jul-03 5:23

Eric Gunnerson (msft)

27-Jul-03 5:23

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?

STW27-Jul-03 8:48

27-Jul-03 8:48

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

Daniel Turini23-Jul-03 11:31

Daniel Turini

23-Jul-03 11:31

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

STW26-Jul-03 23:41