▲

Haskell을 사용한 Huffman 코드 기반 데이터 압축 유틸리티 개발

 (lazamar.github.io)
1P by GN⁺ 2024-07-06 | ★ favorite | 댓글 1개

Huffman 코딩을 사용한 데이터 압축 프로그램 구현

  • Huffman 코드란?
    • 각 문자를 고유한 비트 시퀀스로 매핑하여 데이터 압축을 수행함
    • 자주 등장하는 문자는 짧은 비트 시퀀스로, 드물게 등장하는 문자는 긴 비트 시퀀스로 매핑함
    • 예: 문자열 aaab의 경우, a는 1, b는 0으로 매핑되어 1110으로 압축됨

접두사 없는 코드

  • 접두사 없는 코드란?
    • 어떤 코드 단어도 다른 코드 단어의 접두사가 되지 않도록 함
    • 예: aaabc의 경우, a는 1, b는 00, c는 01로 매핑되어 1110001로 압축됨

접두사 없는 코드 생성

  • 접두사 없는 코드 생성 방법
    • 모든 문자를 완전 이진 트리의 잎으로 배치
    • 왼쪽 가지는 1, 오른쪽 가지는 0으로 라벨링
    • 루트에서 잎까지의 경로가 각 문자의 코드 단어를 설명함

코더 작성

  • 타입 정의

    • Bit, Code, FreqMap, CodeMap, Weight, HTree 타입 정의
    • HTree는 Leaf와 Fork로 구성됨

  • 인코딩 함수

    • 문자열을 비트로 변환하는 함수
    • FreqMap을 사용하여 각 문자의 빈도를 계산하고, 이를 기반으로 Huffman 트리를 생성함
    • Huffman 트리에서 각 문자의 코드 단어를 생성함

  • 디코딩 함수

    • 비트를 원래 문자열로 변환하는 함수
    • Huffman 트리를 사용하여 비트를 순차적으로 디코딩함

바이너리 파일과의 연동

  • 바이너리 데이터 인코딩
    • Data.ByteString.Char8 모듈을 사용하여 바이트를 문자로 읽음
    • 텍스트 코더를 사용하여 바이너리 데이터를 인코딩함

직렬화

  • 직렬화 함수
    • FreqMap과 비트를 실제 바이트로 변환하여 파일에 저장함
    • Put 모나드를 사용하여 효율적으로 ByteString을 생성함

역직렬화

  • 역직렬화 함수
    • 파일에서 읽은 데이터를 FreqMap과 비트로 변환함
    • Get 모나드를 사용하여 FreqMap을 역직렬화함

전체 코드 통합

  • 파일 압축 및 해제 함수
    • compress 함수: 파일을 읽어 빈도 맵을 생성하고, 데이터를 인코딩하여 압축 파일로 저장함
    • decompress 함수: 압축 파일을 읽어 데이터를 디코딩하여 원래 파일로 저장함

개선 사항

  • 멀티스레딩

    • 파일의 섹션을 병렬로 디코딩함
    • 섹션 경계와 예상 디코딩 크기를 지정하는 테이블을 추가하여 병렬 처리를 가능하게 함

  • 단일 패스 인코딩

    • 빈도 맵을 실시간으로 생성하며 인코딩함
    • 파일 시작 부분에 빈도 맵을 포함할 필요가 없음

  • 정규 Huffman 코드

    • 트리를 탐색하는 대신 벡터를 인덱싱하여 O(1) 시간 복잡도로 디코딩함

  • 더 빠른 코드 생성

    • 단일 패스 인코딩을 시도할 경우, 코드맵 생성 속도를 높여야 함

GN⁺의 의견

  • Huffman 코딩의 장점

    • 자주 등장하는 문자를 짧은 비트 시퀀스로 매핑하여 효율적인 데이터 압축을 가능하게 함
    • 메모리 사용을 최소화하면서도 큰 데이터를 처리할 수 있음

  • Haskell의 장점

    • 함수형 프로그래밍의 장점을 활용하여 모듈화된 코드를 작성할 수 있음
    • 게으른 평가를 통해 메모리 사용을 최적화할 수 있음

  • 비슷한 기능을 가진 프로젝트

    • gzip, bzip2 등 다양한 데이터 압축 도구가 존재함
    • 각 도구의 장단점을 비교하여 적절한 도구를 선택하는 것이 중요함

  • 새로운 기술 도입 시 고려 사항

    • 성능과 메모리 사용량을 고려하여 적절한 알고리듬을 선택해야 함
    • 단일 패스 인코딩과 같은 최적화 기법을 적용하여 효율성을 높일 수 있음
▲
GN⁺ 2024-07-06  [-]
Hacker News 의견

  • 배열 기반의 인플레이스 알고리즘이 존재하여 트리를 할당하고 포인터를 추적할 필요가 줄어듦

    • 대학에서 트리 기반 접근 방식을 배울 때 다른 방법이 있는지 몰랐음
    • 트리 접근 방식이 직관적이고 유익하지만, 많은 데이터를 빠르게 처리해야 할 때는 인플레이스 배열을 사용하는 것이 더 합리적임
    • 참고 문헌: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

  • 코드 단어가 다른 코드 단어의 접두사가 되지 않도록 해야 한다는 것은 기술적으로 정확하지 않음

    • 유일하게 디코딩 가능한 코드 클래스는 접두사 코드의 상위 집합임
    • 예를 들어, 접두사 코드의 역순은 여전히 명확하게 디코딩 가능함
    • 예시 코드: 
      a 1
b 00
c 10
    • 'a'의 코드가 'c'의 코드의 접두사이지만, 역순으로 처리하면 명확하게 디코딩 가능함

  • Haskell 프로그램 작성에 대한 더 고급 기능(모나드 변환기, 렌즈 등)을 다루는 유사한 튜토리얼이 있는지 궁금함

  • Coursera의 함수형 프로그래밍 코스(Scala)에서 유사한 Huffman 코딩 과제를 제공함

  • Huffman 코드를 사용하여 MICMAC 프로세서 매크로 프로그램을 최소한의 마이크로사이클과 마이크로명령으로 실행했음

    • 매크로 명령어의 히스토그램을 작성하고, 이를 기반으로 프로그레시브 디코딩 마이크로코드 프로그램을 작성했음
    • 실제로는 느리고 불편했을 것임
    • Huffman 코드의 장점은 값의 분포에 따라 접두사 깊이를 조절할 수 있다는 것임
    • 비초과파이프라인 프로세서 모델에서 분기 예측을 처리해야 했음

  • Huffman 코딩에 대한 추가 정보: Rosetta Code Huffman Coding

  • Haskell 프로그래머를 위한 질문: 최적화된 코드를 작성하려는 프로그래머에게 Haskell의 성능은 어떤지 궁금함

    • 특히 행렬 연산과 SIMD를 활용하는 수치 계산 성능에 관심이 있음

  • 공유해줘서 고맙다는 의견

  • "Creating prefix-free codes" 섹션의 표에 오타가 있음

    • D는 '0010'이어야 함 (현재는 '0110'으로 잘못 표기됨)
    • 그 외에는 훌륭한 읽을거리였음

  • 산술 코드는 거의 모든 면에서 더 나음

    • 더 적은 RAM과 코드로 구현 가능함
    • 더 나은 압축 및 디컴프레션 비율을 제공함
    • 스트림 중에 다른 기호가 나타날 확률을 동적으로 업데이트하기 더 쉬움
    • Huffman 코드는 먼저 발명되었고 산술 코드는 특허가 있었기 때문에 사용됨
    • 현재 특허가 만료되었으므로 더 나은 설계를 사용해야 함
답변달기