|laziness, impatience, and hubris|
Re^2: Dynamically Updating Frequency Analysisby Limbic~Region (Chancellor)
|on May 09, 2013 at 18:01 UTC||Need Help??|
The reference to the Huffman Coding and "plugging holes" has nothing to do with this post - it deals with Challenge: Optimal Animals/Pangolins Strategy. You are absolutely correct about there not being any holes. The holes come in when you don't "properly construct" the tree. Somewhere in one of these threads, I mentioned that he is populating the tree top down instead of bottom up. I read somewhere that Huffman's professors had the same problem - it isn't perfect. I am sure this has confused some people because I have continued to refer to holes and Huffman Coding together rather than saying Huffman Coding-ish. I originally didn't mention Huffman Coding at all because that wasn't the road I was trying to go down - it just seemed like they were equivalent solutions - they are not.
The reason this thread doesn't look like it has anything to do with Huffman coding is because it isn't. This guy's idea was to map all 96 symbols to 7 bits and use the 32 remaining 7 bit sequences to encode some popular multi-character tuples.
You asked in reference to THEN and HE:
It is not clear why this is so. Is this because you aren't allowed overlapping sequences? Or some other reason. Can you explain more?
It is because HE is a complete substring of THEN. Once HE no longer exists anywhere in the file, there will no longer be any THEN to replace. Imagine the following dictionary:
Now imagine the file we are compressing contains
We note that HE appears 3 times and will give us the largest compression (I have used # to indicate the data has already been compressed).
There is no longer a THEN to consider.
Anyway, it sounds like this problem is NP hard
Cheers - L~R