알고리즘 LCS, 허프만코드에 대한 분석

소개글

알고리즘 LCS, 허프만코드에 대한 분석에 대한 보고서 자료입니다.

목차

Introduction

Longest Common Subseqence(LCS)의 정의

LCS의 해결방안 모색

◆ 동적 프로그래밍의 4단계

∎Optimal Substructure

∎Overlapping Subproblems

◆ 접두사

◆ 접두사 개념을 통해 얻을 수 있는 몇 가지 중요한 성질들

LCS - Length(X, Y) 의사 코드

conclusion

Huffman Codes

허프만코드의 정의

⋇Greedy algorithm이란?

Huffman 부호화

Huffman 압축기법

허프만코드 생성 방법

Huffman(C) 의사 코드

■ 초기 코드의 Binary Tree 표현

■ 허프만코드 산출을 위한 이진트리

■ 허프만 알고리즘의 수행시간 분석

본문내용

되지만 허프만 압축기법에 의해 가장 자주 나타나는 A라는 문자에는‘0’, 즉 1비트의 부호어가, 그리고 가장 자주 나타나지 않는 문자인 H에는‘111111’이라는 6비트의 부호어가 할당되어 있다. 따라서 압축전과 압축후의 전체 데이터길이의 비율을 계산한 결과 압축에 의해 20%의 축소효과를 가져왔음을 알 수 있다.
허프만 압축기법을 적용한 압축 방식으로는 현재 팩시밀리 통신의 표준으로서 권고되고 있는 수정 허프만부호가 있다.
팩시밀리 통신은 앞에서도 언급한 바와 같이 이미지정보이므로 서류의 한 줄당 최소 1728비트의 데이터가 필요하게 된다. 수정 허프만 기법은 각 줄당 1728개에 달하는 데이터가 모두 흑(‘1’ 비트)과 백(‘0’ 비트)으로 이루어져 있으며 또 이미지정보의 경우 흑과 백의 분포가 상호연관되어 있는 점에 착안, 각 줄당 흑과 백의 반복개수마다 앞의 허프만 기법을 적용해 압축 부호어를 구함으로써 데이터를 축소시킬 수 있게 된다.
현재 통계에 의하면 이 기법에 의해 원래 팩시밀리 통신의 이미지정보를 평균 약1/8이하로 축소해 전송할 수 있다고 한다.
허프만 압축기법의 또 다른 변형으로는 상용 압축파일 가운데서 가장 압축률이 우수한 LHARC라는 압축파일이 채용하고 있는 ‘적응적 허프만부호’를 들 수 있다.
허프만 압축기법이 미리 조사된 정보원 데이터의 통계적 성질을 이용해 압축을 수행하는 반면, 이 기법은 원래 데이터의 각 문자 입력마다 적응적으로 발생문자의 빈도수를 계산해 확률 값에 따라 허프만부호를 할당하는 압축방식이다. 동적 압축기법은 압축수행에 소요되는 시간 때문에 정보통신분야 에서는 잘 이용하지 않는다.
허프만코드 생성 방법
① 단 하나의 노드만을 가지고 있는 Binary Tree와 각 문자를 매핑
② 각 트리에 문자들의 빈도수를 할당 : 트리의 가중치(weight) - 내림차순으로 정렬
③ 두 개의 가장 작은 가중치를 가지고 있는 트리를 찾아 하나의 트리로 합치고 새로운 루트 노드를 만들어 냄 (이 새 트리의 가중치는 합쳐진 두 트리의 가중치의 합)
④ 마지막으로 하나의 트리가 남을 때까지 이 과정을 반복
⑤ 이 과정이 끝났을 때 원래 노드들의 각각은 마지막 Binary Tree의 말단 노드(leaf)가 됨
⑥ Binary Tree에서 루트로부터 말단 노드에 이르는 유일한 길(path)이 있게 되고 이 길이 허프만 코드가 됨(각 왼쪽 자식 포인터에 0을 할당하고, 오른쪽 자식 포인터에 1을 할당해서 결정)
초기 코드
Character
Code
Frequency
Total Bits
a
000
10
30
e
001
15
45
i
010
12
36
s
011
3
9
t
100
4
12
space
101
13
39
new line
110
1
3
Total
3 Bits
58 회
174 Bits
Huffman(C) 의사 코드
n <- |C|
Q <- C
for i <- 1 to n - 1
do
left[z] <- x <- Extract - Min(Q)
right[z] <- y <- Extract - Min(Q)
f[z] <- f[x] + f[y]
Insert(Q, z)
return Extract - Min(Q)
■ 초기 코드의 Binary Tree 표현
■ 허프만코드 산출을 위한 이진트리
문자의 빈도수를 이용해 다음 과정으로 이진트리를 생성하여 트리의 왼쪽 종속트리로 갈 때에는 0, 오른쪽 종속트리로 갈 때에는 1로 코드화한다.
■ 허프만 알고리즘의 수행시간 분석
Q가 이진 최소 힙으로 구현되어 있다고 가정하고, N개의 문자를 가진 집합 C에 대해 2행에 있는 Q의 초기화
Huffman Code는 Greedy Algorithm으로 해결가능하다.

키워드

알고리즘,   LCS,   Huffman,   허프만코드