Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Prozak

Compression Technologies

This topic is 5998 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, i''m researching into compression, lossless compression that is, and I would like to know more about the compression techniques used "out there"... I know Run Length Encoding, which is pretty basic... I''ve heard about "wave compression", or something like it... What other lossless mainstream compression techniques are used, in today''s most popular compressors, like WinACE, WinZIP, rar, etc...? Thanks,

[Hugo Ferreira][Positronic Dreams][Stick Soldiers]
"Redundant book title: "Windows For Dummies".
"Camouflage condoms: So they won''t see you coming".

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
huffman encoding

Share this post


Link to post
Share on other sites
by "wave compression", perhaps you mean wavelet based encoding, which is a <gack> "lossy" coder, that is supposed to provide better quality in less space than jpg''s. I think png''s may use it. The wavelet transform is a substitution for the DCT (Discrete Cosine Transformation) phase of lossy encoding.

About all I know about lossless encoding, is RLE, Hoffman, and zlib is free.

Share this post


Link to post
Share on other sites
The compression in PNG is strictly lossless (deflate, same as zlib). JPEG 2000 (the new/next version of JPEG) uses wavelets for its encoding, though.

[edited by - spock on June 5, 2002 12:41:41 AM]

Share this post


Link to post
Share on other sites
When doing lossless compression on unknown data most algorithms can be derived from one of three compression types:

Run Length Encoding: Basically encoding a repeating set of characters as a length value and a character value. This is done either by assuming most of the file has repeating characters and simply having a long string of value+character records, or by using an escape character to indicate that a character/pattern is going to be repeated. RLE is the fastest of the three types (for both encoding and decoding), however it produces the worst results most of the time. RLE is best for compressing things like flat bitmap images (like a screenshot of your desktop without wallpaper).

Huffman: Huffman works by storing characters/patterns in varying bit lengths. Instead of storing all characters as 8 bits it stores "e" as something like "01" and "z" as something like "0011010101010" (There is an algorithm to determine the best bit codes for characters in a file based their frequency). Huffman has the best overall compression of the three, however due to the bit manipulation is usually the slowest.

Lempel-Ziv: LZ works by find repetitve patterns in data. Whenever a repetition is found, rather than storing it again, it is stored as an address and length reference to the first instance of the repetion. This type of compression gets results similar to huffman.

A fourth type of compression that is not really in use (though you hear about it whenever a lab say they''ve found a way to compress data better than everyone else, they just have to test it on a second file...) is genetic/neural net compression. All compression algorithms seek to remove redundent information from a file (RLE and LZ are the better examples). The 4th type of compression uses AI to try and find patterns in data that we cannot see. For instance the file "123456789" has a pattern, however without hardcoding detection, compression and decompression for this exact type of pattern we can''t compress it. Using genetic algorithms (or similar ai technology), a program can be created that regenerates the original file, using any type of pattern it wants (the ai creates a special case decompressor).

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
by "wave compression", perhaps you mean wavelet based encoding, which is a "lossy" coder, that is supposed to provide better quality in less space than jpg''s.



Wavelets aren''t necessarily lossy, they are simply a data transformation. However, in order to get general lossless compression using wavelets (or at least, wavelet-like constructions), WITHOUT actually increasing the size of the data, you need some serious whacking and thwacking, and using strange boundary-case properties of integer arithmetic.

Most wavelet compression is in fact lossy, therefore, and also tends to lead to the most horrible visual artifacts because the actual wavelet base is badly chosen.

There are some nice websites around demonstrating it in fact.

People might not remember what you said, or what you did, but they will always remember how you made them feel.

Share this post


Link to post
Share on other sites
We''ll, i don''t want to sound arrogant or anything,
but those compression schemes seem to me quite weak.

What is the best general-purpose compressor tool
in the world, currently? (even if it takes 10m to
compress a 80Kb file...)

[Hugo Ferreira][Positronic Dreams][Stick Soldiers]
"Redundant book title: "Windows For Dummies".
"Camouflage condoms: So they won''t see you coming".

Share this post


Link to post
Share on other sites
...and another question... if a new compression tool
for the home user came up that compressed 10% better than
zip and alike, would it have an impact, or is the market
saturated?

I think you can never have "enough" compression!

[Hugo Ferreira][Positronic Dreams][Stick Soldiers]
"Redundant book title: "Windows For Dummies".
"Camouflage condoms: So they won''t see you coming".

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!