LZW Presentation.pptx

lzw compression

1. LZW Encoding Algorithm By Israa A. Basheer Rasha A. Yousef Maalem A. Atiyaa Supervised By Assist. Prof. Wisam D. Abdullah TIKRIT UNIVERSITY COLLEGE OF COMPUTER SCIENCE AND MATHEMATICS POST GRADUATE

2. Introduction To LZW Compression Algorithm History of LZW algorithm developed by Abraham Lempel and Jacob Ziv , Lempel and Ziv published a series of papers describing various compression algorithms. Their first algorithm was published in 1977, hence its name: LZ77. This compression algorithm maintains its dictionary within the data themselves . In 1978, Lempel and Ziv published a second paper outlining a similar algorithm that is now referred to as LZ78. This algorithm maintains a separate dictionary. In 1984 Terry Welch published an improved version of the LZ78 dictionary coding algorithm developed by Lempel and Ziv . 2 LZW ( Lampel – Ziv -Welch ) Definition It is a lossless ‘dictionary based’ compression algorithm in which longer fragments of the input text are replaced by much shorter references to code words stored in the special set called dictionary. The Idea relies on reoccurring patterns to save data space. LZW is the foremost technique for general purpose data compression due to its simplicity and versatility. It is the basis of many PC utilities that claim to “double the capacity of your hard drive”. It used to reduce the size of files, e.g. for archival or transmission . It used by a number of formats , including GIF, TIFF, PostScript, PDF,  Unix  Compress, and V.42bis .

3. Working of the LZW Algorithm - The Algorithm is broken down into two parts, the encoding algorithm which converts the strings into integer codes, and the decoding algorithm which does vice versa. - Both the encoder and decoder algorithm has a default table or a code-string pair dataset that acts as the initial model for both the encoder and the decoder. And when the algorithm goes on the new integer codes for the various string patterns get added to this table. - The Encoding works by reading a sequence of symbols, grouping the symbols into strings, and converting the strings into codes. Because the codes take up less space than the strings they replace, we get compression. 3

4. Continue… Algorithm LZW compression uses a code table, with 4096 as a common choice for the number of table entries. Codes 0-255 in the code table are always assigned to represent single bytes from the input file . When encoding begins the code table contains only the first 256 entries, with the remainder of the table being blanks. Compression is achieved by using codes 256 through 4095 to represent sequences of bytes . As the encoding continues, LZW identifies repeated sequences in the data, and adds them to the code table . 4

5. Implementation : The idea of the compression algorithm is the following : As the input data is being processed, a dictionary keeps a correspondence between the longest encountered words and a list of code values. The words are replaced by their corresponding codes and so the input file is compressed. Therefore, the efficiency of the algorithm increases as the number of long, repetitive words in the input data increases. 5 * PSEUDOCODE (For Viewing): 1 Initialize table with single character strings 2 P = first input character 3 WHILE not end of input stream 4 C = next input character 5 IF P + C is in the string table 6 P = P + C 7 ELSE 8   output the code for P 9 add P + C to the string table 10 P = C 11 END WHILE 12 output code for P

6. Use the LZW algorithm to compress the string : BABAABAAA 6 Example Of LZW Compression

7. Example of LZW Compressiom : Step 1 7 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA BABAABAAA P=empty C=B P= p+c P=c

8. Example of LZW Compressiom : Step 2 8 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA 65 A 257 AB BABAABAAA P=B C=A

9. Example of LZW Compressiom : Step 3 9 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA 65 A 257 AB 256 BA 258 BAA BABAABAAA P=A C = B

10. Example of LZW Compressiom : Step 4 10 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA 65 A 257 AB 256 BA 258 BAA 257 AB 259 ABA BABAABAAA P=A C = A

11. Example of LZW Compressiom : Step 5 11 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA 65 A 257 AB 256 BA 258 BAA 257 AB 259 ABA 65 A 260 AA BABAABAAA P=A C= A

12. Example of LZW Compressiom : Step 6 12 ENCODER OUTPUT STRING TABLE Output code Representing Codeword String 66 B 256 BA 65 A 257 AB 256 BA 258 BAA 257 AB 259 ABA 65 A 260 AA 260 AA BABAABAAA P=AA C= empty

13. Advantage Of LZW : 1- The LZW is simple, easy and requires no prior information about the input data stream. 2- The LZW algorithm is faster compared to the other algorithms. 3- The LZW algorithm works more efficiently for files containing lots of repetitive data. 4-The LZW algorithm compresses the data in a single pass. 5- This is a lossless compression technique, none of the contents in the file are lost during or after compression. 13

14. Disadvantage Of LZW : 1- LZW is a fairly old compression technique . All recent computer systems have the powerful to use more efficient algorithms . 2- Creates entries in the dictionary that may never be used. 3- Useful only for large amount of text data when redundancy is high. 4- Royalties have to be paid to use LZW compression algorithms within applications. 14

15. 15 THANKS FOR ATTENTION