6. 런-길이 인코딩 (RLE, Run-Length Encoding) — 연속 반복 압축

핵심 인사이트 (3줄 요약)

본질: RLE (Run-Length Encoding)는 동일 기호가 연속으로 반복되는 "런(Run)"을 "횟수 + 기호" 쌍으로 교체하여 데이터를 압축하는 가장 단순한 무손실 압축 알고리즘이다.

가치: 구현이 O(n)으로 매우 단순하고 하드웨어 구현도 용이하여, 반복이 많은 이진 이미지(팩스)·스캔 문서·배경이 단색인 그래픽에서 수십 배의 압축률을 달성한다.

판단 포인트: 데이터 엔트로피(무작위성)가 낮을수록(반복 많을수록) 효과적이며, 무작위 데이터(사진, 영상)에는 역효과(파일 크기 증가)가 나므로 허프만·LZ77 등 고급 알고리즘과 혼합하여 사용한다.

Ⅰ. 개요 및 필요성

디지털 팩스 전송 시 흰색 배경에 검은 텍스트가 있는 이미지는 "흰 픽셀이 200개, 검은 픽셀이 50개, 흰 픽셀이 300개..."처럼 동일 픽셀이 길게 이어진다. RLE는 이 반복 패턴을 "W200B50W300..."처럼 압축하여 전송 데이터를 대폭 줄인다. 1970년대 팩스 표준(ITU T.4)부터 현재의 BMP·PCX 포맷까지 반세기 이상 현역이다.

RLE 압축/복원

원본: AAAAABBBCCDDDDD  (15 bytes)
압축: 5A3B2C5D         (8 bytes, 47% 절감)

원본: ABCDE            (5 bytes)
압축: 1A1B1C1D1E       (10 bytes, 100% 증가!) ← 무작위 데이터 역효과

📢 섹션 요약 비유: RLE는 출석부 대신 "김철수 3번 연속 지각"이라고 요약하는 것—반복이 많으면 효과적이지만, 매번 다른 이름이 나오면 더 길어진다.

Ⅱ. 아키텍처 및 핵심 원리

RLE 인코딩/디코딩 구조

인코딩 O(n):

입력 스트림:
  W W W W W B B B W W B B B B W W W W

처리:
  W×5 → "5W"
  B×3 → "3B"
  W×2 → "2W"
  B×4 → "4B"
  W×4 → "4W"

출력: 5W3B2W4B4W  (10 토큰 vs 원본 18 픽셀)

디코딩 O(output):
  "5W" → W W W W W
  "3B" → B B B
  ...

이진 RLE (Binary RLE)

팩스(CCITT Group 3):
  이진 이미지에서 흰색/검은색 런 길이만 순서대로 나열
  (항상 흰색으로 시작하는 관례)

  원본 행: 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1
  RLE:     5 3 8 2   ← [흰5, 검3, 흰8, 검2]

  허프만 코딩과 결합: 자주 등장하는 런 길이에 짧은 코드 부여
  → CCITT Group 4 팩스 표준

이미지 포맷에서의 RLE 활용

포맷	RLE 방식	특징
BMP (RLE4/RLE8)	색상 인덱스 런 인코딩	팔레트 색상 반복 압축
PCX	행 단위 RLE	게임 스프라이트에 활용
TIFF	PackBits RLE	팩스·스캔 문서 표준
PDF	CCITT Fax	이진 이미지 압축
TGA	RLE 옵션	3D 텍스처

📢 섹션 요약 비유: 이진 이미지의 RLE는 흑백 얼룩말 무늬를 "흰 줄 3cm, 검은 줄 2cm, 흰 줄 4cm..."로 기록하는 것—그림 전체를 픽셀로 저장하지 않아도 된다.

Ⅲ. 비교 및 연결

RLE vs 다른 압축 알고리즘

알고리즘	원리	적합 데이터	압축률
RLE	연속 반복 압축	팩스, 스프라이트	낮음~매우 높음
허프만 코딩	빈도 기반 가변 코드	텍스트, 일반 데이터	중간~높음
LZ77/LZ78	슬라이딩 윈도우 사전	텍스트, 바이너리	높음
DEFLATE	LZ77 + 허프만	ZIP, PNG, HTTP	매우 높음
bzip2	BWT + RLE + 허프만	텍스트	매우 높음

