반복 길이 부호화

위키백과 ― 우리 모두의 백과사전.

반복 길이 부호화(RLE, Run-length encoding)는 매우 간단한 비손실 압축 방법으로, 데이터에서 같은 값이 연속해서 나타나는 것을 그 갯수와 반복되는 값만으로 표현하능 방법이다. 이 방법은 아이콘 등의 간단한 이미지와 같이 연속된 값이 많이 있는 데이터에 효과적이다.

예를 들어서, 흰 바탕에 검은 글자가 나오는 스크린을 생각하면 이 스크린에는 연속된 흰 픽셀이 많이 나타날 것이다. 이러한 스크린의 한 스캔 라인이 다음과 같다고 가정하자. (흰 픽셀을 W로 표시하고 검은 픽셀을 B로 표시한다)

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

위의 데이터를 간단한 반복 길이 부호를 사용해서 압축하면 다음과 같은 결과를 얻을 수 있다.

12WB12W3B24WB14W

이는 "12개의 W, (한 개의) B, 12개의 W, 3개의 B, 24개의 W, (한 개의) B, 14개의 W"로 해석한다. 위의 예제의 경우, 압축 전에는 67글자였으나 압축 후에는 단지 16글자만으로 표현할 수 있다. 물론 실제로 이러한 이미지는 바이너리 포맷으로 저장되며 반복되는 길이를 저장하는 방법도 다양하지만, 기본적인 개념은 동일하다.

반복 길이 부호화를 사용하는 대표적인 파일 형식으로 PCX, BMP, ILBM 등이 있다.

반복 길이 부호화는 "BWWBWWBWWBWW"와 같이 데이터가 일정한 패턴을 따르는 경우를 처리할 수 없으며, 이런 경우 LZ77이나 LZ78 계열 알고리즘들이 유리하다. 또한 이 방법은 연속된 색조로 이루어진 이미지에도 그리 잘 사용되지 않으며, 이런 용도로는 별도의 변환과 양자화를 사용하는 JPEG와 같은 방법이 사용된다.