무손실 압축기법_반복길이 부호화, LZW알고리즘, 산술 부호화

▣ 무손실 압축기법_반복길이 부호화, LZW알고리즘, 산술 부호화

반복길이 부호화 (RLE, Run Length Encoding)	데이터에서 같은 값이 연속해서 나타나는 것을 그 개수와 반복되는 값만으로 표현하는 방법 아이콘 등의 간단한 이미지와 같이 연속된 값이 많이 있는 데이터에 효과적임 런 렝스 부호화는 만화나 애니메이션 등과 같이 배경의 변화가 없는 영상에 적합함
Lempel-Ziv-Welch(LZW) 알고리즘	아브라함 렘펠과 제콥 지브, 테리 웰치가 만든 공통 비손실 데이터 압축 알고리즘 RLE 기술과 비슷하게 반복되는 문자열이나 단어를 검색하여 변수에 저장 코드워드의 길이가 다른 가변 길이 부호화와는 달리, 영어 문장의 단어처럼 주로 함께 발생하는 가변 길이의 기호/문자열을 표현하는데 고정 길이 코드워드 사용 부호화기와 복호화기는 데이터를 수신하는 동안 유동적으로 동일한 사전을 생성 단일 코드가 한 가지 기호/문자 이상을 표현할 수 있기 때문에 데이터 압축이 이루어짐
산술부호화	전체 메시지를 하나의 단위로 취급 입력 데이터는 보통 오류 전파를 방지하기 위해 일단의 묶음으로 쪼개짐 다른 엔트로피 부호화 알고리즘이 각각의 기호를 1:1로 부호로 대체하는 반면에, 산술 부호화는 전체 메시지를 하나의 실수 n으로 대체함 산술 부호화는 주어진 기호와 확률분포에 대해 최적에 가까운 압축률을 보일 수 있음

■ LZW 예제

1. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

 

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

 

msg	answer
KAKAO	[11, 1, 27, 15]

 

▣ 손실 압축 vs무손실 압축

구분	손실 압축	무손실 압축
기본	Lossy 압축 방법은 눈에 띄지 않는 약간의 데이터를 제거 데이터 품질이 최우선 순위가 아닌 경우 유용 오디오 신호 및 이미지와 같은 유기적 데이터에 사용	원본 데이터를 압축 데이터에서 정확하게 재구성 할 수 있는 데이터 압축 알고리즘
연산	변환 코딩, DCT, DWT, 프랙탈 압축, RSSMS	RLE, LZW, 산술 인코딩, 허프만 인코딩, Shannon Fano 코딩
사용	이미지, 오디오 및 비디오	텍스트 또는 프로그램, 이미지 및 사운드
	JPEG, GUI, MP3, MP4, OGG, H-264, MKV 등	RAW, BMP, PNG, WAV, FLAC, ALAC 등

 

 

---

2020년 77번

정답 : 4번

무손실 압축기법은 반복길이(run-length)부호화, LZW부호화, 산술 부호화 등이 있음

 

반복LZW산술