→ 빈도 수를 이용해 1-2번의 방법으로 파일 줄이기
→ 반복을 통해 3-6번의 방법으로 파일 줄이기
→ 빈도수와 반복을 적절히 혼합한 7번 방법
1. RLE(Run-Length Encoding)
1-1) RLE?
Window 3.0 혹은 Window 3.1 시절에 사용됐음.
BMP(Click), RLE 등의 고대 인코딩을 위해 사용.
연속된 동일한 글자를 횟수로 축약
연속된 같은 글자가 없으면 효율이 떨어짐.
⇒ 빈도 수를 통해 파일을 줄임
1-2) RLE Action Structure
→ A가 5개일 때 5A로 D가 2개일 때 2 D
2. Huffman Code(=Entrophy Encoding)
2-1) Entrophy Encoding
심볼이 출연할 확률에 따라 심볼에 사용하는 비트 수를 줄임.
적은 심볼을 사용하는 경우 적은 비트 수를
많은 심볼을 사용하는 경우에는 많은 비트 수를 사용하면
결과적으로 적은 비트 수를 사용해 인코딩을 할 수 있음.
이를 가리켜 엔트로피 부호화함.
2-2) Entrophy Encoding 예시
→ A는 5번(0.45), C는 2번(0.18), D는 3번(0.27), E는 1번(0.09).
→ 위와 같은 횟수를 바탕으로 확률을 가지게 됨.
2-2)-1. 아래 확률을 기반으로 오름차순으로 정리
⇒ 낮은 확률 두 개를 선택함.(E와 C)
2-2)-2. Tree 구조-1
2-2)-3. Tree 구조-2
2-2)-4. Tree 구조-3
2-2)-5. Tree 구조 -4
⇒ 확률이 높을 수록 더 적은 비트 수를 갖고 표현 됨.
⇒ 확률이 적을 수록 더 많은 비트 수를 갖고 표현 됨.
3. LZ77(LZ1)
3-1) LZ77(LZ1)
→ 빈도 수를 통해 파일을 줄일 뿐 아니라 반복을 통해 파일을 줄일 필요가 있음.
1977년에 만들어 LZ77 혹은 첫 번째라서 LZ1이라고 부름
중복된 문자열을 제거. 슬라이딩 윈도우가 특징.
반복되는 문자열이 슬라이딩 윈도우(Sliding Window)보다 길 경우 압축 할 수 없음.
3-2) Sliding Window(Search Buffer)
3-2)-1. Sliding Window(Search Buffer)
Window는 검색 대상, View는 이번에 처리해야할 내용.
View에서 처리가 끝난 데이터는 Window로 이동.
→ Window는 View와 같은 내용이 있는지 없는지 확인하는 공간임.
-> View는 압축할 내용임. View에서 압축한 내용들은 다시 Window로 이동하게 됨.
→ Window에 있는 기존 내용은 사라지게 됨.
3-2)-2. Sliding Window 예시
View의 앞부분 Hell과 겹치는 Hell을 Window에서 찾음.
→ 겹치는 부분이 있기 때문에 압축을 할 수 있는 거임.
3-3) LLD(Literal, Length, Distance)
LZ77에서 핵심적으로 볼게 바로 LLD임.
Literal : 중복되지 않음 첫 번째 글자
Length : 중복된 길이
Distance : View 앞 부분에 있는 글자가 Window에서 어느 위치에 있는지를 기록하기 위한 거임.
→ Distance에서 6개의 글자를 지나고 나서야 겹치는 문자열로 이동할 수 있음.
⇒ (6, 4, 'o')를 통해 LLD 튜플의 목록을 만듦.
⇒ 3가지의 정보(6, 4, 'o')를 갖고 있는 1개의 튜플이 만들어지는 모습.
3-4) LLD 이해
3-4)-1. View Buffer 5bytes, Window Buffer 6bytes로 가정했을 때
→ View 'H'부터 압축 시작.
3-4)-2. View Buffer 5bytes, Window Buffer 6bytes로 가정했을 때
→ Window에서 공통적인 부분을 찾기 어렵기 때문에 모두 0임.
3-4)-3. View Buffer 5bytes, Window Buffer 6bytes로 가정했을 때
→ 마찬 가지로 겹치는 부분이 없기 때문에 Distance와 Length는 0임.
3-4)-4. View에서 Window로 넘어오면서 겹치는 부분이 있을 때
3-4)-5. 겹치는 부분이기에 패스
3-4)-6. Hell이라는 글자가 중복 됐을 때
4. LZ78(LZ2)
5. LZW
6. LZSS(LZ77을 개선한 방식)