เช
เชญเซเชฏเชพเชธเชเซเชฐเชฎเชจเซ เชถเชฐเซเชเชค เชชเชนเซเชฒเชพเช
เชนเชซเชฎเซเชจ เชเซเชกเชฟเชเช เช เชกเซเชเชพ เชเชฎเซเชชเซเชฐเซเชถเชจ เชเชฒเซเชเซเชฐเชฟเชงเชฎ เชเซ เชเซ เชซเชพเชเชฒ เชเชฎเซเชชเซเชฐเซเชถเชจเชจเซ เชฎเซเชณเชญเซเชค เชตเชฟเชเชพเชฐ เชฌเชจเชพเชตเซ เชเซ. เช เชฒเซเชเชฎเชพเช, เช เชฎเซ เชจเชฟเชถเซเชเชฟเชค เช เชจเซ เชเชฒ เชฒเชเชฌเชพเชเชจเชพ เชเชจเซเชเซเชกเชฟเชเช, เชตเชฟเชถเชฟเชทเซเช เชฐเซเชคเซ เชกเซเชเซเชก เชเชฐเซ เชถเชเชพเชฏ เชคเซเชตเชพ เชเซเชกเซเชธ, เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎเซ เช เชจเซ เชนเชซเชฎเซเชจ เชเซเชฐเซ เชฌเชจเชพเชตเชตเชพ เชตเชฟเชถเซ เชตเชพเชค เชเชฐเซเชถเซเช.
เชเชชเชฃเซ เชเชพเชฃเซเช เชเซเช เชเซ เชฆเชฐเซเช เช
เชเซเชทเชฐ 0 เช
เชจเซ 1 เชจเชพ เชเซเชฐเชฎ เชคเชฐเซเชเซ เชธเชเชเซเชฐเชนเชฟเชค เชฅเชพเชฏ เชเซ เช
เชจเซ 8 เชฌเชฟเชเซเชธ เชฒเซ เชเซ. เชเชจเซ เชซเชฟเชเซเชธเซเชก เชฒเซเชจเซเชฅ เชเชจเซเชเซเชกเชฟเชเช เชเชนเซเชตเชพเชฎเชพเช เชเชตเซ เชเซ เชเชพเชฐเชฃ เชเซ เชฆเชฐเซเช เช
เชเซเชทเชฐ เชธเซเชเซเชฐ เชเชฐเชตเชพ เชฎเชพเชเซ เชธเชฎเชพเชจ เชจเชฟเชถเซเชเชฟเชค เชธเชเชเซเชฏเชพเชฎเชพเช เชฌเชฟเชเซเชธเชจเซ เชเชชเชฏเซเช เชเชฐเซ เชเซ.
เชเชพเชฒเซ เชเชนเซเช เชเซ เช เชฎเชพเชฐเซ เชชเชพเชธเซ เชเช เชเซเชเซเชธเซเช เชเซ. เชเช เช เชเซเชทเชฐเชจเซ เชธเชเชเซเชฐเชนเชฟเชค เชเชฐเชตเชพ เชฎเชพเชเซ เชเชฐเซเชฐเซ เชเชเซเชฏเชพเชจเซ เชฎเชพเชคเซเชฐเชพเชจเซ เชเชชเชฃเซ เชเซเชตเซ เชฐเซเชคเซ เชเชเชพเชกเซ เชถเชเซเช?
เชฎเซเชเซเชฏ เชตเชฟเชเชพเชฐ เชเชฒ เชฒเชเชฌเชพเช เชเชจเซเชเซเชกเชฟเชเช เชเซ. เช
เชฎเซ เช เชนเชเซเชเชคเชจเซ เชเชชเชฏเซเช เชเชฐเซ เชถเชเซเช เชเซเช เชเซ เชเซเชเซเชธเซเชเชฎเชพเช เชเซเชเชฒเชพเช เช
เชเซเชทเชฐเซ เช
เชจเซเชฏ เชเชฐเชคเชพ เชตเชงเซ เชตเชเชค เชเชตเซ เชเซ (
เชเซเชตเซ เชฐเซเชคเซ, เชฌเชฟเชเซเชธเชจเซ เชเซเชฐเชฎ เชเชพเชฃเซเชจเซ, เชคเซเชจเซ เช เชธเซเชชเชทเซเช เชฐเซเชคเซ เชกเซเชเซเชก เชเชฐเชตเซเช?
เชฒเซเชเซ เชงเซเชฏเชพเชจเชฎเชพเช เชฒเซ "เช เชฌเชเชกเชพเชฌ". เชคเซเชฎเชพเช 8 เช เชเซเชทเชฐเซ เชเซ, เช เชจเซ เชเซเชฏเชพเชฐเซ เชจเชฟเชถเซเชเชฟเชค เชฒเชเชฌเชพเชเชจเซ เชเชจเซเชเซเชกเชฟเชเช เชเชฐเชตเชพเชฎเชพเช เชเชตเซ เชเซ, เชคเซเชฏเชพเชฐเซ เชคเซเชจเซ เชธเชเชเซเชฐเชนเชฟเชค เชเชฐเชตเชพ เชฎเชพเชเซ 64 เชฌเชฟเชเซเชธเชจเซ เชเชฐเซเชฐ เชชเชกเชถเซ. เชจเซเชเชง เชเชฐเซ เชเซ เชชเซเชฐเชคเซเช เชเชตเชฐเซเชคเชจ "a", "b", "c" ะธ "เชกเซ" เช เชจเซเชเซเชฐเชฎเซ 4, 2, 1, 1 เชฌเชฐเชพเชฌเชฐ. เชเชพเชฒเซ เชเชฒเซเชชเชจเชพ เชเชฐเชตเชพเชจเซ เชชเซเชฐเชฏเชพเชธ เชเชฐเซเช "เช เชฌเชเชกเชพเชฌ" เชเชเชพ เชฌเชฟเชเซเชธ, เช เชนเชเซเชเชคเชจเซ เชเชชเชฏเซเช เชเชฐเซเชจเซ "เชชเซเชฐเชคเชฟ" เชเชฐเชคเชพเช เชตเชงเซ เชตเชพเชฐเชเชตเชพเชฐ เชฅเชพเชฏ เชเซ "เชฌเซ"เช เชจเซ "เชฌเซ" เชเชฐเชคเชพเช เชตเชงเซ เชตเชพเชฐเชเชตเชพเชฐ เชฅเชพเชฏ เชเซ "c" ะธ "เชกเซ". เชเชพเชฒเซ เชเซเชกเชฟเชเช เชฆเซเชตเชพเชฐเชพ เชถเชฐเซ เชเชฐเซเช "เชชเซเชฐเชคเชฟ" 0 เชจเซ เชฌเชฐเชพเชฌเชฐ เชเช เชฌเซเช เชธเชพเชฅเซ, "เชฌเซ" เช เชฎเซ เชฌเซ-เชฌเซเช เชเซเชก 11 เชธเซเชเชชเซเชถเซเช, เช เชจเซ เชคเซเชฐเชฃ เชฌเชฟเชเซเชธ 100 เช เชจเซ 011 เชจเซ เชเชชเชฏเซเช เชเชฐเซเชจเซ เช เชฎเซ เชเชจเซเชเซเชก เชเชฐเซเชถเซเช "c" ะธ "เชกเซ".
เชชเชฐเชฟเชฃเชพเชฎเซ, เช เชฎเชจเซ เชฎเชณเชถเซ:
a
0
b
11
c
100
d
011
เชคเซเชฅเซ เชฐเซเชเชพ "เช เชฌเชเชกเชพเชฌ" เชคเชฐเซเชเซ เชเชจเซเชเซเชก เชเชฐเซเชถเซเช 00110100011011 (0|0|11|0|100|011|0|11)เชเชชเชฐเชจเชพ เชเซเชกเชจเซ เชเชชเชฏเซเช เชเชฐเซเชจเซ. เชเซ เชเซ, เชฎเซเชเซเชฏ เชธเชฎเชธเซเชฏเชพ เชกเซเชเซเชกเชฟเชเชเชฎเชพเช เชนเชถเซ. เชเซเชฏเชพเชฐเซ เชเชชเชฃเซ เชถเชฌเซเชฆเชฎเชพเชณเชพเชจเซ เชกเซเชเซเชก เชเชฐเชตเชพเชจเซ เชชเซเชฐเชฏเชพเชธ เชเชฐเซเช เชเซเช 00110100011011, เช เชฎเชจเซ เชเช เช เชธเซเชชเชทเซเช เชชเชฐเชฟเชฃเชพเชฎ เชฎเชณเซ เชเซ, เชเชพเชฐเชฃ เชเซ เชคเซ เช เชฐเซเชคเซ เชฐเชเซ เชเชฐเซ เชถเชเชพเชฏ เชเซ:
0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
...
เช
เชจเซ เชคเซเชฅเซ เชชเชฐ
เช เช เชธเซเชชเชทเซเชเชคเชพเชจเซ เชเชพเชณเชตเชพ เชฎเชพเชเซ, เชเชชเชฃเซ เชเชพเชคเชฐเซ เชเชฐเชตเซ เชเซเชเช เชเซ เชเชชเชฃเซเช เชเชจเซเชเซเชกเชฟเชเช เชเชตเชพ เชเซเชฏเชพเชฒเชจเซ เชธเชเชคเซเชทเซ เชเซ เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎ, เชเซ เชฌเชฆเชฒเชพเชฎเชพเช เชธเซเชเชตเซ เชเซ เชเซ เชเซเชกเซเชธ เชซเชเซเชค เชเช เช เชจเชจเซเชฏ เชฐเซเชคเซ เชกเซเชเซเชก เชเชฐเซ เชถเชเชพเชฏ เชเซ. เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎ เชธเซเชจเชฟเชถเซเชเชฟเชค เชเชฐเซ เชเซ เชเซ เชเซเช เชเซเชก เชฌเซเชเชพเชจเซ เชเชชเชธเชฐเซเช เชจเชฅเซ. เชเซเชก เชฆเซเชตเชพเชฐเชพ, เช เชฎเชพเชฐเซ เชฎเชคเชฒเชฌ เชเซเชเซเชเชธ เช เชเซเชทเชฐเชจเซ เชฆเชฐเซเชถเชพเชตเชตเชพ เชฎเชพเชเซ เชเชชเชฏเซเชเชฎเชพเช เชฒเซเชตเชพเชคเชพ เชฌเชฟเชเซเชธ. เชเชชเชฐเชจเชพ เชเชฆเชพเชนเชฐเชฃเชฎเชพเช 0 เชเชชเชธเชฐเซเช เชเซ 011, เชเซ เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎเชจเซเช เชเชฒเซเชฒเชเชเชจ เชเชฐเซ เชเซ. เชคเซเชฅเซ, เชเซ เช เชฎเชพเชฐเชพ เชเซเชกเซเชธ เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎเชจเซ เชธเชเชคเซเชทเซ เชเซ, เชคเซ เช เชฎเซ เช เชจเชจเซเชฏ เชฐเซเชคเซ เชกเซเชเซเชก เชเชฐเซ เชถเชเซเช เชเซเช (เช เชจเซ เชเชฒเชเซเช).
เชเชพเชฒเซ เชเชชเชฐเชจเชพ เชเชฆเชพเชนเชฐเชฃเชจเซ เชซเชฐเซ เชฎเซเชฒเชพเชเชพเชค เชเชฐเซเช. เช เชตเชเชคเซ เชเชชเชฃเซ เชชเซเชฐเชคเซเชเซ เชฎเชพเชเซ เชธเซเชเชชเซเชถเซเช "a", "b", "c" ะธ "เชกเซ" เชเซเชก เชเซ เชเซ เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎเชจเซ เชธเชเชคเซเชทเซ เชเซ.
a
0
b
10
c
110
d
111
เช เชเชจเซเชเซเชกเชฟเชเช เชธเชพเชฅเซ, เชถเชฌเซเชฆเชฎเชพเชณเชพ "เช เชฌเชเชกเชพเชฌ" เชคเชฐเซเชเซ เชเชจเซเชเซเชก เชเชฐเชตเชพเชฎเชพเช เชเชตเชถเซ 00100100011010 (0|0|10|0|100|011|0|10). เช เชจเซ เช เชนเซเช 00100100011010 เช เชฎเซ เชชเชนเซเชฒเชพเชฅเซ เช เช เชธเซเชชเชทเซเชเชชเชฃเซ เชกเซเชเซเชก เชเชฐเซ เชถเชเซเชถเซเช เช เชจเซ เช เชฎเชพเชฐเซ เชฎเซเชณ เชธเซเชเซเชฐเชฟเชเช เชชเชฐ เชชเชพเชเชพ เชเชตเซเชถเซเช "เช เชฌเชเชกเชพเชฌ".
เชนเชซเชฎเซเชจ เชเซเชกเชฟเชเช
เชนเชตเซ เชเซเชฏเชพเชฐเซ เชเชชเชฃเซ เชตเซเชฐเชฟเชฏเซเชฌเชฒ เชฒเซเชจเซเชฅ เชเชจเซเชเซเชกเชฟเชเช เช เชจเซ เชเชชเชธเชฐเซเช เชจเชฟเชฏเชฎ เชธเชพเชฅเซ เชเชพเชฎ เชเชฐเซเชฏเซเช เชเซ, เชเชพเชฒเซ เชนเชซเชฎเซเชจ เชเชจเซเชเซเชกเชฟเชเช เชตเชฟเชถเซ เชตเชพเชค เชเชฐเซเช.
เชชเชฆเซเชงเชคเชฟ เชฆเซเชตเชฟเชธเชเชเซ เชตเซเชเซเชทเซเชจเซ เชฐเชเชจเชพ เชชเชฐ เชเชงเชพเชฐเชฟเชค เชเซ. เชคเซเชฎเชพเช, เชจเซเชก เชเซเชฏเชพเช เชคเซ เช เชเชคเชฟเชฎ เช เชฅเชตเชพ เชเชเชคเชฐเชฟเช เชนเซเช เชถเชเซ เชเซ. เชถเชฐเซเชเชคเชฎเชพเช, เชคเชฎเชพเชฎ เชเชพเชเช เซเชจเซ เชชเชพเชเชฆเชกเชพ (เชเชฐเซเชฎเชฟเชจเชฒ) เชเชฃเชตเชพเชฎเชพเช เชเชตเซ เชเซ, เชเซ เชชเซเชฐเชคเซเช เชชเซเชคเซ เช เชจเซ เชคเซเชจเซเช เชตเชเชจ (เชเชเชฒเซ โโโโเชเซ, เชเชเชจเชพเชจเซ เชเชตเชฐเซเชคเชจ) เชฆเชฐเซเชถเชพเชตเซ เชเซ. เชเชเชคเชฐเชฟเช เชเชพเชเช เซเชฎเชพเช เชชเชพเชคเซเชฐเชจเซเช เชตเชเชจ เชนเซเชฏ เชเซ เช เชจเซ เชคเซ เชฌเซ เชตเชเชถเช เชเชพเชเช เซเชจเซ เชธเชเชฆเชฐเซเชญ เชเชชเซ เชเซ. เชธเชพเชฎเชพเชจเซเชฏ เชเชฐเชพเชฐ เชฆเซเชตเชพเชฐเชพ, เชฌเซเช "0" เชกเชพเชฌเซ เชถเชพเชเชพเชจเซ เช เชจเซเชธเชฐเซเชจเซ เชฐเชเซ เชเชฐเซ เชเซ, เช เชจเซ "1" - เชเชฎเชฃเซ เชฌเชพเชเซเช. เชธเชเชชเซเชฐเซเชฃ เชตเซเชเซเชทเชฎเชพเช N เชชเชพเชเชฆเชกเชพ เช เชจเซ N-1 เชเชเชคเชฐเชฟเช เชเชพเชเช เซ. เชเชตเซ เชญเชฒเชพเชฎเชฃ เชเชฐเชตเชพเชฎเชพเช เชเชตเซ เชเซ เชเซ เชนเชซเชฎเซเชจ เชเซเชฐเซ เชฌเชจเชพเชตเชคเซ เชตเชเชคเซ, เชถเซเชฐเซเชทเซเช เชฒเชเชฌเชพเชเชจเชพ เชเซเชกเซเชธ เชฎเซเชณเชตเชตเชพ เชฎเชพเชเซ เชฌเชฟเชจเชเชชเชฏเซเชเซ เชชเซเชฐเชคเซเชเซเชจเซ เชเชพเชขเซ เชจเชพเชเชตเชพเชฎเชพเช เชเชตเซ.
เชนเชซเชฎเซเชจ เชเซเชฐเซ เชฌเชจเชพเชตเชตเชพ เชฎเชพเชเซ เช เชฎเซ เชชเซเชฐเชพเชงเชพเชจเซเชฏเชคเชพ เชเชคเชพเชฐเชจเซ เชเชชเชฏเซเช เชเชฐเซเชถเซเช, เชเซเชฏเชพเช เชธเซเชฅเซ เชเชเซ เชเชตเชฐเซเชคเชจ เชงเชฐเชพเชตเชคเชพ เชจเซเชกเชจเซ เชธเซเชฅเซ เชตเชงเซ เชชเซเชฐเชพเชงเชพเชจเซเชฏ เชเชชเชตเชพเชฎเชพเช เชเชตเชถเซ. เชฌเชพเชเชงเชเชพเชฎเชจเชพ เชชเชเชฒเชพเช เชจเซเชเซ เชตเชฐเซเชฃเชตเซเชฒ เชเซ:
- เชฆเชฐเซเช เช เชเซเชทเชฐ เชฎเชพเชเซ เชฒเซเชซ เชจเซเชก เชฌเชจเชพเชตเซ เช เชจเซ เชคเซเชฎเชจเซ เชชเซเชฐเชพเชฅเชฎเชฟเชเชคเชพ เชเชคเชพเชฐเชฎเชพเช เชเชฎเซเชฐเซ.
- เชเซเชฏเชพเชฐเซ เชเชคเชพเชฐเชฎเชพเช เชเช เชเชฐเชคเชพเช เชตเชงเซ เชถเซเช เชนเซเชฏ, เชคเซเชฏเชพเชฐเซ เชจเซเชเซเชจเชพ เชเชฐเซ:
- เชเชคเชพเชฐเชฎเชพเชเชฅเซ เชธเชฐเซเชตเซเชเซเช เช เชเซเชฐเชคเชพ (เชธเซเชฅเซ เชเชเซ เชเชตเชฐเซเชคเชจ) เชธเชพเชฅเซ เชฌเซ เชเชพเชเช เซ เชฆเซเชฐ เชเชฐเซ;
- เชเช เชจเชตเซ เชเชเชคเชฐเชฟเช เชจเซเชก เชฌเชจเชพเชตเซ, เชเซเชฏเชพเช เช เชฌเซ เชเชพเชเช เซ เชฌเชพเชณเชเซ เชนเชถเซ, เช เชจเซ เชเชเชจเชพเชจเซ เชเชตเชฐเซเชคเชจ เช เชฌเซ เชเชพเชเช เซเชจเซ เชซเซเชฐเซเชเซเชตเชจเซเชธเซเชจเชพ เชธเชฐเชตเชพเชณเชพ เชเซเชเชฒเซ เชนเชถเซ.
- เชชเซเชฐเชพเชงเชพเชจเซเชฏเชคเชพ เชเชคเชพเชฐเชฎเชพเช เชเช เชจเชตเซ เชจเซเชก เชเชฎเซเชฐเซ.
- เชเชเชฎเชพเชคเซเชฐ เชฌเชพเชเซเชจเซ เชจเซเชก เชฐเซเช เชนเชถเซ, เช เชจเซ เช เชตเซเชเซเชทเชจเซเช เชฌเชพเชเชงเชเชพเชฎ เชชเซเชฐเซเชฃ เชเชฐเชถเซ.
เชเชฒเซเชชเชจเชพ เชเชฐเซ เชเซ เชเชชเชฃเซ เชชเชพเชธเซ เช เชฎเซเช เชฒเชเชพเชฃ เชเซ เชเซเชฎเชพเช เชฎเชพเชคเซเชฐ เช เชเซเชทเชฐเซเชจเซ เชธเชฎเชพเชตเซเชถ เชฅเชพเชฏ เชเซ "เช เชฌเซ เชธเซ เชกเซ" ะธ "เช เชจเซ", เช เชจเซ เชคเซเชฎเชจเซ เชเชเชจเชพเชจเซ เชเชตเชฐเซเชคเชจ เช เชจเซเชเซเชฐเชฎเซ 15, 7, 6, 6 เช เชจเซ 5 เชเซ. เชจเซเชเซ เชเชฟเชคเซเชฐเซ เชเซ เชเซ เช เชฒเซเชเซเชฐเชฟเชงเชฎเชจเชพ เชชเชเชฒเชพเชเชจเซ เชชเซเชฐเชคเชฟเชฌเชฟเชเชฌเชฟเชค เชเชฐเซ เชเซ.
เชฐเซเชเชฅเซ เชเซเชเชชเชฃ เช
เชเชคเชฟเชฎ เชจเซเชก เชธเซเชงเซเชจเซ เชฎเชพเชฐเซเช เชคเซ เช
เชเชคเชฟเชฎ เชจเซเชก เชธเชพเชฅเซ เชธเชเชเชณเชพเชฏเซเชฒ เช
เชเซเชทเชฐเชจเซ เช
เชจเซเชฐเซเชช เชถเซเชฐเซเชทเซเช เชเชชเชธเชฐเซเช เชเซเชก (เชเซ เชนเชซเชฎเซเชจ เชเซเชก เชคเชฐเซเชเซ เชชเชฃ เชเชณเชเชพเชฏ เชเซ) เชธเชเชเซเชฐเชนเชฟเชค เชเชฐเชถเซ.
เชนเชซเชฎเซเชจ เชตเซเชเซเชท
เชจเซเชเซ เชคเชฎเชจเซ C++ เช เชจเซ Java เชฎเชพเช เชนเชซเชฎเซเชจ เชเชฎเซเชชเซเชฐเซเชถเชจ เช เชฒเซเชเซเชฐเชฟเชงเชฎเชจเซ เช เชฎเชฒ เชเซเชตเชพ เชฎเชณเชถเซ:
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :n" << 'n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << 'n';
}
cout << "nOriginal string was :n" << text << 'n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "nEncoded string is :n" << str << 'n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "nDecoded string is: n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> freq = new HashMap<>();
for (int i = 0 ; i < text.length(); i++) {
if (!freq.containsKey(text.charAt(i))) {
freq.put(text.charAt(i), 0);
}
freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node left = pq.poll();
Node right = pq.poll();
// Create a new internal node with these two nodes as children
// and with frequency equal to the sum of the two nodes
// frequencies. Add the new node to the priority queue.
int sum = left.freq + right.freq;
pq.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}
เชเชฆเชพเชนเชฐเชฃ: เชเชจเชชเซเช เชธเซเชเซเชฐเชฟเชเช เชฆเซเชตเชพเชฐเชพ เชเชชเชฏเซเชเชฎเชพเช เชฒเซเชตเชพเชคเซ เชฎเซเชฎเชฐเซ 47*8 = 376 เชฌเชฟเชเซเชธ เชเซ เช เชจเซ เชเชจเซเชเซเชกเซเชก เชธเซเชเซเชฐเชฟเชเช เชฎเชพเชคเซเชฐ 194 เชฌเชฟเชเซเชธ เชเซ เชเชเชฒเซ เชเซ. เชกเซเชเชพ เชฒเชเชญเช 48% เชฆเซเชตเชพเชฐเชพ เชธเชเชเซเชเชฟเชค เชเซ. เชเชชเชฐเชจเชพ C++ เชชเซเชฐเซเชเซเชฐเชพเชฎเชฎเชพเช, เช เชฎเซ เชชเซเชฐเซเชเซเชฐเชพเชฎเชจเซ เชตเชพเชเชเซ เชถเชเชพเชฏ เชคเซ เชฎเชพเชเซ เชเชจเซเชเซเชกเซเชก เชธเซเชเซเชฐเชฟเชเช เชธเซเชเซเชฐ เชเชฐเชตเชพ เชฎเชพเชเซ เชธเซเชเซเชฐเชฟเชเช เชเซเชฒเชพเชธเชจเซ เชเชชเชฏเซเช เชเชฐเซเช เชเซเช.
เชเชพเชฐเชฃ เชเซ เชเชพเชฐเซเชฏเชเซเชทเชฎ เชชเซเชฐเชพเชฏเซเชฐเชฟเชเซ เชเชคเชพเชฐ เชกเซเชเชพ เชธเซเชเซเชฐเชเซเชเชฐเชจเซ เชชเซเชฐเชคเชฟ เชจเชฟเชตเซเชถเชจเซ เชเชฐเซเชฐ เชเซ O(เชฒเซเช(N)) เชธเชฎเชฏ, เชชเชฐเชเชคเซ เชธเชพเชฅเซ เชธเชเชชเซเชฐเซเชฃ เชฆเซเชตเชฟเชธเชเชเซ เชตเซเชเซเชทเชฎเชพเช N เชชเชพเชเชฆเชกเชพ เชนเชพเชเชฐ 2N-1 เชจเซเชกเซเชธ, เช เชจเซ เชนเชซเชฎเซเชจ เชเซเชฐเซ เช เชธเชเชชเซเชฐเซเชฃ เชฌเชพเชเชจเชฐเซ เชเซเชฐเซ เชเซ, เชชเชเซ เชเชฒเซเชเซเชฐเชฟเชงเชฎ เช เชเชฆเชฐ เชเชพเชฒเซ เชเซ O(Nlog(N)) เชธเชฎเชฏ, เชเซเชฏเชพเช N - เชชเชพเชคเซเชฐเซ.
เชธเซเชคเซเชฐเซเชคเซ:
เชธเซเชฐเซเชธ: www.habr.com