New Compression Technique: What to Do?

[Harry Potter]

I recently discovered a new compression technique. On its own, it
seems to be okay. It can even provide a good compression ratio for
files already compresed. However, with LZW, I lose some
compressibility, resulting in poor results. My first goal with file
compression is to create a *better* compression technique, and I still
have ideas. I know of Huffman codes and arithmetic coding and would
like information on other techniques. Any feedback would be
appreciated.
--
Joseph Rose, a.k.a. Harry Potter
Working magic for the computer community

[Harry Potter]

On Dec 19, 5:10 pm, "D. Stussy" <spam+newsgro...@bde-arc.ampr.org>
wrote:
> LZW is hardly new.  Its original form was published in 1978.
>
I didn't say it clearly: by "new technque," I mean one I created
myself. LZW is simply a technique I was using alongside the new
technique.

> The idea of compression is to identify repeating patterns and represent
> them using fewer bits while non-repeating values get more bits.  When there
> are more repeating patterns than not, the reduction in bits used overall
> decreases, thus causing the benefit.  With small input, there's not enough
> repeating data to make this economical, and often the compression
> transformation may increase the size of the data.
>
That's tue. I've ben looking a long time for such an approach with
limited success. I recently found one that works well, but not on its
own. It seems to work well on .zip and .rar files, though. :) Now,
I just have to implement Huffman code or arithmetic coding based on
compession envionment or, if possible, user option.

> There is one difference from the published algorith that may help:  The
> algorithm specifies that it should reset its transformation codebook once
> it fills.  That prematurely resets the stream.  Delaying a reset until the
> codebook overflows (i.e. one entry more) is more useful, as existing
> repeating patterns in the data at the point of fill can be absorbed into
> the existing compression segment (where otherise, they would start a new
> segment at the cost of lost efficiency).  This modification is what the
> early 1990's DOS program "LHARC.EXE" did.

Use a sliding dictionary. Got it.

[Earl_Colby_Pottinger]

Suggestion.

Write a compression program.

Write a Decompression program.

Compress some files.

Decompress the results.

Do a byte-to-byte comparison between the original file and the
decompressed version.

Fix your mistakes (no-one write perfect code all the time).

Post your results.

[Harry Potter]

On Dec 20, 11:37 am, Earl_Colby_Pottinger

I am in the process of creating the routine. However, I want the
routine to at least *seem* better than others before continuing.

[Willem]

Harry Potter wrote:
) I am in the process of creating the routine. However, I want the
) routine to at least *seem* better than others before continuing.

You're comparing against LZW, right ? That's actually not a very
good compression algorithm, there are others that are way better.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[pfraser]

Harry Potter wrote:
> On Dec 20, 11:37 am, Earl_Colby_Pottinger
> <earlcolby.pottin...@sympatico.ca> wrote:
>> Suggestion.
>> Write a compression program.
>> Write a Decompression program.
>> Compress some files.
>> Decompress the results.
>> Do a byte-to-byte comparison between the original file and the
>> decompressed version.
>> Fix your mistakes (no-one write perfect code all the time).
>

> I am in the process of creating the routine. However, I want the
> routine to at least *seem* better than others before continuing.

It stands no chance of seeming better if it can't meet the
ECP requirements (above).

[Harry Potter]

On Dec 20, 12:12 pm, Willem <wil...@toad.stack.nl> wrote:
> Harry Potter wrote:
>
> ) I am in the process of creating the routine.  However, I want the
> ) routine to at least *seem* better than others before continuing.
>
> You're comparing against LZW, right ?  That's actually not a very
> good compression algorithm, there are others that are way better.
>

I am not comparing it against LZW. I plan to use it along with other
techniques, including LZW. Also, I'm not going to test-decompress
data and debug the software until the numbers show a better
technique. However, so far, my technique plus LZW produces poor
results. I have plans, though. Just bear with me; I'm doing the best
I can. :(

[Willem]

Harry Potter wrote:
) I am not comparing it against LZW. I plan to use it along with other
) techniques, including LZW. Also, I'm not going to test-decompress
) data and debug the software until the numbers show a better
) technique.

Why not? If it doesn't work properly, it's a waste of time.

[glen herrmannsfeldt]

Harry Potter <rose.j...@yahoo.com> wrote:
> I recently discovered a new compression technique. On its own, it
> seems to be okay. It can even provide a good compression ratio for
> files already compresed.

It seems to me that any work on new compression algorithms, ones that
should work better than existing algorithms, needs a new statistical
model of the data that it is trying to compress.

That is, to find redundancy that other algorithms don't, and exploit that
to reduce the size of the compressed file.

The existing algorithms do pretty well for a variety of different
types of files, even ones they weren't specifically designed to work on.

LZW, for example, works well on natural language text, which tends to
use words and letters within words in a non-uniform distribution.
Even for data with no substring redundancy, LZW can use the non-uniform
byte distribution to compress data.

