[알고리즘] Run-Length Encoding (런-렝스 부호화) 쉽게 이해하기

Run-Length부호화는, 문자열의 "중복"에 따라 압축하는 비교적 간단한 알고리즘이다.

이 인코딩 방식은 사진, 아이콘 등과 같이 "연속된 값"이 많은 데이터에 효과적이고, 애니메이션 처럼 특정 배경이 반복해서 등장하는 영상에 이용하기에 효율적이다. 

이러한 인코딩 방식을 사용하는 대표적 파일 형식은 PCX, BMP, ILBM 이 있다.

 

---

Run-Length Encoding 이해하기.

 

쉽게 이야기하면 텍스트 파일의 내용이 "AAABBCDDDDDD"로 되어 있다고 하면,

A3B2CD6으로 중복되는 문자를 치환하는 것이다. (A가 3개, B가 2개 ...)

하지만 우리가 사용하는 이진파일에서는 0과 1만 사용되기 때문에 갯수로만 표현할 수 있다.

변환된 값이 232이고 시작이 0이라면, 0011100이다.

 

조금더 나아가서, 우리가 0000000000000001111111000000011111111111 이라는 raw data를 압축하려고 한다면,

1111 0111 0111 1011 로 표현할 수 있다.

(맨 앞이 0의 개수(15) 이고 다음은 1의 개수(7), 다음은 0의 개수(7), 다음은 1의 개수(11) 이렇게 표현이 되는 것이다.)

이렇게 변환하면, 총  40글자에서 16글자로 줄어들게 된다.

 

---

우리가 표현할 수 있는 개수의 범위를 넘어가면 어떻게 해야할까?

 

그런데!!  지금 우리는 4bit 즉 0개~15개 까지만 커버 가능할 수 있다. (0000 ~ 1111)

만약에 11111111111111111111. 이렇게 1이 20개가 오는 경우에는 어떻게 표현 할 수 있을까?

 

20은 15 + 5 이다.

그렇다면 1(15개) 0(0개) 1(5개) 이렇게 표현할 수 있지 않을까?

 

위를 Run-Length 부호화로 변환한 최종적 표현은 다음과 같다.

1111 0000 0101 

이런 방식을 통해, 4bit의 최대 숫자보다 더 큰 개수도 표현할 수 있다.