DOC PREVIEW
UGA CSCI 2720 - Lempel_Ziv

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

The LZ familyOverview of LZ familyLZ family overviewSender : The CompressorLZSlide 6Bit Representation of Coded InformationCompression good?Receiver: The Decompressor (ImplementationLempel-Ziv appletLempel Ziv Welsch (LZW)LZW compressionLZW encoderDemonstrationsLZW encoder exampleLZW decoderLempel-Ziv compressionLZW decoder exampleLZW IssuesLZW advantages/disadvantagesEntropy methodsSlide 22The LZ family LZ77LZRLZSSLZBLZH – used by zip and unzipLZ78 LZW – Unix compressLZC – Unix compressLZTLZMWLZJLZFGOverview of LZ familyTo demonstrate:simple alphabet containing only two letters, a and b, and create a sample stream of textLZ family overviewRule: Separate this stream of characters into pieces of text so that the shortest piece of data is the string of characters that we have not seen so far.Sender : The CompressorBefore compression, the pieces of text from the breaking-down process are indexed from 1 to n:LZindices are used to number the pieces of data. The empty string (start of text) has index 0. The piece indexed by 1 is a. Thus a, together with the initial string, must be numbered Oa. String 2, aa, will be numbered 1a, because it contains a, whose index is 1, and the new character a.LZthe process of renaming pieces of text starts to pay off.Small integers replace what were once long strings of characters. can now throw away our old stream of text and send the encoded information to the receiverBit Representation of Coded InformationNow, want to calculate num bits neededeach chunk is an int and a letternum bits depends on size of table permitted in the dictionary every character will occupy 8 bits because it will be represented in US ASCII formatCompression good? in a long string of text, the number of bits needed to transmit the coded information is small compared to the actual length of the text. example: 12 bits to transmit the code 2b instead of 24 bits (8 + 8 + 8) needed for the actual text aab.Receiver: The Decompressor (Implementationreceiver knows exactly where boundaries are, so no problem in reconstructing the stream of text. Preferable to decompress the file in one pass; otherwise, we will encounter a problem with temporary storage..Lempel-Ziv appletSeehttp://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic23/#JavaAppletLempel Ziv Welsch (LZW)previous methods worked only on charactersLZW works by encoding stringssome strings are replaced by a single codewordfor now assume codeword is fixed (12 bits)for 8 bit characters, first 256 (or less) entries in table are reserved for the charactersrest of table (257-4096) represent stringsLZW compressiontrick is that string-to-codeword mapping is created dynamically by the encoderalso recreated dynamically by the decoderneed not pass the code table between the twois a lossless compression algorithmdegree of compression hard to predictdepends on data, but gets better as codeword table contains more stringsLZW encoderInitialize table with single character stringsSTRING = first input characterWHILE not end of input streamCHARACTER = next input characterIF STRING + CHARACTER is in the string tableSTRING = STRING + CHARACTERELSEOutput the code for STRINGAdd STRING + CHARACTER to the string tableSTRING = CHARACTEREND WHILEOutput code for stringDemonstrationsAnother animated LZ algorithm …http://www.data-compression.com/lempelziv.htmlLZW encoder examplecompress the string BABAABAAALZW decoderLempel-Ziv compressiona lossless compression algorithmAll encodings have the same lengthBut may represent more than one characterUses a “dictionary” approach – keeps track of characters and character strings already encounteredLZW decoder example decompress the string <66><65><256><257><65><260>LZW Issuescompression better as the code table growswhat happens when all 4096 locations in string table are used?A number of options, but encoder and decoder must agree to do the same thingdo not add any more entries to table (as is)clear codeword table and start againclear codeword table and start again with larger table/longer codewords (GIF format)LZW advantages/disadvantagesadvantagessimple, fast and good compressioncan do compression in one passdynamic codeword table built for each filedecompression recreates the codeword table so it does not need to be passeddisadvantagesnot the optimum compression ratioactual compression hard to predictEntropy methodsall previous methods are lossless and entropy based lossless methods are essential for computer data (zip, gnuzip, etc.)combination of run length encoding/huffman is a standard toolare often used as a subroutine by other lossy methods (Jpeg, Mpeg)Lempel-Ziv compressiona lossless compression algorithmAll encodings have the same lengthBut may represent more than one characterUses a “dictionary” approach – keeps track of characters and character strings already


View Full Document

UGA CSCI 2720 - Lempel_Ziv

Documents in this Course
Load more
Download Lempel_Ziv
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lempel_Ziv and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lempel_Ziv 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?