JBIG2 was specifically designed around the statistics of binary
(black and white but no gray) images. It works very well for that
case, but not well at all for many other types of data.

-- glen

[Jim Leonard]

On Dec 20, 12:16 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> Also, I'm not going to test-decompress
> data and debug the software until the numbers show a better
> technique.

Research is fine, but at some point you should do the following:

1. Hand-assemble a few bytes of compressed data
2. Write a decompressor that can decompress the data
3. Write a compressor that creates output the decompressor can
decompress

Going through the above steps is HIGHLY recommended because many
people who believe they've discovered a new way to compress data don't
see the flaw in their reasoning until much time and effort has been
wasted. I'm not saying that your method is flawed -- I'm saying you
don't know if your method is flawed, so try to implement it. Don't
worry if it's not perfect or doesn't beat LZW. Just get it working
first and then look for ways to improve it. You may even figure out
how to improve it as you're implementing it.

Implement the above steps IN ORDER. Don't write the compressor
first. People who do that usually write the compressor, see the space
savings in the output, and then claim their method works and start
announcing to the world when they don't even have a way to reconstruct
the data.

[Harry Potter]

On Dec 21, 12:19 pm, Jim Leonard <mobyga...@gmail.com> wrote:
> On Dec 20, 12:16 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
>
> > Also, I'm not going to test-decompress
> > data and debug the software until the numbers show a better
> > technique.
>
> Research is fine, but at some point you should do the following:
>
> 1. Hand-assemble a few bytes of compressed data
> 2. Write a decompressor that can decompress the data
> 3. Write a compressor that creates output the decompressor can
> decompress
>
> Going through the above steps is HIGHLY recommended because many
> people who believe they've discovered a new way to compress data don't
> see the flaw in their reasoning until much time and effort has been
> wasted.  I'm not saying that your method is flawed -- I'm saying you
> don't know if your method is flawed, so try to implement it.  Don't
> worry if it's not perfect or doesn't beat LZW.  Just get it working
> first and then look for ways to improve it.  You may even figure out
> how to improve it as you're implementing it.
>

My technique seems good: two small compressed archives compress well
(>18% less), but highly-compressible files offer only slightly better
compression. It should be good after other techniques. Right now, I
plan to debug the technique; implement and debug LZW and Huffman/
arithmetic coding, then get the final results. BTW, I have other
improvements. Of course, as you warned me, I'm jumping the gun here.

> Implement the above steps IN ORDER.  Don't write the compressor
> first.  People who do that usually write the compressor, see the space
> savings in the output, and then claim their method works and start
> announcing to the world when they don't even have a way to reconstruct
> the data.

I tried to do that but couldn't resist. :(

--
Joseph Rose, a.k.a. Harry Potter

Working magic in the computer community

[Earl_Colby_Pottinger]

On Dec 21, 12:19 pm, Jim Leonard <mobyga...@gmail.com> wrote:

I see and agree with your point, to me writing the compressor and the
de-compressor is something I always do together. But you are right,
if one writes the compressor only it is tempting to think it is bug-
free and working great. That is why I also insist on the byte-by-byte
comparison test.

As you said research is good, but working code is king.

[Jim Leonard]

On Dec 21, 12:35 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> My technique seems good: two small compressed archives compress well
> (>18% less), but highly-compressible files offer only slightly better
> compression.

Already this is a red flag (compressed files reducing 18% but regular
files not). Have you decompressed the "two small compressed archives"
successfully yet? If not, STOP and write the decompressor for just
your method first.

[Harry Potter]

On Dec 22, 3:21 pm, Jim Leonard <mobyga...@gmail.com> wrote:
> Already this is a red flag (compressed files reducing 18% but regular
> files not).  Have you decompressed the "two small compressed archives"
> successfully yet?  If not, STOP and write the decompressor for just
> your method first.

I'm working on it.... I'll be back with the results.

[Earl_Colby_Pottinger]

How is it coming along.

[Harry Potter]

On Dec 30 2011, 1:05 pm, Earl_Colby_Pottinger

Not well enough. :( I disabled the compression technique to test the
compression structure. That almost works, but there are corrupted
bytes here and there.

[Earl_Colby_Pottinger]

Now you are learning. :)

You could have the best compression code going, but if your input/
output or memory management or data structures or .... have any errors
in them, you still don't have a working compressor/decompressor.

Still keep working on it. Remember even if your idea turns out to have
no value, you will still learn to be a better programmer and
debugger. There is no loss if you learn anything from the experience.

[Ernst]

On Jan 2, 9:08 am, Earl_Colby_Pottinger

That is a really nice post.

[Earl_Colby_Pottinger]

On Jan 24, 11:18 am, Ernst <Ernst_B...@sbcglobal.net> wrote:

