Data CompressionLossless And Lossy CompressionSlide 3Text CompressionLZW CompressionSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Code Table RepresentationSlide 18LZW DecompressionSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Time ComplexityData Compression•Reduce the size of data.Reduces storage space and hence storage cost.•Compression ratio = original data size/compressed data sizeReduces time to retrieve and transmit data.Lossless And Lossy Compression•compressedData = compress(originalData)•decompressedData = decompress(compressedData)•When originalData = decompressedData, the compression is lossless.•When originalData != decompressedData, the compression is lossy.Lossless And Lossy Compression•Lossy compressors generally obtain much higher compression ratios than do lossless compressors.Say 100 vs. 2.•Lossless compression is essential in applications such as text file compression.•Lossy compression is acceptable in many imaging applications.In video transmission, a slight loss in the transmitted video is not noticed by the human eye.Text Compression•Lossless compression is essential.•Popular text compressors such as zip and Unix’s compress are based on the LZW (Lempel-Ziv-Welch) method.LZW Compression•Character sequences in the original text are replaced by codes that are dynamically determined.•The code table is not encoded into the compressed text, because it may be reconstructed from the compressed text during decompression.LZW Compression•Assume the letters in the text are limited to {a, b}.In practice, the alphabet may be the 256 character ASCII set.•The characters in the alphabet are assigned code numbers beginning at 0.•The initial code table is:codekey0a1bLZW Compression•Original text = abababbabaabbabbaabba•Compression is done by scanning the original text from left to right.•Find longest prefix p for which there is a code in the code table.•Represent p by its code pCode and assign the next available code number to pc, where c is the next character in the text that is to be compressed.codekey0a1bLZW Compression•Original text = abababbabaabbabbaabba•p = a•pCode = 0•c = b•Represent a by 0 and enter ab into the code table.•Compressed text = 0codekey0a1b2abLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 0codekey0a1b2ab3ba•p = b•pCode = 1•c = a•Represent b by 1 and enter ba into the code table.•Compressed text = 01LZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 01codekey0a1b2ab3ba•p = ab•pCode = 2•c = a•Represent ab by 2 and enter aba into the code table.•Compressed text = 0124abaLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 012codekey0a1b2ab3ba•p = ab•pCode = 2•c = b•Represent ab by 2 and enter abb into the code table.•Compressed text = 01224aba5abbLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 0122codekey0a1b2ab3ba•p = ba•pCode = 3•c = b•Represent ba by 3 and enter bab into the code table.•Compressed text = 012234aba5abb6babLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 01223codekey0a1b2ab3ba•p = ba•pCode = 3•c = a•Represent ba by 3 and enter baa into the code table.•Compressed text = 0122334aba5abb6bab7baaLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 012233codekey0a1b2ab3ba•p = abb•pCode = 5•c = a•Represent abb by 5 and enter abba into the code table.•Compressed text = 01223354aba5abb6bab7baa8abbaLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 0122335codekey0a1b2ab3ba•p = abba•pCode = 8•c = a•Represent abba by 8 and enter abbaa into the code table.•Compressed text = 012233584aba5abb6bab7baa8abba9abbaaLZW Compression•Original text = abababbabaabbabbaabba•Compressed text = 01223358codekey0a1b2ab3ba•p = abba•pCode = 8•c = null•Represent abba by 8. •Compressed text = 0122335884aba5abb6bab7baa8abba9abbaaCode Table Representation•Dictionary.Pairs are (key, element) = (key,code).Operations are : get(key) and put(key, code)•Limit number of codes to 212.•Use a hash table.Convert variable length keys into fixed length keys.Each key has the form pc, where the string p is a key that is already in the table.Replace pc with (pCode)c.codekey0a1b2ab3ba4aba5abb6bab7baa8abba9abbaaCode Table Representationcodekey0a1b2ab3ba4aba5abb6bab7baa8abba9abbaacodekey0a1b20b31a42a52b63b73a85a98aLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•Convert codes to text from left to right.•0 represents a.•Decompressed text = a•pCode = 0 and p = a.•p = a followed by next text character (c) is entered into the code table.codekey0a1bLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•1 represents b.•Decompressed text = ab•pCode = 1 and p = b.•lastP = a followed by first character of p is entered into the code table.codekey0a1b2abLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•2 represents ab.•Decompressed text = abab•pCode = 2 and p = ab.•lastP = b followed by first character of p is entered into the code table.codekey0a1b2ab3baLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•2 represents ab•Decompressed text = ababab.•pCode = 2 and p = ab.•lastP = ab followed by first character of p is entered into the code table.codekey0a1b2ab3ba4abaLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•3 represents ba•Decompressed text = abababba.•pCode = 3 and p = ba.•lastP = ab followed by first character of p is entered into the code table.codekey0a1b2ab3ba4aba5abbLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•3 represents ba•Decompressed text = abababbaba.•pCode = 3 and p = ba.•lastP = ba followed by first character of p is entered into the code table.codekey0a1b2ab3ba4aba5abb6babLZW Decompression•Original text = abababbabaabbabbaabba•Compressed text = 012233588•5 represents abb•Decompressed text = abababbabaabb.•pCode = 5 and p = abb.•lastP = ba followed by first character of p is entered into the code table.codekey0a1b2ab3ba4aba5abb6bab7baaLZW Decompression•Original text =