ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Compression one example

•Download as PPTX, PDF•
•
Amr Nasr
Amr Nasr

The document provides an overview and examples of different compression algorithms including LZW, Huffman coding, Shannon-Fano coding, and arithmetic coding. It discusses the process for each algorithm and provides examples to encode the text "BILLGATES". It also lists some advantages and disadvantages of each method.

1 of 31
Downloaded 16 times
Compression one example
Agenda LZW Example Huffman Example Shanon Fano Example Arithmetic Coding Example Advantages for Every method
BILLGATES 1 B B B BILLGATES 1 2 B I BI I ILLGATES 1 2 3 B I L BIL L LLGATES 1 2 3 B I L BIL3 L LGATES 1 2 3 4 B I L G BIL3G G GATES 1 2 3 4 5 B I L G A BIL3G A A ATES
1 2 3 4 5 6 B I L G A T BIL3G AT T TES 1 2 3 4 5 6 7 B I L G A T E BIL3G ATE E ES 1 2 3 4 5 6 7 8 B I L G A T E S BIL3G ATES S S
Advantages and Disadvantages of LZW Advantage: Is a lossless compression algorithm.Hence no information is lost. One need not pass the code table between the two compression and the decompression. Simple ,fast and good compression Disadvantage: What happens when the dictionary becomes too large One approach is to throw the dictionary away when it reaches a certain size Useful only for a large amount of test data where redundancy is high
Shannon–Fano Algorithm BILLGATES Symbols B I L G A T E S Probabilities 1/9 1/9 2/9 1/9 1/9 1/9 1/9 1/9
L B I G A T E S A L B I G A T E S B
For a given list of symbols, develop a corresponding list of probabilities or frequency counts so that each symbol’s relative frequency of occurrence is known. Sort the lists of symbols according to frequency, with the most frequently occurring symbols at the left and the least common at the right.
Divide the list into two parts, with the total frequency counts of the left part being as close to the total of the right as possible.
C L B I G A T S E
D L B I G A T S E
E L B I G A T S E
1 0 1 0 1 0 F 0 1 0 1 0 1 0 1 L B I G A T S E
Symbols L : 00 B: 01 I : 100 G: 101 A: 1100 T: 1101 E: 1110 S: 1111
2Bit(1+1)+3Bit*(1+1)+4B it*(1+1+1+1)/9 =2.888888Bits/symbol
What are the disadvantages of shanon fano coding? What is better shannon fano and huffman coding? huffman has a better compression rate.
Huffman Algorithm BILLGATES Symbols B I L G A T E S Probabilities 1/9 1/9 2/9 1/9 1/9 1/9 1/9 1/9
G A T E S L A B I B I G A S T E L B
ï‚› Create a leaf node for each symbol and add it to frequency of occurrence. ï‚› While there is more than one node in the queue: ï‚› Remove the two nodes of lowest probability or frequency from the queue ï‚› Prepend 0 and 1 respectively to any code already assigned to these nodes ï‚› Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities. ï‚› Add the new node to the queue. ï‚› The remaining node is the root node and the tree is complete.
B I G A T E L S
1 1 0 0 1 0 0 0 1 1 0 1 1 0 B I G A T E L S
Symbols : B: 00 I:01 G:100 A:101 T:1100 E:1101 L:1110 S:1111
2Bit*(1+1)+3Bit*(1+1)+4Bit*(1+1+1+1)/9 =2.888888 Bits/symbol
Advantages and disadvantages of Huffman This compression algorithm is mainly efficient in compressing text or program files. Images like they are often used in prepress are better handled by other compression algorithms.
What are the advantages of Huffman coding? Algorithm is easy to implement Produce a lossless compression of images
Adaptive Huffman Coding (Dynamic Huffman Coding) ï‚› Advantage: Source is encoded in real time. ï‚› Disadvantage: More chance for transmission error.
Arithmetic Coding
Compression one example
Compression one example
What are the Advantages of arithmetic coding over Huffman coding? ï‚› 1.the compression ratio is higher compared to huffman coding. ï‚› 2.efficiency is greater comparatively. ï‚› 3.Redundancy is much reduced.
THANK YOU

