허프만 코딩은 1952년 데이비드 허프먼이 개발한 무손실 압축 알고리즘으로[1], JPEG 이미지나 MP3 음악 파일 압축에서의 서브루틴 역할을 넘어 훨씬 광범위한 분야에서 활용되고 있습니다[2]. 허프만 테이블의 핵심 원리는 빈도가 높은 데이터에는 짧은 코드를, 빈도가 낮은 데이터에는 긴 코드를 할당하여 전체 데이터 크기를 최소화하는 것입니다[3].
파일 형식 및 멀티미디어 압축
이미지 압축 형식
허프만 코딩은 PNG 파일 압축에서 핵심적인 역할을 합니다[4]. PNG는 LZ77 알고리즘과 허프만 부호화를 결합한 DEFLATE 압축 알고리즘을 사용하며[5], 빈도수를 파악해 자주 나타나는 패턴일수록 더 적은 비용으로 압축합니다[5]. PNG의 디코딩 과정에서는 Dynamic/Fixed Huffman Coding으로 압축된 데이터로 트리를 생성한 후 해당 트리를 가지고 1차적으로 압축을 해제합니다[4].
음성 및 비디오 코덱
JPEG, MP3 등의 코덱에서 허프만 코딩이 서브루틴으로 활용됩니다[2][6]. 이러한 코덱들이 허프만 코딩을 선택하는 이유는 알고리즘이 단순하고 빠르기 때문입니다[6]. 특히 FLAC 음성 압축에서도 허프만 테이블이 사용되어 무손실 오디오 압축을 구현합니다[7].
네트워크 통신 및 웹 기술
HTTP/2 헤더 압축
HTTP/2의 HPACK에서 허프만 코딩이 헤더 압축에 사용됩니다[8]. HTTP 헤더를 압축하기 위해서는 무손실 압축이 필요하며, 실시간 전송을 위해 압축 속도가 매우 중요합니다[8]. 허프만 코딩은 연속된 값이 거의 없는 HTTP 헤더 같은 데이터를 압축할 경우 효율적이며[8], 산술 부호화보다 연산량이 적어 시간이 적게 걸린다는 장점이 있습니다[8].
파일 압축 유틸리티
Unix 파일 압축 명령어와 ZIP 압축 형식에서도 허프만 코딩이 활용됩니다[2][9]. 텍스트 압축을 위해 널리 사용되는 방법으로, 원본 데이터에서 빈도수가 높은 문자는 적은 비트의 코드로, 빈도수가 낮은 문자는 많은 비트의 코드로 변환하여 압축률을 높입니다[10].
생물정보학 및 과학 연구
DNA 서열 분석
DNA 염기서열 분석 기법에서 허프만 코딩이 활용됩니다[11]. 반복 서열이나 공통 패턴을 효율적으로 인코딩하는 알고리즘으로 사용되며[11], 고속 대용량 염기서열 분석에서의 정보 압축에 핵심적인 역할을 합니다[11]. 수십억 개의 염기쌍 데이터를 다루는 과정에서 수십~수백 기가바이트에 달하는 원시 데이터를 저장하고 전송하며 처리하기 위해 허프만 압축이 필수적입니다[11].
자연어 처리
자연어 처리 응용에서도 허프만 코딩이 사용됩니다[7]. 텍스트 압축에서 문자의 출현 빈도를 분석하여 효율적인 인코딩을 수행하며, 특히 대용량 텍스트 데이터의 저장 공간을 최적화하는 데 활용됩니다[7].
암호화 및 보안 통신
보안 데이터 전송
암호화 및 보안 데이터 전송에서 허프만 코딩이 활용됩니다[7]. 데이터를 압축한 후 암호화함으로써 전송 효율성과 보안성을 동시에 확보할 수 있습니다[12]. 파일의 윗부분에는 코드 테이블이 들어가고, 아래는 압축 테이블을 활용하여 암호화한 데이터가 들어가는 구조로 구현됩니다[12].
데이터베이스 및 저장 시스템
데이터베이스 최적화
데이터베이스에서의 데이터 저장 최적화에 허프만 코딩이 사용됩니다[7]. 빈번하게 접근되는 데이터에 짧은 코드를 할당하여 저장 공간을 효율적으로 활용하고, 데이터 검색 속도를 향상시킵니다[7].
통신 대역폭 최적화
통신에서의 대역폭 사용 최적화에도 허프만 코딩이 적용됩니다[7]. 전송되는 데이터의 크기를 줄여 네트워크 대역폭을 효율적으로 사용하고, 전송 시간을 단축시킵니다[7].
이론적 배경과 한계
엔트로피와 정보 이론
허프만 코딩은 엔트로피 부호화의 일종으로, 심볼이 나올 확률에 따라 심볼을 나타내는 코드의 길이를 달리하는 부호화 방법입니다[13][14]. 엔트로피는 각 기호가 포함하는 평균 정보량을 의미하며[15], Shannon 부호화 이론에서는 엔트로피를 우리가 할 수 있는 최선이라고 말합니다[15].
영어 알파벳을 예로 들면, 26자로 이루어진 알파벳 1글자는 약 4.7비트의 엔트로피를 가지지만[16], 실제 사용되는 문장에서의 엔트로피는 이보다 훨씬 적습니다[16]. 사용 가능한 단어들로만 이루어진 문장에서는 정보의 조합 중 일부가 배제되기 때문입니다[16].
다른 압축 알고리즘과의 비교
허프만 코딩은 산술 부호화(Arithmetic Coding)와 비교했을 때 각각의 장단점이 있습니다[17][18]. 허프만 인코딩은 단순히 기호들의 나열을 통해 표현하는 반면, 산술 인코딩은 부호화하고자 하는 메시지 전체가 하나의 숫자로 나타납니다[18]. 산술 부호화는 허프만보다 압축률이 좋지만, 복잡한 수학적 계산을 수행해야 하므로 연산량이 매우 크고 시간이 오래 걸립니다[8][17].
Shannon-Fano 코딩과 비교할 때, 허프만 코딩은 소스 심볼 확률을 기반으로 하는 반면 Shannon-Fano는 누적 분포 함수를 기반으로 합니다[19]. 허프만 코딩이 더 나은 효율성과 높은 최적화를 제공합니다[19].
성능 특성과 한계
허프만 코딩의 시간 복잡도는 O(n log n)입니다[20][21]. 문자 집합의 크기를 n이라고 할 때, 허프만 트리를 생성하기 위한 초기 힙 구축에 O(n) 시간이 걸리고, for 루프는 (n-1)번 반복하면서 루프 내에서 힙에서 최솟값을 삭제하는 데 O(log n) 시간이 걸립니다[22].
허프만 코딩의 한계는 각 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 제한에서 기인합니다[1]. 이 때문에 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프만 부호보다 효율적인 경우가 많습니다[1].
또한 허프만 코딩에서는 각 문자의 빈도수를 모르는 경우 주어진 텍스트를 두 번 읽어야 하는 단점이 있습니다[22]. 이를 해결하기 위해 문자의 빈도수를 만들어 나가면서 코딩을 하는 동적 허프만 코딩도 개발되었습니다[22].
출처
[1] 허프먼 부호화 – 위키백과, 우리 모두의 백과사전 https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A8%BC_%EB%B6%80%ED%98%B8%ED%99%94
[2] 허프만 코딩(Huffman coding) – velog https://velog.io/@junhok82/%ED%97%88%ED%94%84%EB%A7%8C-%EC%BD%94%EB%94%A9Huffman-coding
[3] 압축 알고리즘 Huffman Coding – 소프트웨어 공장 https://coding-by-head.tistory.com/entry/huffman-coding
[4] [임시][PNG] Deflate/Inflate – Huffman Coding – 네이버 블로그 https://blog.naver.com/hoon0917sjs/221359091043
[5] 22.03.16 png 압축 알고리즘 – Sweet But Psycho – 티스토리 https://jemerald.tistory.com/191
[6] 허프만 코드 (Huffman Code) https://timewizhan.tistory.com/entry/%ED%97%88%ED%94%84%EB%A7%8C-%EC%BD%94%EB%93%9C-Huffman-Code
[7] Huffman Coding Applications to Know for Information Theory https://library.fiveable.me/lists/huffman-coding-applications
[8] HPACK이 Huffman coding을 사용하는 이유 – 전지적 개발자 시점 https://http2.tistory.com/2
[9] [자료구조/JAVA] 허프만 코딩 (Huffman Coding) https://sjh9708.tistory.com/207
[10] 허프만 코딩(Huffman Coding) – Java 구현 : 네이버 블로그 https://blog.naver.com/duddl425/222358519212
[11] [컴퓨터 SW] 생명과학 세특 주제 탐구 – DNA 염기서열 분석 기법 탐구 … https://miraeinjae1297.tistory.com/entry/%EC%BB%B4%ED%93%A8%ED%84%B0-SW-%EC%83%9D%EB%AA%85%EA%B3%BC%ED%95%99-%EC%84%B8%ED%8A%B9-%EC%A3%BC%EC%A0%9C-%ED%83%90%EA%B5%AC-DNA-%EC%97%BC%EA%B8%B0%EC%84%9C%EC%97%B4-%EB%B6%84%EC%84%9D-%EA%B8%B0%EB%B2%95-%ED%83%90%EA%B5%AC%EC%97%90-%ED%99%9C%EC%9A%A9%EB%90%9C-%EB%B0%94%EC%9D%B4%EC%98%A4%EC%9D%B8%ED%8F%AC%EB%A7%A4%ED%8B%B1%EC%8A%A4
[12] 허프만코딩(Huffman Coding) – 이론, 알고리즘,C로 코딩한 소스 코드 … http://blog.naver.com/rkttndk/221398382908
[13] 엔트로피 코딩 : 네이버 블로그 https://blog.naver.com/ichitaka99/90013836792
[14] 8. Huffman’s Code (허프만 부호화) – exponential-e – 티스토리 https://exponential-e.tistory.com/52
[15] Huffman Coding | JAVA – README – GitBook https://dahye-jeong.gitbook.io/java/master-1/algorithm/2018-06-02-algorithm-huffman
[16] ▷ 허프만 부호화(Huffman Coding) ◁ : 네이버 블로그 https://blog.naver.com/supergrammer/221371777709
[17] 산술 부호화 – 땅콩킹땅콩 – 티스토리 https://gomguk.tistory.com/26
[18] Arithmetic Coding :: A Think Piece https://thinkpiece.tistory.com/2
[19] Difference Between Huffman Coding and Shannon Fano Coding https://techdifferences.com/difference-between-huffman-coding-and-shannon-fano-coding.html
[20] [알고리즘] Huffman code / 허프만코드 – 성장하는 개발 블로그 https://mirrorofcode.tistory.com/67
[21] [알고리즘 정리] 허프만 코드(Huffman Code Problem) – 티스토리 https://jeonyeohun.tistory.com/85
[22] 4장 욕심쟁이 알고리즘 9 (허프만 코딩) – 네이버 블로그 https://blog.naver.com/wongoni/222189020294
[23] 허프만 코드 필요성과 알고리즘 소개 https://velog.io/@kimgh06/%ED%97%88%ED%94%84%EB%A7%8C-%EC%BD%94%EB%93%9C-%ED%95%84%EC%9A%94%EC%84%B1%EA%B3%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%86%8C%EA%B0%9C
[24] [자료구조] 허프만 코드 (Huffman Code) – 나무보다 숲을 – 티스토리 https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%97%88%ED%94%84%EB%A7%8C-%EC%BD%94%EB%93%9C-Huffman-Code
[25] [DS] 허프만 코드 : 힙의 응용 – velog https://velog.io/@he1256/%ED%97%88%ED%94%84%EB%A7%8C-%EC%BD%94%EB%93%9C-%ED%9E%99%EC%9D%98-%EC%9D%91%EC%9A%A9
[26] 허프만 코드 https://bethejustice.tistory.com/25
[27] Huffman Coding – 개발 노트 – 티스토리 https://kchanguk.tistory.com/135
[28] Huffman coding: Description and instructions for use – DataScientest https://datascientest.com/en/huffman-coding-description-and-instructions-for-use
[29] PNG JPG 똑같은거 아님? – velog https://velog.io/@wyk172899/PNGJPG%EB%98%91%EA%B0%99%EC%9D%80%EA%B1%B0%EC%95%84%EB%8B%98
[30] JPG, PNG, WebP에 대해 알아보자 – seholee https://seholee.com/blog/jpg-png-webp
[31] [c++] Huffman Algorithm – 파일 압축 알고리즘 – 호정s 개발 일기 https://hojung-testbench.tistory.com/entry/c-Huffman-Algorithm-%ED%8C%8C%EC%9D%BC-%EC%95%95%EC%B6%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
[32] 이미지 압축해 저장하기 (feat. 손실 압축, 무손실 압축) – < Hyun / Log > https://hstory0208.tistory.com/entry/%EC%9D%B4%EB%AF%B8%EC%A7%80-%EC%95%95%EC%B6%95%ED%95%B4-%EC%A0%80%EC%9E%A5%ED%95%98%EA%B8%B0-feat-%EC%86%90%EC%8B%A4-%EC%95%95%EC%B6%95-%EB%AC%B4%EC%86%90%EC%8B%A4-%EC%95%95%EC%B6%95
[33] LZW 알고리즘과 허프만 부호화 방법을 서로 비교하여 분석해보자. https://steadyman.tistory.com/14
[34] [C++] Adaptive Huffman Coding(적응형 허프만 코딩) – 밸런스 있는 삶 https://himbopsa.tistory.com/46
[35] Arithmetic Coding – 소프트웨어 공장 – 티스토리 https://coding-by-head.tistory.com/entry/arithmetic-coding
[36] [PDF] DNA 서열을 위한 빠른 매칭 기법 https://koreascience.kr/article/JAKO200932056734188.pdf
[37] 허프만 알고리즘을 통한 최적 이진 문자 코드 구축 과정 분석하기 … https://develop247.tistory.com/66
[38] Entropy & Information Theory | Hyeongmin Lee’s Website https://hyeongminlee.github.io/post/prob001_information_theory/
[39] [알고리즘] 허프만 트리를 이용한 텍스트 압축 – 신입부터의 기록 https://makga.tistory.com/88
답글 남기기