Here is the Huffman code for the file PQueue.java.
Notice at the end that the average code length is close to the
entropy.
Display of Huffman coding tree
+---/: 0.0099, 000000 (step 31)
|
+---+---@: 0.0204, 00000 (step 40)
| |
| | +----: 0.0050, 0000010 (step 22) a hyphen
| | |
| +---+---@: 0.0105, 000001 (step 31)
| |
| | +---S: 0.0028, 00000110 (step 16)
| | |
| +---+---@: 0.0055, 0000011 (step 22)
| |
| +---,: 0.0028, 00000111 (step 16)
|
+---+---@: 0.0419, 0000 (step 48)
| |
| | +---p: 0.0105, 000010 (step 32)
| | |
| +---+---@: 0.0215, 00001 (step 40)
| |
| | +---": 0.0055, 0000110 (step 23)
| | |
| +---+---@: 0.0110, 000011 (step 32)
| |
| +---}: 0.0055, 0000111 (step 23)
|
+---+---@: 0.0855, 000 (step 54)
| |
| | +---d: 0.0215, 00010 (step 41)
| | |
| +---+---@: 0.0436, 0001 (step 48)
| |
| +---u: 0.0221, 00011 (step 41)
|
+---+---@: 0.1853, 00 (step 57)
| |
| | +---{: 0.0055, 0010000 (step 24)
| | |
| | +---+---@: 0.0116, 001000 (step 33)
| | | |
| | | | +---v: 0.0028, 00100010 (step 17)
| | | | |
| | | +---+---@: 0.0061, 0010001 (step 24)
| | | |
| | | | +---[: 0.0017, 001000110 (step 11)
| | | | |
| | | +---+---@: 0.0033, 00100011 (step 17)
| | | |
| | | | +---j: 0.0006, 0010001110 (step 4)
| | | | |
| | | +---+---@: 0.0017, 001000111 (step 11)
| | | |
| | | | +---I: 0.0006, 00100011110 (step 3)
| | | | |
| | | +---+---@: 0.0011, 0010001111 (step 4)
| | | |
| | | +---q: 0.0006, 00100011111 (step 3)
| | |
| | +---+---@: 0.0237, 00100 (step 42)
| | | |
| | | | +---L: 0.0061, 0010010 (step 25)
| | | | |
| | | +---+---@: 0.0121, 001001 (step 33)
| | | |
| | | +---y: 0.0061, 0010011 (step 25)
| | |
| | |
| | +---+---@: 0.0480, 0010 (step 49)
| | | |
| | | +---r: 0.0243, 00101 (step 42)
| | |
| +---+---@: 0.0998, 001 (step 54)
| |
| +---l: 0.0518, 0011 (step 49)
|
+---+---@: 0.4153, 0 (step 59)
| |
| | +---a: 0.0121, 010000 (step 34)
| | |
| | +---+---@: 0.0259, 01000 (step 43)
| | | |
| | | | +---g: 0.0066, 0100010 (step 26)
| | | | |
| | | +---+---@: 0.0138, 010001 (step 34)
| | | |
| | | | +---x: 0.0033, 01000110 (step 18)
| | | | |
| | | +---+---@: 0.0072, 0100011 (step 26)
| | | |
| | | +---0: 0.0039, 01000111 (step 18)
| | |
| | +---+---@: 0.0546, 0100 (step 50)
| | | |
| | | | +---h: 0.0143, 010010 (step 35)
| | | | |
| | | +---+---@: 0.0287, 01001 (step 43)
| | | |
| | | +---f: 0.0143, 010011 (step 35)
| | |
| | +---+---@: 0.1098, 010 (step 55)
| | | |
| | | +---i: 0.0552, 0101 (step 50)
| | |
| +---+---@: 0.2300, 01 (step 57)
| |
| | +---s: 0.0298, 01100 (step 44)
| | |
| | +---+---@: 0.0596, 0110 (step 51)
| | | |
| | | +---o: 0.0298, 01101 (step 44)
| | |
| +---+---@: 0.1202, 011 (step 55)
| |
| +---e: 0.0607, 0111 (step 51)
|
+---@: 1.0000,
|
| +---t: 0.0640, 1000 (step 52)
| |
| +---+---@: 0.1324, 100 (step 56)
| | |
| | | +---b: 0.0083, 1001000 (step 27)
| | | |
| | | +---+---@: 0.0165, 100100 (step 36)
| | | | |
| | | | | +---c: 0.0039, 10010010 (step 19)
| | | | | |
| | | | +---+---@: 0.0083, 1001001 (step 27)
| | | | |
| | | | | +---W: 0.0006, 10010011000 (step 2)
| | | | | |
| | | | | +---+---@: 0.0011, 1001001100 (step 5)
| | | | | | |
| | | | | | +---z: 0.0006, 10010011001 (step 2)
| | | | | |
| | | | | +---+---@: 0.0022, 100100110 (step 14)
| | | | | | |
| | | | | | | +---1: 0.0006, 10010011010 (step 1)
| | | | | | | |
| | | | | | +---+---@: 0.0011, 1001001101 (step 5)
| | | | | | |
| | | | | | +---R: 0.0006, 10010011011 (step 1)
| | | | | |
| | | | +---+---@: 0.0044, 10010011 (step 19)
| | | | |
| | | | +---+: 0.0022, 100100111 (step 14)
| | | |
| | | +---+---@: 0.0336, 10010 (step 45)
| | | | |
| | | | +---=: 0.0171, 100101 (step 36)
| | | |
| | +---+---@: 0.0684, 1001 (step 52)
| | |
| | +---\n: 0.0347, 10011 (step 45) actual newline
| |
| +---+---@: 0.2785, 10 (step 58)
| | |
| | | +---D: 0.0011, 1010000000 (step 7)
| | | |
| | | +---+---@: 0.0022, 101000000 (step 13)
| | | | |
| | | | +---\: 0.0011, 1010000001 (step 7)
| | | |
| | | +---+---@: 0.0044, 10100000 (step 20)
| | | | |
| | | | | +---!: 0.0011, 1010000010 (step 6)
| | | | | |
| | | | +---+---@: 0.0022, 101000001 (step 13)
| | | | |
| | | | +--->: 0.0011, 1010000011 (step 6)
| | | |
| | | +---+---@: 0.0088, 1010000 (step 28)
| | | | |
| | | | | +---k: 0.0011, 1010000100 (step 9)
| | | | | |
| | | | | +---+---@: 0.0022, 101000010 (step 12)
| | | | | | |
| | | | | | +---Q: 0.0011, 1010000101 (step 9)
| | | | | |
| | | | +---+---@: 0.0044, 10100001 (step 20)
| | | | |
| | | | | +---<: 0.0011, 1010000110 (step 8)
| | | | | |
| | | | +---+---@: 0.0022, 101000011 (step 12)
| | | | |
| | | | +---E: 0.0011, 1010000111 (step 8)
| | | |
| | | +---+---@: 0.0177, 101000 (step 37)
| | | | |
| | | | +---): 0.0088, 1010001 (step 28)
| | | |
| | | +---+---@: 0.0353, 10100 (step 46)
| | | | |
| | | | +---m: 0.0177, 101001 (step 37)
| | | |
| | | +---+---@: 0.0717, 1010 (step 53)
| | | | |
| | | | | +---(: 0.0088, 1010100 (step 29)
| | | | | |
| | | | | +---+---@: 0.0182, 101010 (step 38)
| | | | | | |
| | | | | | | +---:: 0.0044, 10101010 (step 21)
| | | | | | | |
| | | | | | +---+---@: 0.0094, 1010101 (step 29)
| | | | | | |
| | | | | | | +---T: 0.0022, 101010110 (step 15)
| | | | | | | |
| | | | | | +---+---@: 0.0050, 10101011 (step 21)
| | | | | | |
| | | | | | | +---P: 0.0011, 1010101110 (step 10)
| | | | | | | |
| | | | | | +---+---@: 0.0028, 101010111 (step 15)
| | | | | | |
| | | | | | +---]: 0.0017, 1010101111 (step 10)
| | | | | |
| | | | +---+---@: 0.0364, 10101 (step 46)
| | | | |
| | | | +---.: 0.0182, 101011 (step 38)
| | | |
| | +---+---@: 0.1462, 101 (step 56)
| | |
| | | +---n: 0.0370, 10110 (step 47)
| | | |
| | +---+---@: 0.0745, 1011 (step 53)
| | |
| | | +---w: 0.0094, 1011100 (step 30)
| | | |
| | | +---+---@: 0.0188, 101110 (step 39)
| | | | |
| | | | +---N: 0.0094, 1011101 (step 30)
| | | |
| | +---+---@: 0.0375, 10111 (step 47)
| | |
| | +---;: 0.0188, 101111 (step 39)
| |
+---+---@: 0.5847, 1 (step 59)
|
+--- : 0.3061, 11 (step 58) a blank
Dump of Table ----->
Size: 60
Entry 0. Symbol: /, Weight: 0.009928295642581356, Representation: 000000
Entry 1. Symbol: , Weight: 0.30612244897959184, Representation: 11
Entry 2. Symbol: P, Weight: 0.0011031439602868175, Representation: 1010101110
Entry 3. Symbol: Q, Weight: 0.0011031439602868175, Representation: 1010000101
Entry 4. Symbol: u, Weight: 0.02206287920573635, Representation: 00011
Entry 5. Symbol: e, Weight: 0.06067291781577496, Representation: 0111
Entry 6. Symbol: ., Weight: 0.01820187534473249, Representation: 101011
Entry 7. Symbol: j, Weight: 5.515719801434088E-4, Representation: 0010001110
Entry 8. Symbol: a, Weight: 0.012134583563154992, Representation: 010000
Entry 9. Symbol: v, Weight: 0.0027578599007170436, Representation: 00100010
Entry 10. Symbol: :, Weight: 0.00441257584114727, Representation: 10101010
Entry 11. Symbol: i, Weight: 0.05515719801434087, Representation: 0101
Entry 12. Symbol: m, Weight: 0.01765030336458908, Representation: 101001
Entry 13. Symbol: p, Weight: 0.010479867622724766, Representation: 000010
Entry 14. Symbol: l, Weight: 0.05184776613348042, Representation: 0011
Entry 15. Symbol: n, Weight: 0.03695532266960838, Representation: 10110
Entry 16. Symbol: t, Weight: 0.06398234969663541, Representation: 1000
Entry 17. Symbol: r, Weight: 0.024269167126309985, Representation: 00101
Entry 18. Symbol: o, Weight: 0.02978488692774407, Representation: 01101
Entry 19. Symbol: y, Weight: 0.006067291781577496, Representation: 0010011
Entry 20. Symbol: q, Weight: 5.515719801434088E-4, Representation: 00100011111
Entry 21. Symbol: s, Weight: 0.02978488692774407, Representation: 01100
Entry 22. Symbol: k, Weight: 0.0011031439602868175, Representation: 1010000100
Entry 23. Symbol: d, Weight: 0.02151130722559294, Representation: 00010
Entry 24. Symbol: f, Weight: 0.014340871483728626, Representation: 010011
Entry 25. Symbol: \n, Weight: 0.03474903474903475, Representation: 10011
Entry 26. Symbol: I, Weight: 5.515719801434088E-4, Representation: 00100011110
Entry 27. Symbol: z, Weight: 5.515719801434088E-4, Representation: 10010011001
Entry 28. Symbol: g, Weight: 0.006618863761720904, Representation: 0100010
Entry 29. Symbol: c, Weight: 0.003861003861003861, Representation: 10010010
Entry 30. Symbol: {, Weight: 0.005515719801434087, Representation: 0010000
Entry 31. Symbol: L, Weight: 0.006067291781577496, Representation: 0010010
Entry 32. Symbol: N, Weight: 0.009376723662437948, Representation: 1011101
Entry 33. Symbol: =, Weight: 0.01709873138444567, Representation: 100101
Entry 34. Symbol: ;, Weight: 0.018753447324875896, Representation: 101111
Entry 35. Symbol: h, Weight: 0.014340871483728626, Representation: 010010
Entry 36. Symbol: w, Weight: 0.009376723662437948, Representation: 1011100
Entry 37. Symbol: b, Weight: 0.00827357970215113, Representation: 1001000
Entry 38. Symbol: (, Weight: 0.00882515168229454, Representation: 1010100
Entry 39. Symbol: T, Weight: 0.002206287920573635, Representation: 101010110
Entry 40. Symbol: ), Weight: 0.00882515168229454, Representation: 1010001
Entry 41. Symbol: x, Weight: 0.003309431880860452, Representation: 01000110
Entry 42. Symbol: }, Weight: 0.005515719801434087, Representation: 0000111
Entry 43. Symbol: E, Weight: 0.0011031439602868175, Representation: 1010000111
Entry 44. Symbol: [, Weight: 0.001654715940430226, Representation: 001000110
Entry 45. Symbol: ], Weight: 0.001654715940430226, Representation: 1010101111
Entry 46. Symbol: ,, Weight: 0.0027578599007170436, Representation: 00000111
Entry 47. Symbol: 0, Weight: 0.003861003861003861, Representation: 01000111
Entry 48. Symbol: <, Weight: 0.0011031439602868175, Representation: 1010000110
Entry 49. Symbol: +, Weight: 0.002206287920573635, Representation: 100100111
Entry 50. Symbol: ", Weight: 0.005515719801434087, Representation: 0000110
Entry 51. Symbol: S, Weight: 0.0027578599007170436, Representation: 00000110
Entry 52. Symbol: \, Weight: 0.0011031439602868175, Representation: 1010000001
Entry 53. Symbol: D, Weight: 0.0011031439602868175, Representation: 1010000000
Entry 54. Symbol: -, Weight: 0.004964147821290678, Representation: 0000010
Entry 55. Symbol: >, Weight: 0.0011031439602868175, Representation: 1010000011
Entry 56. Symbol: !, Weight: 0.0011031439602868175, Representation: 1010000010
Entry 57. Symbol: W, Weight: 5.515719801434088E-4, Representation: 10010011000
Entry 58. Symbol: R, Weight: 5.515719801434088E-4, Representation: 10010011011
Entry 59. Symbol: 1, Weight: 5.515719801434088E-4, Representation: 10010011010
----> End Dump of Table
Entropy: 4.300902477574152, Ave. Code Length: 4.328736900165471