Huffman tree coding

Greedy Methodology

1. Huffman Tree Coding Greedy Technique 1 Dr. P. Subathra Prof/ IT KAMARAJ College of Engg . & Tech (AUTONOMOUS) Madurai

2. Huffman Tree Coding Encoding In computer technology,  encoding  is the process of putting a sequence of characters into a special format for transmission or storage purposes. Code Word The special format that represents each character is called as the code word Fixed Length Encoding fixed-length encoding that assigns to each symbol a bit string of the same length m Eg . ASCII codes Variable Length Encoding Variable-length encoding , which assigns codewords of different lengths to different symbols 2

3. Huffman Tree Coding Encoding In computer technology,  encoding  is the process of putting a sequence of characters into a special format for transmission or storage purposes. Code Word The special format that represents each character is called as the code word Fixed Length Encoding fixed-length encoding that assigns to each symbol a bit string of the same length m Eg . ASCII codes Variable Length Encoding Variable-length encoding , which assigns codewords of different lengths to different symbols 3

4. Huffman Tree Coding Encoding In computer technology,  encoding  is the process of putting a sequence of characters into a special format for transmission or storage purposes. Code Word The special format that represents each character is called as the code word Fixed Length Encoding fixed-length encoding that assigns to each symbol a bit string of the same length m Eg . ASCII codes Variable Length Encoding Variable-length encoding , which assigns codewords of different lengths to different symbols 4

5. Huffman Tree Coding 5

6. Huffman Tree Coding Frequency of Occurrence of English Alphabets 6

7. Huffman Tree Coding Encoding In computer technology,  encoding  is the process of putting a sequence of characters into a special format for transmission or storage purposes. Code Word The special format that represents each character is called as the code word Fixed Length Encoding fixed-length encoding that assigns to each symbol a bit string of the same length m Eg . ASCII codes Variable Length Encoding Variable-length encoding , which assigns codewords of different lengths to different symbols 7

8. Huffman Tree Coding Variable-length encoding assigns codewords of different lengths to different symbols Eg . E 1 A 10 P 101 Q 1010 How to decode: 110101 ? How can we tell how many bits of an encoded text represent the first ? 8

9. Huffman Tree Coding We can limit ourselves to the so-called prefix-free (or simply prefix ) codes . In a prefix code, no codeword is a prefix of a codeword of another symbol. Eg . E 1 A 01 P 100 Q 101 How to decode: 10101101 ? 1 01 01 101  E A A Q 9

10. Huffman Tree Coding Consider the five-symbol alphabet { A , B, C, D, _ } with the following occurrence frequencies in a text made up of these symbols : Create a Huffman Tree and Generate the Huffman Code. 10

11. Huffman Tree Coding 11

12. Huffman Tree Coding 12

13. Huffman Tree Coding 13

14. Huffman Tree Coding 14

15. Huffman Tree Coding 15

16. Huffman Tree Coding 16

17. Huffman Tree Coding 17

18. Huffman Tree Coding 18

19. Huffman Tree Coding 19

20. Huffman Tree Coding 20

21. Huffman Tree Coding 21

22. Huffman Tree Coding 22

23. Huffman Tree Coding 23

24. Huffman Tree Coding 24

25. Huffman Tree Coding 25

26. Huffman Tree Coding 26

27. Huffman Tree Coding 27

28. Huffman Tree Coding 28 Character Code A B C D -

29. Huffman Tree Coding 29 Character Code A 11 B C D -

30. Huffman Tree Coding 30 Character Code A 11 B 100 C D -

31. Huffman Tree Coding 31 Character Code A 11 B 100 C 00 D -

32. Huffman Tree Coding 32 Character Code A 11 B 100 C 00 D 01 -

33. Huffman Tree Coding 33 Character Code A 11 B 100 C 00 D 01 - 101

34. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 34 Character Code A 11 B 100 C 00 D 01 - 101

35. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 35 Character Code A 11 B 100 C 00 D 01 - 101

36. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 11 36 Character Code A 11 B 100 C 00 D 01 - 101

37. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 11 01 37 Character Code A 11 B 100 C 00 D 01 - 101

38. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 11 01 101 38 Character Code A 11 B 100 C 00 D 01 - 101

39. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 11 01 101 00 39 Character Code A 11 B 100 C 00 D 01 - 101

40. Huffman Tree Coding Encode: “DAD CAB” D A D C A B 100 11 01 101 00 11 40 Character Code A 11 B 100 C 00 D 01 - 101

41. Huffman Tree Coding Encode: “DAD_CAB” D A D _ C A B 100 11 01 101 00 11 100 41 Character Code A 11 B 100 C 00 D 01 - 101

42. Huffman Tree Coding Decode: 10011011010011100 42 Character Code A 11 B 100 C 00 D 01 - 101

43. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B 43 Character Code A 11 B 100 C 00 D 01 - 101

44. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A 44 Character Code A 11 B 100 C 00 D 01 - 101

45. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A D 45 Character Code A 11 B 100 C 00 D 01 - 101

46. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A D _ 46 Character Code A 11 B 100 C 00 D 01 - 101

47. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A D _ C 47 Character Code A 11 B 100 C 00 D 01 - 101

48. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A D _ C A 48 Character Code A 11 B 100 C 00 D 01 - 101

49. Huffman Tree Coding Decode: 100 11 01 101 00 11 100 B A D _ C A B 49 Character Code A 11 B 100 C 00 D 01 - 101

50. Huffman Tree Coding 50