-
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비트
