알고리즘) 문자열 압축

 
 압축비율 할때는 어차피 4비트니깐 굳이 이진수로 표현할필요없이 몇덩어리인지만 알면 된나 

 

 

 

 

 

 

 
 
 

1. 데이터 압축의 기초 개념

압축을 하는 이유와 분류

데이터를 압축하면 파일의 크기가 줄어들어 저장 공간을 절약할 수 있고, 네트워크를 통해 파일을 전송할 때 걸리는 시간도 단축할 수 있습니다. 압축 방식은 복원 결과에 따라 두 가지로 분류됩니다.

• 무손실 압축 (Lossless Compression): 압축 후 복원한 데이터(b')가 원래 데이터(b)와 완전히 일치하는 방식입니다. 텍스트 데이터의 경우 데이터가 조금이라도 달라지면 안 되므로 반드시 무손실 압축을 해야 합니다. 단, 손실 압축에 비해 압축률이 다소 낮다는 한계가 있습니다.
• 손실 압축 (Lossy Compression): 복원된 데이터가 원본과 일치하지 않는 방식입니다. 하지만 압축률이 매우 높기 때문에 사람의 시각이나 청각이 미세한 차이를 쉽게 인지하지 못하는 멀티미디어 데이터(MP3, JPEG, MPEG 등) 분야에서 주로 사용됩니다.

압축률의 정의

이 강의(교재)에서는 압축률을 다음과 같이 정의합니다.
압축률 = 압축된 데이터 크기(cb) / 원래 데이터 크기(b)

• 예를 들어, 원래 100MB인 파일을 압축하여 10MB로 줄였다면 압축률은 0.1(10%)이 됩니다.
• 즉, 압축률 수치가 작을수록 더 많이 압축된 것을 의미합니다. (학자에 따라 이를 1 - (cb/b)로 정의하여 줄어든 비율을 압축률로 보기도 하므로 혼동하지 않도록 주의가 필요합니다.)

---

2. 고정 길이 코드 (Fixed-Length Code)와 비트 단위 I/O

고정 길이 코드 예시: 유전자 코드 (DNA)

유전자 코드는 오직 네 가지 알파벳 A, C, T, G로만 구성되어 있습니다.

• 이 문자들을 일반적인 아스키(ASCII) 코드로 표현하면 문자당 8비트가 소요됩니다.
• 하지만 문자의 종류가 4개뿐이므로, A=00, C=01, T=10, G=11과 같이 2비트로만 매핑하여 표현할 수 있습니다.
• 이 경우 압축률은 2/8 = 25%가 되어 파일 크기가 원본 대비 1/4로 줄어듭니다.
• 이처럼 모든 문자를 동일한 비트 길이(k 비트)의 코드로 변환하는 방식을 고정 길이 코드라고 부릅니다. k 비트의 코드를 사용하면 최대 2^k개의 서로 다른 문자를 표현할 수 있습니다.

비트 단위 I/O 연산의 필요성

디스크나 메모리에서 데이터를 읽고 쓸 때 시스템이 지원하는 가장 작은 기본 단위는 바이트(8비트) 단위입니다. 하지만 압축을 진행하면 2비트, 3비트, 혹은 5비트 등 바이트보다 작은 단위로 데이터를 읽고 써야 할 일이 발생합니다. 이를 위해 물리적으로는 바이트 단위로 입출력(I/O)을 하되, 내부 버퍼 내에서 **비트 와이즈 연산(Bitwise Operation)**을 통해 비트 단위로 데이터를 쪼개어 가져오는 시스템 클래스가 필요합니다.
강의에서는 자바(Java)로 구현된 BinaryStdIn 클래스의 readBoolean() 메서드를 통해 이 원리를 설명합니다.

• 내부 버퍼(buffer): 시스템으로부터 읽어온 1바이트 데이터가 저장되는 공간입니다.
• 카운트(count): 현재 버퍼 안에 유효한 비트가 몇 개 남아 있는지를 추적합니다. (초기값 혹은 버퍼를 채운 직후에는 8)
• fillBuffer() 동작: 입력 스트림에서 1바이트를 읽어 버퍼에 채우고 count를 8로 설정합니다. 파일 끝(EOF)에 도달하면 버퍼와 count를 -1로 설정합니다.
• readBoolean() 동작:
  1. count 값을 1 감소시킵니다.
  2. 현재 버퍼 안의 비트들을 count만큼 오른쪽 시프트(>>>) 연산하고 최하위 비트와 1을 AND 연산(&)하여 가장 상위 비트부터 하나씩 추출합니다.
  3. 추출한 비트가 1이면 true, 0이면 false를 반환합니다.
  4. count가 0이 되면 다음 바이트를 가져오기 위해 fillBuffer()를 호출합니다.

이진 데이터 표현의 효율성 (날짜 저장 예시)

1999년 12월 31일이라는 데이터를 파일에 저장하는 방식을 비교해 보면 이진 표현의 장점을 명확히 알 수 있습니다.

1. 텍스트(문자열) 표현: "12/31/1999"로 저장할 경우 슬래시를 포함해 총 10바이트가 필요하며, 이는 80비트에 해당합니다.
2. 일반 정수(Integer) 표현: 월, 일, 년을 각각 4바이트 정수로 저장하면 3 x 4바이트 = 12바이트가 되어 96비트가 소요됩니다. (숫자가 작을 때는 텍스트보다 비효율적일 수 있습니다.)
3. 필드별 맞춤 비트 표현:
   • 월(Month): 1~12월까지 있으므로 4비트(0 ~ 15 표현 가능)로 충분합니다.
   • 일(Day): 1~31일까지 있으므로 5비트(0 ~ 31 표현 가능)로 충분합니다.
   • 연도(Year): 넉넉히 4000년 대까지 고려해 12비트(0 ~ 4095 표현 가능)로 설정합니다.
   • 합계: 4 + 5 + 12 = 21비트가 필요합니다. 파일 저장을 위해 8의 배수로 정렬하더라도 3비트만 패딩하여 총 **24비트(3바이트)**로 날짜 하나를 온전히 저장할 수 있습니다. 텍스트 방식(80비트)에 비해 매우 효율적입니다.

---

3. 압축 알고리즘의 한계

이론적으로 모든 비트 스트림을 압축할 수 있는 단일 알고리즘은 존재하지 않습니다. 만약 어떤 알고리즘이 임의의 모든 데이터를 항상 더 작게 압축할 수 있다면, 압축된 결과물을 다시 동일한 알고리즘으로 반복 압축하여 결국 크기를 0 비트로 만들 수 있다는 모순이 생기기 때문입니다. 따라서 특정 데이터 유형과 패턴에 특화된 알고리즘을 선택해야 합니다.

---

4. 런렝스 코딩 (Run-Length Encoding, RLE)

동작 원리

런렝스 코딩은 데이터 내에 동일한 비트(0 또는 1)가 연속해서 나타나는 빈도가 높을 때 유용한 압축 방식입니다. 연속된 비트 패턴을 '값 자체'로 나열하는 대신, **'연속된 개수(Run length)'**를 고정된 k 비트 크기의 숫자로 기록하며, 0과 1이 번갈아 가며 나타난다고 상정합니다.

• 예를 들어, k = 4일 때 표현할 수 있는 최대 개수는 2^4 - 1 = 15입니다.
• 만약 연속된 개수가 15를 초과하는 경우(예: 0이 23개 연속)에는 다음과 같이 나누어 표현합니다.
  1. 0이 15개 연속되어 있음을 기록합니다. (1111)
  2. 0과 1이 교차해야 하므로, 사이에 1이 0개 연속되어 있음을 기록합니다. (0000)
  3. 남은 0이 8개 연속되어 있음을 기록합니다. (1000)

연습 문제 풀이 (수업 내용 기반)

문제: 0이 23개, 1이 3개, 0이 12개, 1이 18개 연속된 스트림(M)이 있고, k = 4일 때 압축 결과와 압축률을 구하시오.

• 원래 데이터 길이: 23 + 3 + 12 + 18 = 56비트
• k=4일 때의 그룹 분할:
  1. 0이 23개 -> 15개(0), 0개(1), 8개(0)
  2. 1이 3개 -> 3개(1)
  3. 0이 12개 -> 12개(0)
  4. 1이 18개 -> 15개(1), 0개(0), 3개(1)
     • 연속 개수 시퀀스: 15, 0, 8, 3, 12, 15, 0, 3 (총 8개 블록)
     • 이진수 변환 (k=4): 1111, 0000, 1000, 0011, 1100, 1111, 0000, 0011
• 압축된 데이터 길이: 8 x 4비트 = 32비트
• 압축률: 32/56 = 약 57.1%

만약 k = 5로 설정한다면? (최대 표현 가능 개수: 31)

• k=5일 때의 그룹 분할:
  1. 0이 23개 -> 23개(0) (31 이하이므로 한 번에 표현 가능)
  2. 1이 3개 -> 3개(1)
  3. 0이 12개 -> 12개(0)
  4. 1이 18개 -> 18개(1)
     • 연속 개수 시퀀스: 23, 3, 12, 18 (총 4개 블록)
     • 이진수 변환 (k=5): 10111, 00011, 01100, 10010
• 압축된 데이터 길이: 4 x 5비트 = 20비트
• 압축률: 20/56 = 약 35.7% (이 조건에서는 k=5가 훨씬 효과적입니다.)

런렝스 코딩의 장단점

• 동일한 비트가 길게 연속되는 환경에서는 비트 크기가 큰 k를 쓰는 것이 좋고, 0과 1이 자주 교차하는 환경에서는 작은 k가 유리합니다.
• 텍스트 파일에서의 한계: 일반적인 영어 텍스트 아스키코드는 문자마다 8비트 내에서 0과 1이 매우 빈번하게 섞여 있으므로, 런렝스 코딩을 적용하면 오히려 원본보다 크기가 커질 수 있어 부적합합니다. 반면, 문서 스캔 이미지(흰 배경은 0, 글자는 1)처럼 특정 영역이 길게 연속되는 이미지 데이터에서는 매우 효과적입니다.

---

5. 허프만 압축 (Huffman Compression)

텍스트 파일처럼 문자 단위로 압축을 진행할 때 가장 널리 쓰이는 알고리즘 중 하나입니다. 가변 길이 코드(Variable-Length Code) 방식을 사용하여 자주 등장하는 문자에는 짧은 비트 코드를, 거의 등장하지 않는 문자에는 긴 비트 코드를 부여합니다.

접두사 코드 (Prefix-free Code)의 필요성

문자마다 비트 길이가 달라질 경우, 압축을 해제할 때 어디서 비트를 잘라 읽어야 하는지 모호해지는 문제가 발생할 수 있습니다.

• 예를 들어, A=0, B=1, R=00으로 코드를 부여했다고 가정해 보겠습니다.
• 이때 압축 데이터가 0100으로 저장되어 있다면, 이것이 ABR(0 + 1 + 00)인지, ABA(0 + 1 + 0 + 0)인지 모호해집니다.
• 이 문제를 해결하기 위해 어떤 문자의 코드도 다른 문자의 접두사(시작 부분)가 되지 않도록 설계해야 합니다. 이를 **접두사 코드(Prefix-free Code)**라고 하며, 허프만 압축은 이 규칙을 준수합니다.

허프만 트리(Huffman Tree) 구축 알고리즘

접두사 코드를 생성하기 위해 **최소 이진 힙(Min-Priority Queue)**을 사용하여 허프만 트리를 만듭니다.

1. 빈도수 조사: 입력 텍스트를 한 번 훑으며 각 문자가 등장하는 빈도수(Frequency)를 계산합니다.
2. 노드 초기화: 등장하는 각 문자와 해당 빈도수를 가지는 리프 노드들을 생성하고, 이를 최소 우선순위 큐(Min-PQ)에 전부 삽입합니다. 이 큐는 빈도수가 작을수록 우선순위가 높습니다.
3. 트리 결합: 큐에 노드가 단 하나만 남을 때까지 다음 과정을 반복합니다.
   • 큐에서 빈도수가 가장 작은 두 노드 x와 y를 제거합니다.
   • 새로운 부모 노드를 생성합니다. 부모 노드의 빈도수는 x와 y의 빈도수의 합(x의 빈도수 + y의 빈도수)이 되며, 자식 문자 정보는 null이 됩니다. 왼쪽 자식에는 x를, 오른쪽 자식에는 y를 연결합니다.
   • 새로 만든 부모 노드를 다시 큐에 삽입합니다.
4. 루트 노드: 마지막으로 큐에 남은 하나의 노드가 허프만 트리의 루트(Root)가 됩니다.

트리가 완성되면 루트에서 왼쪽 가지로 내려갈 때는 0, 오른쪽 가지로 내려갈 때는 1을 부여하여 각 리프 노드에 도달하는 경로를 해당 문자의 압축 코드로 삼습니다. 문자들이 오직 단말(리프) 노드에만 존재하기 때문에 자연스럽게 접두사 조건이 만족됩니다.

압축 파일의 구조와 트리의 직렬화(Serialization)

복원(Decompression)을 하려면 압축을 진행할 때 사용했던 허프만 트리의 구조를 복원기가 알 수 있어야 합니다. 따라서 압축 파일 앞부분에 트리 구조를 헤더 형식으로 기록해야 합니다.
강의에서는 테이블(조회표) 대신 트리 구조 자체를 전위 순회(Preorder Traversal) 방식으로 이진 파일에 기록하는 효율적인 기법을 설명합니다.

• 내부 노드(Internal Node)를 방문했을 때: 파일에 비트 0을 쓰고, 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 계속 씁니다.
• 리프 노드(Leaf Node)를 방문했을 때: 파일에 비트 1을 쓴 뒤, 해당 노드가 가진 실제 문자 데이터(예: 아스키코드 8비트)를 그대로 기록합니다.

트리 복원 예제: 만약 파일 앞부분에서 읽은 비트 스트림이 다음과 같다고 가정해 보겠습니다.
0 (내부) -> 0 (내부) -> 1 (리프) 'a' -> 1 (리프) 'b' -> 0 (내부) -> 0 (내부) -> 1 (리프) 'd' -> 1 (리프) 'e' -> 1 (리프) 'c'
이 스트림을 순서대로 읽으며 트리를 재구성하면 다음과 같이 완벽한 이진 트리를 그릴 수 있습니다.

1. 맨 처음 0을 읽었으므로 내부 노드(루트)를 생성하고 왼쪽으로 내려갑니다.
2. 다시 0을 읽었으므로 내부 노드를 생성하고 왼쪽으로 내려갑니다.
3. 1과 'a'를 읽었으므로 왼쪽 단말에 'a' 리프 노드를 만들고, 부모로 돌아가 오른쪽 자식으로 이동합니다.
4. 1과 'b'를 읽었으므로 오른쪽 단말에 'b' 리프 노드를 완성하고, 루트의 오른쪽 자식으로 이동합니다.
5. 이처럼 **허프만 트리의 모든 내부 노드는 자식 노드를 반드시 2개만 가진다 (Degree = 2)**는 성질이 보장되기 때문에, 중위 순회(Inorder) 정보가 없어도 전위 순회 비트 스트림(0과 1)만으로 원래의 트리 형태를 명확히 역추적하여 복원할 수 있습니다.

최종 압축 및 복원 과정 요약

• 압축(Compress):
  1. 전체 입력 데이터를 읽고 문자별 빈도수를 조사합니다.
  2. 허프만 트리를 구축하고 문자별 가변 길이 코드를 매핑한 심볼 테이블을 만듭니다.
  3. 압축 파일 헤더에 허프만 트리 구조를 기록합니다.
  4. 그 뒤에 **원본 텍스트의 전체 문자 개수(정수)**를 기록합니다. (압축 해제 시 언제 멈춰야 할지 끝을 알기 위함입니다.)
  5. 원본 데이터를 문자 단위로 읽으면서 심볼 테이블을 참조해 해당하는 가변 길이 비트 코드를 순서대로 파일에 씁니다.
• 복원(Decompress):
  1. 압축 파일의 헤더부분을 읽어 허프만 트리를 복구합니다.
  2. 그 뒤에 나오는 원본 문자 개수 정보를 읽습니다.
  3. 파일에서 비트를 한 개씩 순서대로 읽으며 복구된 허프만 트리의 루트 노드부터 탐색을 시작합니다.
     • 읽은 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 이동합니다.
     • 단말(리프) 노드에 도달하면 해당 노드에 저장된 문자를 복원 파일에 쓰고, 다시 트리의 루트 노드로 돌아가 다음 비트를 읽습니다.
  4. 이 과정을 처음에 읽어둔 원본 문자 개수만큼 반복하고 완료합니다.

 
 
 
 
 
 

1. 고정 길이 압축의 근본적인 문제점

고정 길이 압축은 DNA 유전자 코드(A, C, T, G)처럼 표현해야 할 문자의 가짓수가 매우 적고 고정되어 있을 때는 문자당 2비트씩만 할당하여 큰 효과(25%로 압축)를 볼 수 있습니다. 하지만 일반적인 텍스트나 데이터 환경에서는 다음과 같은 한계와 문제점이 발생합니다.

• ① 모든 문자의 '출현 빈도(Frequency)'를 무시함
  고정 길이 코드에서는 자주 나오는 문자나 거의 나오지 않는 문자나 모든 문자에 동일한 비트 길이(k 비트)를 부여합니다. 예를 들어, 영문 텍스트에서 가장 많이 쓰이는 알파벳 e나 a와 거의 쓰이지 않는 x, y, z가 모두 동일하게 8비트 혹은 5비트씩 차지하게 됩니다. 자주 등장하는 문자의 길이를 줄이지 못하므로 전체 파일 크기를 획기적으로 줄이는 데 한계가 있습니다.
• ② 문자 가짓수가 많아지면 압축 효율이 급격히 떨어짐
  아스키(ASCII) 코드처럼 표현해야 할 문자가 256가지라면, 고정 길이 코드를 유지하기 위해 결국 문자당 똑같이 8비트(2^8 = 256)를 줄 수밖에 없습니다. 이 경우 압축률은 8/8 = 100%가 되어 사실상 압축이 전혀 되지 않는 문제가 생깁니다.

---

2. 한계를 극복하기 위한 다음 단계로의 전환

이러한 고정 길이 방식의 한계를 극복하기 위해 제안된 것이 바로 **가변 길이 코드(Variable-Length Code)**이며, 대표적인 예가 **허프만 압축(Huffman Compression)**입니다.

• 가변 길이 코드의 핵심 아이디어:
  • 자주 등장하는 문자(예: e, a)에는 **짧은 비트(예: 1~2비트)**를 부여합니다.
  • 자주 등장하지 않는 문자(예: x, y)에는 **긴 비트(예: 10~12비트)**를 부여합니다.

이렇게 문자마다 비트 길이를 다르게 적용함으로써, 전체 텍스트를 표현할 때 사용되는 평균 비트 수를 크게 낮추어 고정 길이 방식보다 훨씬 더 높은 압축률을 달성할 수 있게 됩니다.

• 요약 (런렝스 코딩과의 연결):
  중간 단계로 언급된 런렝스 코딩은 동일한 비트가 길게 반복되는 특수한 이진 스트림을 압축하기 위해 도입되었으나, 일반적인 텍스트(아스키코드처럼 0과 1이 빈번하게 섞여 있는 데이터)에서는 압축 효과가 거의 없다는 한계가 있었습니다. 따라서 일반적인 문자열(텍스트) 압축을 위해, 각 문자의 빈도수를 반영하여 비트 길이를 유동적으로 할당하는 가변 길이 코드(허프만 압축) 단계로 넘어가게 되었습니다.

 
 
 
 
 
허프만 트리에서는 아래의 두 가지 특별한 성질 덕분에 전위 순회(비트 스트림) 하나만으로 완벽한 복원이 가능합니다.

1. 엄격한 이진 트리 (Strict / Full Binary Tree):
   허프만 트리의 모든 내부 갈림길 노드는 자식 노드를 반드시 2개만 가집니다 (자식 수인 Degree = 2)[3][4]. 자식을 1개만 갖는 노드는 절대로 존재하지 않습니다. 자식이 없거나(리프 노드, 자식 수 0개) 무조건 2개(내부 노드, 자식 수 2개)뿐입니다.
2. 명확한 노드 타입 표시 (0과 1):
   비트 스트림에서 0은 자식이 2개 있는 내부 노드임을 나타내고, 1은 자식이 더 이상 없는 단말 노드(글자)임을 명확히 표시해 줍니다[1][2].

• 결론: 0을 읽는 순간 "이 노드는 앞으로 무조건 왼쪽과 오른쪽 자식을 차례로 가져야 해"라는 정보가 확정되고, 1을 읽는 순간 "이 방향은 자식이 없는 끝부분(리프)이야"라고 확정되므로, 중위 순회 정보가 없어도 컴퓨터가 재귀적으로 호출을 멈추고 되돌아올(Backtrack) 타이밍을 완벽하게 계산할 수 있습니다[2].

 
 
 
 
 
자료구조(Tree)에서 **Degree(차수)**는 높이가 아니라 **'자식 수'**를 의미하는 것이 맞습니다
 
 
전위순회로 트리 그려야함