런 렝스 부호화
런 렝스 부호화(Run-length encoding, RLE) 또는 런 길이 부호화는 매우 간단한 비손실 압축 방법으로, 데이터에서 같은 값이 연속해서 나타나는 것을 그 개수와 반복되는 값만으로 표현하는 방법이다. 이 방법은 아이콘 등의 간단한 이미지와 같이 연속된 값이 많이 있는 데이터에 효과적이다. 런 렝스 부호화는 만화나 애니메이션 등과 같이 배경의 변화가 없는 영상에 적합한 방식이다.[1] 그러나 실제적으로 잘 적용되지 못한다. 이 방식은 3번 이상 반복되는 문자들에 대해 이용되기 때문에 영어 문장에서는 잘 수행되기 어렵다.[1]
예제
편집예를 들어서, 흰 바탕에 검은 글자가 나오는 스크린을 생각하면 이 스크린에는 연속된 흰 픽셀이 많이 나타날 것이다. 이러한 스크린의 한 스캔 라인이 다음과 같다고 가정하자. (흰 픽셀을 W로 표시하고 검은 픽셀을 B로 표시한다.)
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
위의 데이터를 간단한 반복 길이 부호를 사용해서 압축하면 다음과 같은 결과를 얻을 수 있다.
12WB12W3B24WB14W
이는 '12개의 W, (한 개의) B, 12개의 W, 3개의 B, 24개의 W, (한 개의) B, 14개의 W'로 해석한다. 위의 예제의 경우, 압축 전에는 67글자였으나 압축 후에는 단지 16글자만으로 표현할 수 있다. 물론 실제로 이러한 이미지는 바이너리 포맷으로 저장되며 반복되는 길이를 저장하는 방법도 다양하지만, 기본적인 개념은 동일하다. 이때 데이터의 크기는 67바이트에서 16바이트로 줄었으므로 압축률은 약 4.18이다.
활용
편집반복 길이 부호화를 사용하는 대표적인 파일 형식으로 PCX, BMP, ILBM 등이 있다.
반복 길이 부호화는 BWWBWWBWWBWW와 같이 데이터가 일정한 패턴을 따르는 경우를 처리할 수 없으며, 이런 경우 LZ77이나 LZ78 계열 알고리즘들이 유리하다. 또한 이 방법은 연속된 색조로 이루어진 이미지에도 그리 잘 사용되지 않으며, 이런 용도로는 별도의 변환과 양자화를 사용하는 JPEG와 같은 방법이 사용된다.