[Algorithm] Huffman Coding 1: 개념

Huffman Coding

• 무손실 압축 알고리즘이다.

 

 

Huffman Coding 예시

• 파일 안에는 a,b,c,d,e,f 의 단어만 있다고 가정한다.
• 파일의 크기는 100,000 개 이고 각 문자의 등장 횟수는 다음과 같다. 
• Fixed-length code: 문자를 표현하기 위해 3bit 가 필요하므로 300,000비트가 된다.
• Variable-length: 가변길이를 가용하면 224,000 비트가 된다.

 

 

 

 

Prefix Code

FIxed-length 와 Variable-length 어떻게 구할까?

prefix code로 구한다.

• 어떤 codeword도 다른 codeword의 prefix가 되지 않는 코드 (여기서 codeword란 하나의 문자에 부여된 이진코드를 말함)
• 각각의 고유번호를 가지고 있기 때문에 애매한 부분없이 decode가 가능하다.
• prefix code는 하나의 이진트리로 표현 가능하다.

 

 

Tree 가 만들어 지는 과정

• 빈도수가 적은 두개는 자식이 된다.
• 부모는 두개의 빈도수를 합한 값이 된다.
• 반복한다.

 

 

 

Run-Length Encoding

• 또다른 압축 알고리즘의 하나이다.
  같이 정리하는 이유는 해당 알고리즘도 같이 사용할 것이다.
  
  
• 런(run)은 동일한 문자가 하나 혹은 그 이상 연속해서 나오는 것을 의미한다.
  예를 들어 스트링 s = “aaabba”는 다음과 같은 3개의 run으로 구성된다: “aaa”,“bb”, “a”.
  
  
• run-length encoding에서는 각각의 run을 그 “run을 구성하는 문자”와 “run의
  길이”의 순서쌍 (n, ch)로 encoding한다.
  여기서 ch가 문자이고 n은 길이이다. 가령 위의 문자열 s는 다음과 같이 코딩된다: 3a2b1a.
  
  
• Run-length encoding은 길이가 긴 run들이 많은 경우에 효과적이다.

 

 

 

 

다음 순서

인코딩

https://vprog1215.tistory.com/244

[Algorithm] Huffman Coding 2: 예제 설명

 

 

디코딩

https://vprog1215.tistory.com/245

[Algorithm] Huffman Coding 3: Decoding 예제 설명 과 구현