[알고리즘] Huffman code / 허프만코드

📕Huffman code 란?압축은 자료의 크기를 줄이기 위해서 사용된다. 그리고 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 알고리즘이다. Huffman code도 그리디 알고리즘의 일종이다. 허프만코드는 데이터를 매우 효율적으로 압축하는데, 20~90%의 용량을 아낄 수 있다. 허프만 코드는 prefix-free* codes로 표현된다. prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장한다. (*prefix codes가 표준 표기이긴 하지만, prefix-free codes가 좀 더 맞는 이름이기 때문에 여기에서는 prefix-free codes로 표기하겠다) ..

2021.06.13