Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #644 > unrolled thread

New Compression Technique: What to Do?

Back to article view | Back to comp.compression

Contents

  New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-19 08:03 -0800
    Re: New Compression Technique: What to Do? "D. Stussy" <spam+newsgroups@bde-arc.ampr.org> - 2011-12-19 14:10 -0800
      Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-20 06:09 -0800
        Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2011-12-20 08:37 -0800
          Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-20 09:02 -0800
            Re: New Compression Technique: What to Do? Willem <willem@toad.stack.nl> - 2011-12-20 17:12 +0000
              Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-20 10:16 -0800
                Re: New Compression Technique: What to Do? Willem <willem@toad.stack.nl> - 2011-12-20 19:11 +0000
                Re: New Compression Technique: What to Do? Jim Leonard <mobygamer@gmail.com> - 2011-12-21 09:19 -0800
                  Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-21 10:35 -0800
                    Re: New Compression Technique: What to Do? Jim Leonard <mobygamer@gmail.com> - 2011-12-22 12:21 -0800
                      Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2011-12-23 06:01 -0800
                        Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2011-12-30 10:05 -0800
                          Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2012-01-01 04:30 -0800
                            Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-02 09:08 -0800
                              Re: New Compression Technique: What to Do? Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 08:18 -0800
                                Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-24 12:56 -0800
                                  Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2012-02-02 10:50 -0800
                                    Re: New Compression Technique: What to Do? Thomas Richter <thor@math.tu-berlin.de> - 2012-02-03 09:07 +0100
                                    Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-04 20:33 -0800
                                    Re: New Compression Technique: What to Do? "George Johnson" <matrix29@charter.net> - 2012-02-07 07:48 -0500
                                    Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-07 09:47 -0800
                                      Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2012-02-08 06:25 -0800
                                        Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-08 06:55 -0800
                                          Re: New Compression Technique: What to Do? Harry Potter <rose.joseph12@yahoo.com> - 2012-02-08 07:11 -0800
                                            Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-08 08:21 -0800
                  Re: New Compression Technique: What to Do? Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2011-12-21 14:15 -0800
            Re: New Compression Technique: What to Do? pfraser <pete_fraser@comcast.net> - 2011-12-20 10:07 -0800
    Re: New Compression Technique: What to Do? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-12-20 20:19 +0000

Page 1 of 2  [1] 2  Next page →

#644 — New Compression Technique: What to Do?

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

[toc] | [next] | [standalone]

#645

"Harry Potter" <rose.joseph12@yahoo.com> wrote in message
news:48a9a490-2d47-4f43-adf1-e67cabb8251c@e2g2000vbb.googlegroups.com...
> 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.

LZW is hardly new.  Its original form was published in 1978.

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.

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.

[toc] | [prev] | [next] | [standalone]

#646

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.

[toc] | [prev] | [next] | [standalone]

#647

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.

[toc] | [prev] | [next] | [standalone]

#648

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).
>
> Post your results.

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

[toc] | [prev] | [next] | [standalone]

#649

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

[toc] | [prev] | [next] | [standalone]

#651

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

[toc] | [prev] | [next] | [standalone]

#652

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.



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

[toc] | [prev] | [next] | [standalone]

#656

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.

[toc] | [prev] | [next] | [standalone]

#657

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

[toc] | [prev] | [next] | [standalone]

#659

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.

[toc] | [prev] | [next] | [standalone]

#660

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.

[toc] | [prev] | [next] | [standalone]

#671

On Dec 23, 9:01 am, Harry Potter <rose.josep...@yahoo.com> wrote:
> 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.

How is it coming along.

[toc] | [prev] | [next] | [standalone]

#673

On Dec 30 2011, 1:05 pm, Earl_Colby_Pottinger
<earlcolby.pottin...@sympatico.ca> wrote:
> On Dec 23, 9:01 am, Harry Potter <rose.josep...@yahoo.com> wrote:
>
> > 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.
>
> How is it coming along.

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

[toc] | [prev] | [next] | [standalone]

#674

On Jan 1, 7:30 am, Harry Potter <rose.josep...@yahoo.com> wrote:
> On Dec 30 2011, 1:05 pm, Earl_Colby_Pottinger
>
> <earlcolby.pottin...@sympatico.ca> wrote:
> > On Dec 23, 9:01 am, Harry Potter <rose.josep...@yahoo.com> wrote:
>
> > > 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.
>
> > How is it coming along.
>
> Not well enough. :( I disabled the compression technique to test the
> compression structure.  That almost works, but there are corrupted
> bytes here and there.

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.

[toc] | [prev] | [next] | [standalone]

#819

On Jan 2, 9:08 am, Earl_Colby_Pottinger
<earlcolby.pottin...@sympatico.ca> wrote:
> On Jan 1, 7:30 am, Harry Potter <rose.josep...@yahoo.com> wrote:
>
>
>
> > On Dec 30 2011, 1:05 pm, Earl_Colby_Pottinger
>
> > <earlcolby.pottin...@sympatico.ca> wrote:
> > > On Dec 23, 9:01 am, Harry Potter <rose.josep...@yahoo.com> wrote:
>
> > > > 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.
>
> > > How is it coming along.
>
> > Not well enough. :( I disabled the compression technique to test the
> > compression structure.  That almost works, but there are corrupted
> > bytes here and there.
>
> 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.

That is a really nice post.

[toc] | [prev] | [next] | [standalone]

#826

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.

[toc] | [prev] | [next] | [standalone]

#946

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?

[toc] | [prev] | [next] | [standalone]

#947

Am 02.02.2012 19:50, schrieb 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?

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.

[toc] | [prev] | [next] | [standalone]

#975

On Feb 2, 1:50 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> 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?

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compression

csiph-web