알고리즘 공부 - 압축

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 압축(compression)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

압축을 하는 방식에는 무손실(lossless) 압축과 손실(lossy) 압축이 있습니다.

무손실 압축을 사용하는 경우는 text나 수치 데이터와 같이 디코딩시 원본 데이터가 온전히 보전되는 압축 방식을 말하며, 손실 압축을 사용하는 경우는 이미지나 영상 데이터와 같이 사람이 인지하지 못하는 수준내에서 디코딩시 원본 데이터가 손실되는 압축 방식을 말합니다.

Huffman coding

Huffman coding은 무손실 압축을 위한 방식 중 하나로 동일한 데이터에 대한 빈도를 기반으로 가변길이 데이터로 치환하는 방식을 사용합니다.

Huffman coding을 사용하기 위해서는 prefix code가 필요합니다.

Prefix code는 이진트리로 표현할 수 있습니다. 표현하는 방식으로는 최소 빈도를 가진 두개의 노드를 선택하여 부모 노드를 생성하고 부모 노드는 두 자식노드의 빈도 수의 합을 가집니다. 이렇게 최소 빈도 수를 자식으로 가진 부모 노드를 만드는 것을 반복하여 트리를 생성합니다.

이후 루트 노드를 기준으로 왼주쪽 경로는 0, 오른쪽 경로는 1을 부여하여 각 리프노드의 코드를 생성합니다.

Run-length encoding

Run-length encoding도 무손실 압축을 위한 방식 중 하나입니다.

압축을 위한 아이디어로는 반복되는 문자에 대해 갯수를 숫자로 치환하는 것입니다.

해당 압축 방식은 이미지나 영상 데이터를 압축하기 위한 하나의 단계로 사용합니다.

Huffman Method with Run-Length Encoding

Huffman Method with Run-Length Encoding은 Huffman coding의 인코딩 단위를 Run-length encoding으로 정의한 방식입니다. 좀 더 구체적으로 run-length encoding을 사용하여 super-symbol을 정의하고 각 super-symbol에 대해 huffman coding을 적용합니다.

Super-symbol(run) 은 symbol, run length, frequency로 정보로 구성합니다.

구현 코드는 깃헙으로 공유합니다.

관련 강의

• [알고리즘] 제17-1강 압축 (compression01
• [알고리즘] 제17-2강 압축 (compression)
• [알고리즘] 제17-3강 압축 (compression)
• [알고리즘] 제6-4강 힙(heap)의 다른 응용: 우선순위 큐 (priority queue)
• [알고리즘] 제17-4강 압축 (compression)
• [알고리즘] 제17-5강 압축 (compression) - 2016년 버전01)
• [알고리즘] 제17-5강 압축 (compression) - 2015년 버전
• [알고리즘] 제17-6강 압축 (compression)
• [알고리즘] 제17-7강 압축 (compression) (마지막)

관련 글

• 알고리즘 공부 - 최단경로
• 알고리즘 공부 - 최소비용신장트리
• 알고리즘 공부 - 그래프
• 알고리즘 공부 - 해싱
• 알고리즘 공부의 필요성
• 알고리즘 공부 - 트리
• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유