All
허프만 코딩 Huffman coding
문자의 빈도수(출현 횟수)를 기반으로 가변 길이의 이진 코드를 부여하여 전체 데이터를 압축하는 방식
•
빈도수가 높을수록 짧은 이진 코드
•
빈도수가 낮을수록 긴 이진 코드
•
트리 기반 구조로, 접두부 코드(Prefix-free code)를 구성함 → 디코딩 시 모호성 없음
예시 데이터
문자 | 코드 | 빈도 |
a | 11 | 4 |
b | 0 | 5 |
c | 101 | 2 |
d | 100 | 1 |
a b a b a b c d b a b c → 1101101101011000110101
허프만 트리
•
각 문자에 이진 코드를 부여하기 위한 이진트리
•
상향식으로 빈도가 가장 낮은 두 노드를 계속 합치며 트리 구성 (greedy)
생성 방법
1.
초기 노드 생성
[d:1], [c:2], [a:4], [b:5]
2.
가장 작은 두 노드 선택 d:1, c:2 → 합쳐서 dc:3
[dc:3], [a:4], [b:5]
3.
다음 최소: dc:3, a:4 → 합쳐서 dca:7
[dca:7], [b:5]
트리:
root(12)
/ \
b(5) dca(7)
/ \
dc(3) a(4)
/ \
d(1) c(2)
Plain Text
복사
허프만 코드 부여
왼쪽 edge: 0, 오른쪽 edge: 1
문자 | 코드 |
b | 0 |
d | 100 |
c | 101 |
a | 11 |
인코딩
1.
주어진 스트링에서 각 문자의 출현 빈도수 계산
2.
각 문자의 빈도수를 이용하여 허프만 트리를 만들어 각 문자에 이진 코드 부여
3.
주어진 스트링의 각 문자를 이진 코드로 변환하여 압축된 스트링 생성
디코딩
1.
허프만 트리의 루트 노드에서 시작
2.
압축된 스트링을 1비트씩 읽으며 자식 노드로 내려감
3.
리프 노드에 도착하면 그 노드에 해당하는 문자 출력 후 1. 로 이동
성능과 특징
•
인코딩 성능:
◦
각 문자 빈도수 계산: O(n)
◦
허프만 트리 생성 및 이진 코드 생성:
▪
최소 힙 구축:
▪
알파벳 크기만큼 힙에서 최소값 삭제와 삽입 반복하며 트리 생성
▪
트리 순회하며 각 문자의 이진코드 추출:
◦
스트링의 길이만큼 수행: O(n)
•
디코딩 성능:
◦
허프만 트리 생성:
◦
압축된 비트 스트링의 길이만큼 수행:
•
접두부 코드(Prefix-free): 어떤 문자 코드도 다른 문자 코드의 접두사가 아님 → 디코딩에 모호성 없음
•
최적 압축: 자주 등장하는 문자일수록 짧은 코드 → 전체 압축 효율 극대화
•
트리는 유일하지 않음: 같은 빈도수의 문자가 있을 경우 트리 구조가 다를 수 있음 → 결과 코드도 다를 수 있음
LZ77 Lempel-Ziv 77 압축 알고리즘
•
문자열에서 이미 등장한 문자열이 이후에 다시 나타나면,
이를 다시 적는 대신 이전 위치를 참조해 압축하는 방법
•
Sliding Window를 활용하여 한정된 영역 내에서만 과거를 참조함
구성요소
압축된 정보는 다음 3가지 정보의 3-튜플 형태:
(offset, length, next_char)
•
offset (거리): 현재 위치에서 얼마나 뒤로 가야 동일 문자열이 시작되는지를 의미
•
length (길이): 매치되는 문자열의 길이
•
next_char (다음 문자): 반복된 문자열 다음에 나오는 새로운 문자
Sliding Window
•
검색 버퍼(Search Buffer): 이미 읽은 부분 (과거 문자열)
•
탐색 버퍼(Lookahead Buffer): 앞으로 읽을 부분 (현재/미래 문자열)
•
window는 고정 크기를 유지하며 한 글자씩 앞으로 이동
인코딩
1.
현재 위치부터 lookahead buffer에 있는 문자열을 search buffer와 비교
2.
가장 긴 일치 문자열을 찾음
3.
그 매치에 대해 (offset, length, 다음 문자)를 기록
4.
(length + 1) 만큼 이동하고 1번부터 반복
예시:
입력 문자열
abcabcabcabc
Sliding Window 설정 예 (search buffer 최대 6글자)
초기 상태에서 "abc"는 새로 처음 나왔으므로 매치 없음
1.
("", 0, 'a') → 그냥 문자 그대로 출력
2.
("", 0, 'b')
3.
("", 0, 'c')
4.
"abc"가 다시 나옴 → search buffer에 있는 "abc"와 매치
→ offset=3, length=3, next='a'
→ (3, 3, 'a')
5.
이어서 "bca"도 앞과 매치 → (3, 3, 'b')
6.
계속 "cab" 매치 → (3, 3, 'c')
압축 결과
(0, 0, 'a')
(0, 0, 'b')
(0, 0, 'c')
(3, 3, 'a')
(3, 3, 'b')
(3, 3, 'c')
디코딩
1.
문자열을 하나씩 복원
2.
각 튜플에 대해:
•
offset만큼 뒤에서 시작해 length만큼 문자를 복사
•
다음 문자를 추가
3.
복사된 문자열이 길어질수록 압축률이 향상됨
성능과 특징
•
시간복잡도:
◦
인코딩: 일반적으로 O(n), 최악의 경우 O(n²)
◦
디코딩: O(n)
•
특징
◦
무손실 압축 방식
◦
허프만 코딩과 조합해서 ZIP 등에서 사용됨
◦
사전(dictionary)을 별도로 만들지 않고, 이미 지나온 데이터 자체를 참조
◦
LZ78, LZW 등은 LZ77의 발전형
영상 압축
•
2차원 이미지: 인접한 픽셀 간 유사성 활용
•
3차원 동영상: 인접한 프레임 간 유사성 활용 (시간적 중복 제거)
이미지 압축
•
대표 형식: JPEG, GIF, PNG, TIFF 등
•
JPEG 인코딩 과정
1.
블록 분할: 8×8 픽셀 단위로 분할
2.
DCT (이산 코사인 변환): 주파수 영역으로 변환
3.
양자화: 중요하지 않은 주파수 값 제거
4.
엔트로피 코딩: 허프만 등의 방법으로 이진화 압축
•
JPEG 디코딩 과정
◦
엔트로피 디코딩 → 역양자화 → 역 DCT → 블록 합성
동영상 압축
•
대표 형식: MPEG-1, MPEG-2, MPEG-4 등
•
핵심 기법: 시간 간 프레임 간 차이점만 저장
•
움직임 벡터: 프레임 간 객체의 위치 변화를 가로·세로 변화량으로 표현