Improve Performance of String comparison

Hi all,

I am doing compression using Huffman .

I have a string of length around 1500000. The string consists of 1s and 0s only.

I have a linked list consisting of Huffman code table of a symbol and a short binary string representing the symbol.

This is what I do

Loop through longer length string
Loop through linked list
compared if substring of longer length string == string from linked list
decode
End
End

However, this operation takes around 20min to complete which is way too long to decompress a data.

Is there a faster way of decompressing algorithm using the same huffman coding?

Thanks a lot

If your STRING is really a binary number, perhaps it would be quicker to translate it to an integer first, then compare integers? That way you can get up to 32 "bytes" compared in one integer.

There are faster string compares, but they are a bit complex too, and by no means "a magic bullet". On a 32-bit machine, you can achieve about 4x improvement by comparing 4 bytes (one int) at a time. On a 64-bit machine, you get 8x improvment [1]. But that is the string comparison itself, and none of the other code that you run. Whilst I'm sure the string compare is a large proportion of your 20 minutes, I'd expect it to still be quite slow even at 8x faster string compare.

Also, are you sure that a linked list is the best method here? Perhaps you should consider using some sort of sorted container, so that you can eliminate comparisons that are not necessary - for example a binary search?

Are you taking the length of the string each time? strlen() is another function that is quite slow.

Of course, all of my suggestions are based on your brief description of the code - it would help to see the string compare loop in C++ - there may be other things that would help.

[1] The improvement assumes that the string is "mostly matching" - so comparing strings that mismatch on the first few bytes will be almost identical speed.

--
Mats

Huffman codes are the tree - so use tree to store the codes... You search should be a lot faster

Quote:

---

Originally Posted by vart

Huffman codes are the tree - so use tree to store the codes... You search should be a lot faster

---

I thought that was for the uncompressing side - if you are compressing, you need to compare the "current input" with the list of corresponding compressed values.

But I'm sure that the "uncompressed->compressed" list (using list in a vague container sense here) can be sorted or otherwise "optimized" to make the number of possible comparisons a lot fewer.

--
Mats

No, I'm pretty sure the whole point of the tree is to decompress -- you read a 0 and go left, or read a 1 and go right; if you land on a character print it out and start over, otherwise read a 0 and go left or read a 1 and go right.

It would be hard to use the tree to compress -- easier to use an associative array or similar (or if we assume our symbols are contiguous in the encoding, a plain old array).

Yeah, just build and use the tree to decompress.