> That is a really nice post.

I am terrible to people who don't want write code. To people who
clearly are willing to learn I usually am nice.

It is the people who don't want to learn overtime that I dislike.

Want to TRY to compress/decompress random data and trying to write the
code - go for it - you will learn something in the long run.

Want to CLAIM to compress/decompress random data and refusing to write
or show the code to do so - all past experiences says you are a kook
and/or con-artist.

[Harry Potter]

On Jan 24, 3:56 pm, Earl_Colby_Pottinger

<earlcolby.pottin...@sympatico.ca> wrote:
> Want to CLAIM to compress/decompress random data and refusing to write
> or show the code to do so - all past experiences says you are a kook
> and/or con-artist.

I got my technique debuged and running. So far, it sucks! :( By
design, it can only approach a 2:1 compression ratio. However, I
still have ideas. Are these the words of a kook and/or con-artist?

[Thomas Richter]

Well, I don't know what exactly you're doing, but *unless* you claim
that you can compress *all* data, this result looks quite reasonable.
For realisitic data (and not "random" data, for whatever this means
precisely) a 2:1 for lossless is pretty much what you get indeed. Don't
worry, you can try something very simple and get 2:1, and you can try
something very complicated, and in best case, you get a little bit
better than 2:1.

[Earl_Colby_Pottinger]

The problem here is you still have not made any statement that you
BOTH COMPRESSED and then DECOMPRESSED the data and then did a byte by
byte comparison to confirm that there are no errors.

Where have you seen me or others care about your compression ratio?
What FIRST matters is that after you compressed your data, that you
can then decompress out the resultant compressed data file back to the
original decompressed version.

If you refuse to do all the tests required to prove your claims then
you are a kook and/or con-artist!

So you are the one who has to answer the question, not us.

Have you compressed and then decompressed the data and then did a byte
by byte comparison to confirm your code works?

Have you? Yes or No? Until you do you are acting like a kook and/or
con-artist.

Don't be one, do the tests. ALL of them, then report the results.

Please.


So the question

[George Johnson]

"Harry Potter" <rose.j...@yahoo.com> wrote in message
news:9ddccd5a-5a75-461d...@o14g2000vbo.googlegroups.com...

Do you think the MD5 Hash Function started out as itself or a failed
Data Compression attempt with a Lateral Thinking realization that the
programmer's time not be entirely wasted?

There is failing at a goal and then later changing that failure into a
useful product.

[Earl_Colby_Pottinger]

So how is the decompressor working now?

Forget the compression ratio, just answer the question about what
happens after you run the compression module on some data, then take
that output and feed it to your decompressor, do you get your original
file back?

[Harry Potter]

On Feb 7, 12:47 pm, Earl_Colby_Pottinger

I got the results. The program decompressed the data properly. I
then backed up the program and started working on more of the
program. So far, I'm just testing for compressiblity. I'm doing a
little better now, but I still have my work cut out for me--namely a
very complex set of routines. I'm stubbonly persisting. :)

[Earl_Colby_Pottinger]

On Feb 8, 9:25 am, Harry Potter <rose.josep...@yahoo.com> wrote:

> I got the results.  The program decompressed the data properly.

Sorry, decompress properly does not cut it. Did you do a BYTE-BY-BYTE
comparison of the output file to the original data file?

This is a VERY important step! I once wrote a program that compressed
text 14:1, tested it repeatly, checked the beginning of the file was
okay, checked the end of the file was okay. It all looked good, I
boasted, I made big claims, I scrolled thru the entire text only to
find the center portion of the file was PURE GARBAGE!

Finally I fixed the bug and tested again, the compression ratio fell
to 3:1 and the my program must have been ten(10) times slower than
PKZIP which was giving me 3.5:1 on the same file.

DON'T JUST RUN THE COMPRESSOR AND DECOMPRESSOR ONLY - DO THE BYTE-BY-
BYTE COMPARISON!

[Harry Potter]

On Feb 8, 9:55 am, Earl_Colby_Pottinger

<earlcolby.pottin...@sympatico.ca> wrote:
> DON'T JUST RUN THE COMPRESSOR AND DECOMPRESSOR ONLY - DO THE BYTE-BY-
> BYTE COMPARISON!

I did. I used VBinDiff to compare the files, and the files were the
same. Unfotunately, I continued working on the software without
debugging it. It's not eaching the ZIP deflate technique ye, but I'm
stubbonly pursuing the issue.

[Earl_Colby_Pottinger]

On Feb 8, 10:11 am, Harry Potter <rose.josep...@yahoo.com> wrote:
> I did.  I used VBinDiff to compare the files, and the files were the
> same.

Interesting diff program.

Don't forget to use lots of comments in your code to remind yourself
why you did certain things the way you did, otherwise you will come
back a month later and get lost in your own code.