HW No. 2
1. 빈도수가 다음과 같을 때 Huffman code를 생성하시오.
colon: 100
space: 605
newline: 100
comma: 705
0: 431
1: 242
2: 176
3: 59
4: 185
5: 250
6: 174
7: 199
8: 205
9: 217
풀이 → 위 그림은 주어진 빈도수로 허프만트리를 그린 것이다. (계산틀렸다. 1014->1214, 1937->2137, 3448->3648....크흑...)
빈도수 대로 나열하여, 가변길이 코드를 부여하면
|
문자 |
빈도수 |
가변길이코드 |
|
comma |
705 |
00 |
|
space |
605 |
110 |
|
0 |
431 |
100 |
|
5 |
250 |
1011 |
|
1 |
242 |
1010 |
|
9 |
217 |
0111 |
|
8 |
205 |
0110 |
|
7 |
199 |
0101 |
|
4 |
185 |
0100 |
|
2 |
176 |
11111 |
|
6 |
174 |
11110 |
|
colon |
100 |
11100 |
|
newline |
100 |
111011 |
|
3 |
59 |
111010 |
2. 다음 문자를 포함하는 파일을 Lempel-Ziv 사용하여 부호화(숫자는 이진으로 표시) 하시오.
1) "aaabbcbcdddeab"
인덱스:0 1 2 3 4 5 6 7 8
0|a|aa|b|bc|bcd|d|de|ab
인덱스: 1 2 3 4 5 6 7 8
0a|1a|0b|3c|4d|0d|6e|1b
<a>1<a>00<b>11<c>100<d>000<d>110<e>001<b>
2) "I AM SAM. SAM I AM."
인덱스:0 1 2 3 4 5 6 7 8 9 10 11
0|I| |A|M| S|AM|.| SA|M |I |AM.
인덱스: 1 2 3 4 5 6 7 8 9 10 11
|0I|0 |0A|0M|2S|3M|0.|5A|4 |1 |6.
<I>0< >00<A>00<M>010<S>011<M>000<.>101<A>1000< >0001< >0110<.>
3. 1) 다음의 Lempel-Ziv로 부호화된 파일을 decoding하시오.
|0M|0A|0K|0E|0 |0L|2K|4 |0F|7E|
MAKE LAKE FAKE
2) 원래 메시지의 비트 수
14*8 = 112비트
3)부호화된 메시지의 비트 수
(10*8) + (0+1+2*2+3*4+4*2) = 105비트