bzip2 파이프라인: 원본 → RLE1 → BWT (Burrows-Wheeler Transform) → 이동 코드 (Move-to-Front) → RLE2 → 허프만 코딩 → 압축 출력
(RLE가 BWT 전후 두 번 등장)

엔트로피와 압축 한계

섀넌 엔트로피(Shannon Entropy) H = -Σ p_i log₂(p_i)

완전 반복 데이터: AAAAAAA → H → 0  →  무한 압축 가능
완전 무작위 데이터: H → 1  →  압축 불가 (RLE 역효과)

📢 섹션 요약 비유: 엔트로피는 데이터의 "놀라움 지수"—모든 픽셀이 같으면 놀랍지 않아서 RLE가 대박이고, 모든 픽셀이 달라서 계속 놀라면 RLE는 효과 없다.

Ⅳ. 실무 적용 및 기술사 판단

주요 활용 사례

팩스(Fax): ITU T.4/T.6 — 이진 RLE + 허프만으로 행 압축
스캔 PDF: 텍스트 문서의 배경 흰 픽셀 압축
게임 스프라이트: 배경 투명 픽셀(동일 색) 범위 압축
의료 영상 (DICOM): 배경이 검은 MRI/CT 스캔 이미지
원격 데스크탑 (RDP): 화면 변경이 적은 구간 반복 픽셀 압축

기술사 판단 기준

이진 이미지 + 반복 많음              →  RLE 단독 또는 RLE + 허프만
사진·영상 (높은 엔트로피)            →  JPEG(DCT), WebP, HEVC
텍스트 일반 압축                     →  DEFLATE (LZ77 + 허프만)
텍스트 고압축                        →  bzip2 (BWT + RLE + 허프만)
실시간 화면 압축 (RDP/VNC)          →  RLE 기반 행 델타 압축

📢 섹션 요약 비유: RLE는 단순하지만 강력한 첫 번째 무기—팩스 이미지처럼 흑백 줄무늬 데이터에서는 다른 어떤 고급 알고리즘보다 빠르고 간단하게 효과를 낸다.

Ⅴ. 기대효과 및 결론

RLE는 알고리즘 복잡도 O(n)의 극단적 단순함으로 반세기 이상 이진 이미지·팩스·스캔 문서의 표준 압축으로 자리 잡았다. 반복이 많은 저엔트로피 데이터에서는 뛰어난 압축률을 제공하지만, 무작위 데이터에서는 파일 크기가 오히려 증가한다. 현대 압축은 RLE를 단독으로 쓰기보다 bzip2처럼 BWT·허프만 코딩과 파이프라인으로 연결하여 시너지를 극대화한다.

결론: RLE는 가장 단순한 무손실 압축이지만 데이터 특성(반복성)을 정확히 파악하여 적용해야 하며, 고급 압축의 전처리 단계로서도 중요한 역할을 한다.

📌 관련 개념 맵

개념	관계
허프만 코딩 (Huffman Coding)	RLE와 조합하는 엔트로피 압축
LZ77 / DEFLATE	슬라이딩 윈도우 + 허프만 (ZIP/PNG)
BWT (Burrows-Wheeler Transform)	bzip2에서 RLE와 결합
섀넌 엔트로피 (Shannon Entropy)	압축 가능성의 이론적 한계
CCITT Group 3/4	팩스 표준의 RLE + 허프만
무손실 압축 (Lossless Compression)	RLE가 속하는 압축 분류

📈 관련 키워드 및 발전 흐름도

[반복 패턴 (Repetitive Pattern)]
    │
    ▼
[런 길이 부호화 (RLE, Run-Length Encoding)]
    │
    ▼
[허프만 부호화 (Huffman Coding)]
    │
    ▼
[무손실 압축 (Lossless Compression)]

이 흐름도는 반복 패턴을 RLE로 압축하고 더 나아가 허프만 부호화와 무손실 압축으로 확장되는 흐름을 보여준다.

👶 어린이를 위한 3줄 비유 설명

RLE는 색칠 공부 책에서 "파란색 10칸, 빨간색 3칸"이라고 요약하는 거야—10칸을 일일이 쓰지 않아도 돼.
하지만 모든 칸이 다른 색이면 "파1빨1노1초1..."처럼 오히려 더 길어지는 문제가 있어.
팩스 기계는 흰 종이의 흰 부분이 아주 많아서 RLE를 쓰면 전송 시간을 엄청나게 줄일 수 있어!