Google Answers: lossless compression algorithms

View Question

Q: lossless compression algorithms ( Answered, 1 Comment )

Question

Subject: lossless compression algorithms
Category: Computers > Algorithms
Asked by: malith-ga
List Price: $10.00

Posted: 20 Jul 2002 11:09 PDT
Expires: 19 Aug 2002 11:09 PDT
Question ID: 43207

I need a comprehensive guide to lossless compression algorithms. With
all of the major lossless compression algorithms covered in great
detail with diagrams and practical examples accompanying them.

Request for Question Clarification by webadept-ga on 20 Jul 2002 12:57 PDT
Hi, 

You are refering to video and audio compression, and you want a hardcopy book.. yes?

Answer

Subject: Re: lossless compression algorithms
Answered By: blader-ga on 20 Jul 2002 14:14 PDT

Dear malith-ga: Thank you for your question. I have found several comprehensive guides to lossless compression algorithms on the internet. I have ordered these resources by their quality and relevance for your convenience. VectorSite.net has an excellent, detailed guide to lossless compression algorithms. It covers RLE, Huffman, Arithmetic, LZ-77 and LZW codings. It is available here: http://www.vectorsite.net/ttdcmp1.html The ICS Department at UCI has put up Lelewer and Hirschberg's "Data Compression" text book online. It covers all of the fundamental compression algorithms. That is available below: http://www.ics.uci.edu/~dan/pubs/DataCompression.html A less formal but no less detailed guide to data compression is available from the Ganssle Group. They also include basic source code samples for the Huffman and other coding techniques: http://www.ganssle.com/articles/acompres.htm GroovyWeb also has a guide to lossless compression algorithms, replete with animated pictures. It covers the Huffman and LZ methods. http://www.groovyweb.uklinux.net/index.php?page_name=Lossless%20Data%20Compression Finally, the Data Compression Reference Center offers a brief introduction to the fundamental compression algorithms. It is available below: http://www.rasip.fer.hr/research/compress/algorithms/index.html For an excellent hard copy book on the subject, I would recommend "Introduction to Information Theory and Data Compression." You may purchase it from Amazon here: http://www.amazon.com/exec/obidos/ASIN/0849339855/103-5491594-7605422 Related Google Directory: http://directory.google.com/Top/Computers/Algorithms/Compression/?tc=1 Google Search Strategy: lossless compression algorithms ://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=lossless+compression+algorithms&btnG=Google+Search I hope this was the information you were looking for. If you need any clarifications, please don't hesitate to ask. I would be more than happy to assist you further. Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 20 Jul 2002 21:48 PDT I need a comprehensive guide to lossless compression algorithms. With all of the major lossless compression algorithms covered in great detail with diagrams and practical examples accompanying them. The algorithms that I want clarification in are as follows Statistical compression algorithms -Huffman, Arithmetic Substitutional compression algorithms- LZW, LZSS Grouping compression algorithms Variable bit compression algorithms -VBC Location based compression algorithms -LBE Paring compression algorithms Word based compression algorithms Fibonacci based compression algorithms Combining based compression algorithms Reduction based compression algorithms I want all of these algorithms to be in one place or collected into one place. Malith
Request for Answer Clarification by malith-ga on 21 Jul 2002 00:04 PDT I need a comprehensive guide to lossless compression algorithms. With all of the major lossless compression algorithms covered in great detail with diagrams and practical examples accompanying them. The algorithms that I want clarification in are as follows Statistical compression algorithms -Huffman, Arithmetic Substitutional compression algorithms- LZW, LZSS Run length compression algorithms Grouping compression algorithms Variable bit compression algorithms -VBC Location based compression algorithms -LBE Paring compression algorithms Word based compression algorithms Fibonacci based compression algorithms Combining based compression algorithms Reduction based compression algorithms I want all of these algorithms to be in one place or collected into one place. I also need details on the following theories that are associated with compression CRC code Entropy Hashing and hash tables Lazy matching Mathematic rescaling Elias gamma codes Huff codes Golomb codes Malith
Clarification of Answer by blader-ga on 21 Jul 2002 00:26 PDT Dear malith-ga: Thank you for your clarification request. Unfortunately, after an extensive search, I was unable to locate a resource that contained all of the above clarification information in a single site online. In addition, most of the fundamental algorithms you mentioned are already covered by the resources I have provided in my answer. Would it be acceptable if I can provide seperate resources for those algorithms not covered in my original answer? However, I was able to find a hard cover text book that does cover most of the list you mentioned above. It is called "Data Compression. The Complete Reference." You may purchase it here: http://www.bookpool.com/.x/4yrty864o4/sm/0387950451 Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 21 Jul 2002 03:48 PDT Greetings blader-ga Yes, it would be acceptable if you do provide me with the separate resources for the question, in the understanding of course that all of the required information that I have requested is present in the separate resources that you provide me with. If you can collect all the information in the different resources on to a single document and provide it to me, it will be greatly appreciated. I would like to receive web links and not books that are relevant to the subject. Malith
Clarification of Answer by blader-ga on 21 Jul 2002 15:03 PDT Dear malith-ga: Thank you for your clarification request. Here is the list you requested. Statistical compression algorithms -Huffman, Arithmetic Substitutional compression algorithms- LZW, LZSS Run length compression algorithms http://www.vectorsite.net/ttdcmp1.html Grouping Compression Algorithms http://www.geocities.com/hmaxf_urlcr/grouping.htm Variable Bit Count http://www.geocities.com/hmaxf_urlcr/vbc.htm Location Based Encoding http://in.geocities.com/iamthebiggestone/how_lbe_works.htm Paring based compression Algorithms [ I was unable to find any lossless paring compression algorithms ] Word Based Compression Algorithms http://www.csr.uvic.ca/~nigelh/Publications/wordCompression.pdf Fibonacci based compression algorithms. [ I was unable to find any Fibonacci based compression algorithms. However, I was able to find a relationship between Huffman codes and Fibonacci numbers ] http://www.arturocampos.com/ac_fib_huffman.html http://mathforum.org/epigone/sci.math/twalgixskay Combining Based Compression Algorithms [ I was unable to find any combining based compression algorithms ] Reduction Based Compression Algorithms [ I was unable to find any combining based compression algorithms ] CRC Codes http://www.seanerikoconnor.freeservers.com/CommunicationTheory/ChannelCoding/Crc/CRCTheory.html Entropy http://www.math.psu.edu/gunesch/Entropy/shannon.ps http://mathworld.wolfram.com/Entropy.html Hashing and hash tables http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html Lazy Matching http://www.enx.polyu.edu.hk/ckli/publication/thesis/ma-c2000.pdf (3.2.2 Non-greedy matching) - http://216.239.35.100/search?q=cache:uf9wY7K0vpwC:japhy.perlmonk.org/book/3.doc+%22Lazy+matching+%22+&hl=en&ie=UTF-8 Mathematic Rescaling [ I was unable to find any information on "mathematic rescaling" ] Elias Gamma Codes http://www.wikipedia.com/wiki/Elias_Gamma_coding Huffman Codes http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/huffman.html Golomb Codes http://www.iro.umontreal.ca/~pigeon/science/vlc/golomb.html Unfortunately, I am unable to collect all of the information in a single document here, due to copyright issues. I would if I were allowed to, but I am unable to do so legally. My apologies. Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 21 Jul 2002 23:18 PDT Greetings blader-ga Mathematic Rescaling refers to Arithmetic Rescaling, with reference to arithmetic coding of course. Try to find algorithms that are based on a paring, combining, reduction and Fibonacci principles. I will respect the relevant copyrights of the documents and I do not require all of the information to be collected into one source, although it would be nice. Please try to find the required information as specified. Malith
Clarification of Answer by blader-ga on 22 Jul 2002 00:52 PDT Dear malith: Thank you for your clarification request. After an extensive online search, here are the resources I have found relating to your last clarification request: Re Arithmetic Algorithms: I was able to find a resource on arithmetic coding as it relates to Data Compression. That is available here: http://dogma.net/markn/articles/arith/part2.htm I was able to find several resources on "Fibonacci Codes" as it relates to Data Compression: http://www.iro.umontreal.ca/~pigeon/science/vlc/fibonacci.html http://dogma.net/markn/articles/arith/part2.htm The following three pages mention "Fibonacci Codes" as it related Data Coding in passing: http://home.attbi.com/~lkrakauer/codedata.htm http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html I have tried extensively to search for algorithms involving "paring", "reduction" and "combining" once again, and I was still unable to turn up any resources relating to those. Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 22 Jul 2002 05:13 PDT Greetings blader-ga Thank you for the information that you have provided me. I’ll take your on the fact that certain information cannot be found, it may be a problem at my end. If you clarify and provide information on the following aspects it will be greatly appreciated. The relationship between matrices and the Huffman compression algorithm. Can you provide me with an online book that focuses on ’data compression’, in PDF format or in any other format. You have provided me with a postscript document as references, please provide information about viewer that I can view these files in. Thank you for the information that you have provided me with. Regards, Malith
Request for Answer Clarification by malith-ga on 22 Jul 2002 06:36 PDT Greetings blader-ga I’ll just clarify on the algorithms that you were unable to find information on. The PARING compressor works with a dictionary but only the first 64 or 128 are relevant (The most common one). If a pair (Word) is not found in the first 64 the first byte of the word is stored + 64 (or 128) so 1 byte is stored in 1 byte. If the word is found in the first 64 then the complete pair is stored as 1 byte (number < 64). So 2 bytes will be stored in 1 byte. ORDERER: This algorithm created to get some kind of order in a file so it could be compressed better. The idea was to put the small values in front and all the bigger values at the end of the file. The problem was that it had a great amount of overhead because every byte needs an extra bit so it can be replaced in its original position. This was how this idea was born course why not storing all the values < 64 in 6 bits so you gain every time 2 bits. The idea was nice but you have to get a large amount of values < 64 to get some gain overall. ELIMINATOR: This method looks witch character is most common then removes it from the file and in the front of the file it will store that character one time and than it will store it as position pointers witch will tell the decompressor where to put the original character. COMBINER: This method will combine two codes it will find two bytes witch are smaller than 16 = 4 bits rips of the first 4 bits of the 2 bytes and put them together example: 04 & 0B witch will be stripped 4 & B and put together 4B which can be stored in 1 byte so 2 bytes = 1 byte this is basically the idea behind it. SHORTENER: This one will compress in very small amounts cause every byte stored also needs a controller bit witch will be stored. There are 3 ranges witch can be stored. 0 - 63 = 6 bits = range 1 64 - 127 = 6 bits + 64 = range 2 128 - 255 = 7 bits + 127 = range 3 During compression the range type is stored in the controller bits on this way. If bytemod(range)=1 then next value must be between 0 and 63. If not then store a 0 and move to the next bytemod without storing the value. If it is storing a 1 and store the value according to the numbers of bits required for that value. If the compression is finished store 3 x 0 to tell the decompressor that the EOF has reached. STRIPPER: For this algorithm you have to know a little bit of Elias code (gamma) because this is used in the control stream. This compressor makes use of values >127 and <128 witch can be stored in 7 bits if you keep up some kind of controller First a bit will be stored to tell the decompressor that the first 7 bits read must be < 128(lowbyte) or > 127(highbyte). If the first byte is a lowbyte then it will start counting the number of lowbytes following this one. Every byte will be stored in 7 bits and the control stream will hold the amount of follower low- or highbytes. So if this sequence is found: 84,3F,57,72,12,57,34,3A,9E,A0 Then this will be stored 1 to say we start with a highbyte gain = -1 bits 1 as Elias to say when having 1 hyghbyte (stored as 04 in 7 bits) gain = 0 bits change to lowbyte 00111 as elias code to say wheer having 7 lowbytes (stored as 3F,57,72,12,57,34,3A each in 7 bits) gain = 2 bits Change to highbyte 010 as Elias code to say where having 2 highbytes (stored as 1E, 20 in 7 bits) gain = -1 bits so overall were gained - 1 + 0 + 2 - 1 = 0 bits in this example REDUCER This is a 1 run method but we have to keep the whole contents in memory until some variables are saved witch are needed for the decompressor This compressor makes use of a dictionary and code the ASCII character to the position it is located in for every character it has to store a header and location there are 7 headers which will tell you the amount of bits to read for the location Example: Header: positions 0 : 0/1 1 : 2/3/4/5 2 : 6/7/8/9/10/11/12/13 3 : 14/15/16/17/18/19/20/21/22/23/24/25/26/27/28/29 etc The header will have 1,2 or 3 bits depending on the numbers of chars to compress The dictionary is build up from the most common char to the least common char if as char must be stored which is the 6th most common char in the dictionary then the position in the dictionary will be 6 but since we start the value 0 the position will be 6-1=5 5 will fall within the range of header 1 so the header bits will be 001 with will tell us to store 2 bits more for the position of the char since header 1 start with position 2 we can subtract this from the actual position 5-2=3 which can be stored in 2 bits 11 so the code to store the 6ed character will be 001 11 this reducer don’t have to store the dictionary into the output stream cause it will be created on the flow Try to find algorithms that are similar to the functionality that is explained here. Regards, Malith
Clarification of Answer by blader-ga on 22 Jul 2002 12:33 PDT Dear malith-ga: Thank you for your clarification request. I have found two resources that deal with matrices as it relates to Huffman codes. The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees http://epubs.siam.org/sam-bin/dbq/article/31107 The LBE Algorithm relies on a triangular matrices based rather than a tree based encoding for the Huffman: http://in.geocities.com/iamthebiggestone/how_lbe_works.htm I posted a link to a full text book online in my original answer. I was unable to find additional full texts of a text book online. Here is the link the the book in my original answer: http://www.ics.uci.edu/~dan/pubs/DataCompression.html You may view PostScript files using GhostView. That is available here: http://in.geocities.com/iamthebiggestone/how_lbe_works.htm Best Regards, blader-ga
Clarification of Answer by blader-ga on 22 Jul 2002 12:33 PDT My apologies. The link to the Ghostview reader is here: http://www.cs.wisc.edu/~ghost/ Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 23 Jul 2002 00:23 PDT Greetings blader-ga I have provided you with a description of the algorithms that you were unable to find. If you are unable to find the exact algorithm try to find and algorithm that is similar in functionality to the algorithms that I have descried above. Please provide links to implementation to the algorithms that I have requested, I am particularly in these compression algorithms being implemented in visual basic. Meaning visual basic source code implantations of the Huffman, arithmetic, lzw, lzss or any other compression algorithm for that matter witch is lossless in nature of curse. Thank you for all the help you are providing Regards, Malith
Clarification of Answer by blader-ga on 23 Jul 2002 00:52 PDT Dear malith-ga: Thank you for your clarification request. I have again attempted to search for by name of each of these compression algorithms, including the new ones you have posted in your latest clarification request. None of them match what you are seeking. I would recommend you perhaps using a text book instead, as I believe that it is not available online. I do not have the technical knowledge, nor do I feel that it is feasible time wise, to analyze every compression algorithm I can find in order to see if they match the functionality you have described. I'm sorry that I am unable to assist you further. If you feel that the resources I have provided did not answer your question sufficiently to justify your cost, then you may apply for a full refund here: https://answers.google.com/answers/main?cmd=refundrequest Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 23 Jul 2002 02:20 PDT Greetings blader-ga I understand that the requested information is very hard to find and it may not even exist online, but I do admire the effort that you have put on to this search and for that I thank you very much. As a final request could you please provide the following information. Regarding the source codes of the compression algorithms. Please provide links to implementation to the algorithms that I have requested, I am particularly in these compression algorithms being implemented in visual basic. Meaning visual basic source code implantations of the Huffman, arithmetic, lzw, lzss or any other compression algorithm for that matter witch is lossless in nature of course. Thank you for all the help you are providing Regards, Malith
Clarification of Answer by blader-ga on 23 Jul 2002 03:44 PDT Dear malith: Thank you for your kind clarification request. I was unable to find any algorithms implemented in Visual Basic, with the exception of one LZH Dll. However, I was able to find many algorithms implemented in C. Here is all of my results: VB LZH Dll: http://www.programmersheaven.com/search/download.asp?FileID=204 RLE Compression in C: http://www.programmersheaven.com/search/download.asp?FileID=2296 LZ77 Compression in C: http://www.programmersheaven.com/search/download.asp?FileID=2203 Arithmetic Coding in C: http://www.programmersheaven.com/search/download.asp?FileID=2187 http://www.programmersheaven.com/search/download.asp?FileID=2251 LZ Algorithm in C: http://www.programmersheaven.com/search/download.asp?FileID=18277 Huffman Coding in C: http://www.programmersheaven.com/search/download.asp?FileID=18231 http://www.programmersheaven.com/search/download.asp?FileID=18599 LHA in C: http://www.programmersheaven.com/search/download.asp?FileID=2261 Various Algorithms in C: http://www.programmersheaven.com/search/download.asp?FileID=2257 I apologize for the lack of VB source code. For speed purposes, compression source codes are rarely coded in VB. I hope you find that this information fits your needs. Best Regards, blader-ga
Request for Answer Clarification by malith-ga on 24 Jul 2002 22:33 PDT Greetings blader-ga I forgot to ask you another important question this is regarding the BWT and PPM compression algorithms, can you provide me detailed description and a practical implementation of the above algorithms and their predecessors. Regards, Malith
Clarification of Answer by blader-ga on 24 Jul 2002 22:51 PDT Dear malith-ga: Here are the most relevant resources I have found relating to BWT and PPM: Burrows Whellet Transform: http://citeseer.nj.nec.com/rd/90005591%2C498845%2C1%2C0.25%2CDownload/http%3AqSqqSqciteseer.nj.nec.comqSqcacheqSqpapersqSqcsqSq24127qSqhttp%3AzSzzSzwww.mfn.unipmn.itzSz%7EmanzinizSzpaperszSz..zSzpaperszSzmfcs99x.pdf/manzini99burrowswheeler.pdf PPM: http://www.datacompression.info/PPM.shtml Best Regards, blader-ga

Comments

Subject: Text Compression
From: ulu-ga on 20 Jul 2002 19:49 PDT

I enjoyed this book but it was published in 1990.  One reviewer
mentioned a second edition of another title (1999) by some of the same
authors.  It covers the principles behind the algorithms as well as
the details.

Text Compression (Prentice Hall Advanced Reference Series)
by Timothy C. Bell, Ian H. Witten, Ian Whitten (Contributor), John
Cleary (Contributor)
http://www.amazon.com/exec/obidos/ASIN/0139119914

Managing Gigabytes: Compressing and Indexing Documents and Images
by Ian H. Witten, Alistair Moffat, Timothy C. Bell
http://www.amazon.com/exec/obidos/ASIN/1558605703

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.

Search Google Answers for

Google Home - Answers FAQ - Terms of Service - Privacy Policy