Run Length Encoding(RLE)이란?

Run Length Encoding(RLE)이란?

 

 

Run Length Encoding(RLE)이란?

 

반복되는 데이터 값을 효율적으로 압축하는 간단한 무손실 압축 방법이다.

같은 데이터가 연속적으로 나오는 경우, 그 데이터를 모두 저장하는 대신 값과 반복 횟수만을 저장하여 메모리 사용을 줄일 수 있다.

계산이 간단하여 구현이 쉬우며, 반복되는 값이 많은 데이터에서 높은 압축률을 기대할 수 있다.

하지만, 데이터의 반복이 적으면 오히려 압축 결과가 원본보다 커질 수 있으므로 RLE는 단순한 그래픽(아이콘 등)에 적합하여 일반적인 텍스트나 고해상도 사진에는 효과적이지 않다.

• 적용 예시
  1. 이미지 압축 : 비트맵(BMP) 이미지나 흑백, 색상 개수가 적은 아이콘 등
  2. 텍스트 압축 : 특정 문자가 연속적으로 반복되는 경우
  3. 데이터 통신 : 데이터 전송 시 반복적인 패턴을 압축하여 네트워크 대역폭을 절약할 수 있음
  4. 특히 FPGA 같이 메모리가 제한된 시스템에 유용하게 사용됨

 

 

RLE 기본 압축

1. 압축이 된 경우

• 원본 데이터 AAAAAABBBCCCCCCDD
• 압축 데이터 6A3B6C2D (A 6개, B 3개, C 6개, D 2개)

 

2. 압축이 되지 않은 경우

• 원본 데이터 ABCD
• 압축 데이터 1A1B1C1D (A 1개, B 1개, C 1개, D 1개)
• 압축을 시도한 후에 오히려 데이터의 사이즈가 증가했다. 이는 데이터가 반복되지 않을 때는 압축을 하지 않아야 된다는 것을 의미한다. 즉, 데이터가 반복될 때와 아닐 때를 구분할 필요가 있다.
  
  

 

반복 여부를 구분하는 RLE

1. 플래그 비트 사용

• 반복 구간 : 플래그 비트가 1
  
  • 형식 : [1][반복 횟수][값]
• 반복되지 않는 구간 : 플래그 비트가 0
  
  • 형식 : [0][길이][원본 데이터]
• 적용 예시
  • AAAABBCDEEEE  → [1][4][A] [1][2][B] [0][3][CDE] [1][4][E]
    
    

 

2. 구분자(Separator) 사용

• 반복 구간 : 구분자(Separator) 사용 
• 적용 예시
  
  • AAAABBCDEEEE  → 04A02BCD04E
  • 여기서 0은 구분자 역할을 한다.
• 구분자와 반복되지 않는 데이터가 같은 값인 경우 혼동이 생길 수 있다. 이 경우 구분자를 2개 사용하여 구분한다.
  
  • AAAABBC0DEEEE  → 004A002BC0D004E
  • 여기서 00은 구분자 역할을 한다.