demerphq,
Nice speaking with you again as well. I completley understand how confusing this must be to everyone else since I am having a hard time keeping it straight myself. I have multiple people on my team and they are each coming up with different ideas and I have my own. They are overlapping.

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:

0000000 = T
0000001 = H
0000010 = E
0000011 = N
0000100 = HE
0000101 = THEN
0000110 = <space>
[download]

Now imagine the file we are compressing contains

THE HEN THEN
[download]

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

T# #N T#N
[download]

There is no longer a THEN to consider.

Anyway, it sounds like this problem is NP hard

It certainly does which is why I think a heuristic solution would work. I just need to think about BrowserUk's concerns.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.