More Related Content

Compression one example

  • 2. Agenda LZW Example Huffman Example Shanon Fano Example Arithmetic Coding Example Advantages for Every method
  • 3. BILLGATES 1 B B B BILLGATES 1 2 B I BI I ILLGATES 1 2 3 B I L BIL L LLGATES 1 2 3 B I L BIL3 L LGATES 1 2 3 4 B I L G BIL3G G GATES 1 2 3 4 5 B I L G A BIL3G A A ATES
  • 4. 1 2 3 4 5 6 B I L G A T BIL3G AT T TES 1 2 3 4 5 6 7 B I L G A T E BIL3G ATE E ES 1 2 3 4 5 6 7 8 B I L G A T E S BIL3G ATES S S
  • 5. Advantages and Disadvantages of LZW Advantage: Is a lossless compression algorithm.Hence no information is lost. One need not pass the code table between the two compression and the decompression. Simple ,fast and good compression Disadvantage: What happens when the dictionary becomes too large One approach is to throw the dictionary away when it reaches a certain size Useful only for a large amount of test data where redundancy is high
  • 6. Shannon–Fano Algorithm BILLGATES Symbols B I L G A T E S Probabilities 1/9 1/9 2/9 1/9 1/9 1/9 1/9 1/9
  • 7. L B I G A T E S A L B I G A T E S B
  • 8. For a given list of symbols, develop a corresponding list of probabilities or frequency counts so that each symbol’s relative frequency of occurrence is known. Sort the lists of symbols according to frequency, with the most frequently occurring symbols at the left and the least common at the right.
  • 9. Divide the list into two parts, with the total frequency counts of the left part being as close to the total of the right as possible.
  • 10. C L B I G A T S E
  • 11. D L B I G A T S E
  • 12. E L B I G A T S E
  • 13. 1 0 1 0 1 0 F 0 1 0 1 0 1 0 1 L B I G A T S E
  • 14. Symbols L : 00 B: 01 I : 100 G: 101 A: 1100 T: 1101 E: 1110 S: 1111
  • 16. What are the disadvantages of shanon fano coding? What is better shannon fano and huffman coding? huffman has a better compression rate.
  • 17. Huffman Algorithm BILLGATES Symbols B I L G A T E S Probabilities 1/9 1/9 2/9 1/9 1/9 1/9 1/9 1/9
  • 18. G A T E S L A B I B I G A S T E L B
  • 19. ï‚› Create a leaf node for each symbol and add it to frequency of occurrence. ï‚› While there is more than one node in the queue: ï‚› Remove the two nodes of lowest probability or frequency from the queue ï‚› Prepend 0 and 1 respectively to any code already assigned to these nodes ï‚› Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities. ï‚› Add the new node to the queue. ï‚› The remaining node is the root node and the tree is complete.
  • 20. B I G A T E L S
  • 21. 1 1 0 0 1 0 0 0 1 1 0 1 1 0 B I G A T E L S
  • 24. Advantages and disadvantages of Huffman This compression algorithm is mainly efficient in compressing text or program files. Images like they are often used in prepress are better handled by other compression algorithms.
  • 25. What are the advantages of Huffman coding? Algorithm is easy to implement Produce a lossless compression of images
  • 26. Adaptive Huffman Coding (Dynamic Huffman Coding) ï‚› Advantage: Source is encoded in real time. ï‚› Disadvantage: More chance for transmission error.
  • 30. What are the Advantages of arithmetic coding over Huffman coding? ï‚› 1.the compression ratio is higher compared to huffman coding. ï‚› 2.efficiency is greater comparatively. ï‚› 3.Redundancy is much reduced.