엔트로피코딩
![[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbhideE%2FbtqF1noe0pu%2FrhMNuzGFtW9aSfruJ8T1hk%2Fimg.png)
[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현
허프만 부호화 (Huffman coding) 허프만 부호화란 무손실 압축에 사용되는 엔트로피 코딩 중 하나이다. 이전 글에서 엔트로피 코딩의 목적은 데이터 심볼 당 평균 부호 길이가 엔트로피에 가까워지도록 부호를 할당하여 압축 효율을 높이는 것이라고 하였다. 허프만 부호화는 발생 빈도가 높은 (자주 나오는) 심볼에는 짧은 부호를 할당하고, 발생 빈도가 적은 심볼에는 비교적 긴 부호를 할당한다. 따라서 최대한으로 평균 부호길이가 압축되는 결과를 얻을 수 있다. 허프만 부호화 시 각각의 심볼에 접두 코드(Prefix code)를 할당한다. 접두 코드란 코드 집합에서 어떤 코드도 다른 코드의 접두사가 되지 않게 만들어진 코드이다. 예를 들어 {"0", "01"} 코드 집합의 경우 접두 코드가 아니다. "0"은..
[압축 알고리즘] 엔트로피 코딩? + 런렝스 부호화 (Run-length encoding)
엔트로피 코딩 (Entropy Coding) 이란? 일반적으로 엔트로피(Entropy)란 '무질서도' 혹은 '불확실성'을 가리킨다. '정보의 양'을 중요시하는 정보공학적 관점에서는 '평균 정보량'을 엔트로피라고 한다. 엔트로피에 대해 설명하자면... 앞으로 발생할 사건에 대해 (확정적인) 정보가 많다면 예측률이 높아진다. 이러한 경우 우리는 사건이 발생해도 별로 놀라지 않는다. 즉, 이 사건은 결과적으로 우리에게 적은 정보를 제공한다. 이를 엔트로피가 낮다고 한다. 반면, 어떤 정보일지 불확실할수록 사건에 대해 예측이 어려워진다. 따라서 이 사건이 발생할 때 우리는 훨씬 유용한 정보를 제공받게 된다. (놀라운 정보가 많다) 이를 엔트로피가 높다고 한다. 예를 들어 동전과 주사위가 있다. 동전을 던져서 발..