맨위로가기

런 렝스 부호화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

런 렝스 부호화(RLE)는 1967년부터 사용된 데이터 압축 방식이다. 반복되는 문자열을 해당 문자 하나와 반복 횟수로 표현하여 데이터 크기를 줄인다. 주로 팔레트 기반 비트맵 이미지와 팩스 문서 압축에 사용되며, 트루비전 TGA, PCX, BMP, ILBM 등의 파일 형식에서 활용된다. RLE는 연속적인 데이터에 효율적이지만, 데이터 패턴이 불규칙하거나 연속적인 색조로 이루어진 이미지에는 적합하지 않다. RLE의 변형으로는 순차 RLE, 손실 RLE, 적응형 RLE 등이 있으며, PackBits와 Switched Run Length Encoding과 같은 개선된 방식도 존재한다.

더 읽어볼만한 페이지

  • 무손실 압축 알고리즘 - VP9
    VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다.
  • 무손실 압축 알고리즘 - FLAC
    FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
런 렝스 부호화

2. 역사 및 활용

RLE 방식은 1967년부터 아날로그 텔레비전 신호 전송에 사용되었다. 1983년 히타치가 RLE 관련 특허를 취득했다.[1][2][3] RLE는 팔레트 기반 비트맵 이미지(비교적 적은 색상을 사용)에 적합하며, 컴퓨터 아이콘과 같은 초기 온라인 서비스에서 GIF와 같은 더 정교한 형식의 등장 이전에 인기 있는 이미지 압축 방법이었다.

트루비전 TGA, 팩비츠 (애플에서 제작, 맥페인트에서 사용), PCX, ILBM 등의 파일 형식에서 RLE가 사용된다. 국제 전기 통신 연합은 팩스 기기를 위한 런 렝스 컬러 부호화 표준(T.45)을 정의했다. 이 표준은 수정된 허프만 부호화에 통합되었는데, 대부분의 팩스 문서가 주로 흰색 바탕에 검은색 글자로 구성되어 있어 RLE 압축이 효율적이다.

3. 알고리즘

런 렝스 부호화는 연속된 데이터를 해당 데이터 하나와 연속된 길이로 표현하여 압축하는 알고리즘이다. 예를 들어 "A A A A A B B B B B B B B B A A A"는 "A 5 B 9 A 3"으로 표현할 수 있는데, 이는 A가 5번, 그 다음에 B가 9번, 그리고 A가 3번 연속된다는 것을 나타낸다. 연속 횟수를 원래 데이터를 나타내는 부호 앞에 기록하는 경우도 있어, "5 A 9 B 3 A"와 같이 표현되기도 한다.

데이터가 두 종류(A와 B)뿐이고 처음에 A가 온다고 정해놓으면 "5 9 3"만으로도 표현할 수 있다. 만약 B가 처음 발견된 경우, 처음에 A가 0번 연속되었다고 가정한다. 예를 들어 "B B B A A A A A B B B B B A A A"는 "0 3 5 5 3"으로 표현할 수 있다. 이러한 방식은 흰색과 검은색 외에 정보가 거의 없는 흑백 팩시밀리에서 많이 사용된다.

RLE의 공간 복잡도는 O(n)이며, 여기서 n은 입력 데이터의 크기이다. , 형태의 템플릿은 제거되었다.

3. 1. 부호화 (Encoding)

입력 데이터를 순회하면서 연속적으로 반복되는 문자의 수(런 렝스)를 센다. 문자와 해당 런 렝스를 저장한다. 예를 들어 흰 바탕에 검은 글자가 나오는 스크린을 생각하면 이 스크린에는 연속된 흰 픽셀이 많이 나타날 것이다. 이러한 스크린의 한 스캔 라인이 다음과 같다고 가정해보자. (흰 픽셀을 W로 표시하고 검은 픽셀을 B로 표시한다.)

: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

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

: 12WB12W3B24WB14W

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

다른 예시로, "A A A A A B B B B B B B B B A A A"는 "A 5 B 9 A 3"으로 표현할 수 있다. 이는 A가 5번, 그 다음에 B가 9번, 그리고 A가 3번 연속된다는 것을 나타낸다. (연속 횟수를 원래 데이터를 나타내는 부호 앞에 기록하는 경우도 있다. 이 경우 부호화 후에는 "5 A 9 B 3 A"로 표현된다).

또한, 데이터가 이 두 종류(A와 B)뿐이고, 처음에 A가 온다고 정해놓으면 "5 9 3"만으로도 표현할 수 있다. 이 규칙에 따라 B가 처음 발견된 경우, 처음에 A가 0번 연속되었다고 하면 된다. 예를 들어, "B B B A A A A A B B B B B A A A"는 "0 3 5 5 3"으로 표현할 수 있다.

3. 2. 복호화 (Decoding)

인코딩된 데이터를 순회하면서 각 개수-문자 쌍에 대해 문자를 개수만큼 반복한다. 반복된 문자들을 결과 문자열에 추가하여 원래 데이터를 재구성한다. 복호화 단계는 다음과 같다.

# 인코딩된 데이터를 순회한다.

# 각 개수-문자 쌍에 대해 문자를 개수만큼 반복한다.

# 이 문자들을 결과 문자열에 추가한다.

예를 들어, 12WB12W3B24WB14W와 같이 인코딩된 데이터가 있다면, 이를 '12개의 W, 1개의 B, 12개의 W, 3개의 B, 24개의 W, 1개의 B, 14개의 W'로 해석한다. 이 과정을 통해 원래의 데이터인 WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW를 복원할 수 있다.

3. 3. 파이썬 구현 예시

python

def rle_encode(iterable, *, length_first=True):

"""

>>> "".join(rle_encode("AAAABBBCCDAA"))

'4A3B2C1D2A'

>>> "".join(rle_encode("AAAABBBCCDAA", length_first=False))

'A4B3C2D1A2'

"""

return (

f"{ilen(g)}{k}" if length_first else f"{k}{ilen(g)}" # ilen(g): 반복 가능한 객체 g의 길이

for k, g in groupby(iterable)

)

```[4]

```python

def rle_decode(iterable, *, length_first=True):

"""

>>> "".join(rle_decode("4A3B2C1D2A"))

'AAAABBBCCDAA'

>>> "".join(rle_decode("A4B3C2D1A2", length_first=False))

'AAAABBBCCDAA'

"""

return chain.from_iterable(

repeat(b, int(a)) if length_first else repeat(a, int(b))

for a, b in batched(iterable, 2)

)

```[4]

4. 변형

런 렝스 부호화(RLE)는 데이터를 한 줄씩 처리하며 왼쪽에서 오른쪽으로 스캔하는 순차 RLE 방식을 기본으로 한다. 이미지 압축에 주로 사용되며, 데이터를 수직, 대각선, 블록 단위로 스캔하는 변형 방식도 존재한다.[1]

압축률을 높이기 위해 일부 비트를 의도적으로 삭제하는 손실 RLE 방식도 있다. 이 방식은 이미지의 시각적 품질에 최소한의 영향을 주면서 압축률을 높일 수 있다.

적응형 RLE는 런의 길이에 따라 다른 인코딩 방식을 사용한다. 예를 들어, 짧은 런과 긴 런에 대해 서로 다른 인코딩 형식을 적용하여 압축률을 최적화한다.

일반적인 RLE 방식은 연속되지 않는 데이터에 대해서는 압축률이 떨어지는 문제가 있다. 이를 해결하기 위해, 연속되지 않는 데이터가 발견된 경우에는 연속되는 데이터가 나타날 때까지의 길이를 기록하는 방식(PackBits)을 사용한다.

PackBits 부호화 예시
원본 데이터부호화된 데이터
AAAABBCCCCCCDEFG4A2B6C-4DEFG
AAAA4A
BB2B
CCCCCC6C
DEFG-4DEFG



위 표에서 -4DEFG는 "A"가 4개, "B"가 2개, "C"가 6개씩 이어지고, 압축할 수 없는 "DEFG"의 4글자가 있다는 의미이다.

PackBits 방식은 데이터 길이를 나타내는 부호(양수 또는 음수)를 통해 연속/비연속 데이터 여부를 판단하기 때문에 표현 가능한 데이터 길이가 절반(128)으로 줄어드는 단점이 있다.

이러한 단점을 보완하기 위해 코드 변화 지점에서 연속/비연속 데이터 취급을 번갈아 전환하는 스위치드 런 렝스 인코딩(Switched Run Length Encoding) 방식이 개발되었다. 이 방식은 플래그 비트[5]가 필요 없어 256 정도까지의 길이를 표현할 수 있다.

5. 한계 및 해결 방법

PCX, BMP, ILBM 등의 파일 형식이 반복 길이 부호화(RLE)를 사용한다.

RLE는 데이터가 BWWBWWBWWBWW와 같이 일정한 패턴을 따르는 경우 효율적이지 않다. 이 경우 LZ77이나 LZ78 계열 알고리즘이 더 유리하다. 연속된 색조로 이루어진 이미지에도 RLE는 적합하지 않으며, JPEG와 같이 별도의 변환과 양자화를 사용하는 방법이 더 효과적이다.

흰색 배경에 검은색 텍스트가 있는 화면을 예로 들면, 빈 공간은 긴 흰색 픽셀 열로, 텍스트 내부는 짧은 검은색 픽셀 열로 나타난다. 가상 스캔 라인을 검은색 픽셀은 B, 흰색은 W로 표현하면 다음과 같다.

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

이를 RLE로 부호화하면 다음과 같이 표현할 수 있다.

12W1B12W3B24W1B14W

이는 67개의 문자를 18개로 줄여 표현한 것이다. 실제 형식은 ASCII 문자보다는 이진 형식을 사용하지만, 원리는 동일하다. 이진 데이터 파일도 압축할 수 있으며, 파일 형식 사양에서 반복되는 바이트를 패딩 공간으로 지정하기도 한다. 그러나 DEFLATE와 같은 최신 압축 방법은 LZ77 기반 알고리즘을 사용하며, 이는 RLE의 일반화로 BWWBWWBWWBWW와 같은 문자열 열을 활용할 수 있다.

RLE는 "이스케이프" 기호를 사용하여 런을 식별하거나, 문자 자체를 이스케이프로 사용하여 문자가 두 번 나타날 때마다 런을 나타내도록 할 수 있다. 예를 들어, WW12BWW12BB3WW24BWW14는 12개의 W의 런, B, 12개의 W의 런, 3개의 B의 런 등으로 해석된다.

런을 추출한 후에도 서로 다른 문자의 빈도가 클 수 있어 추가 압축이 가능하다. 그러나 런 길이가 런이 발생한 위치의 파일에 기록되면 숫자가 정상적인 흐름을 방해하여 압축을 어렵게 만든다. 이를 해결하기 위해 일부 RLE 인코더는 데이터와 이스케이프 기호를 런 길이에서 분리하여 "WWBWWBBWWBWW"라는 문자열과 숫자(12,12,3,24,14)의 두 가지 출력을 생성한다.

RLE는 연속된 데이터를 해당 데이터 하나와 연속된 길이로 표현하여 압축하는 방식이다. 예를 들어 "AAAAABBBBBBBBBBAAA"는 "A5B9A3"으로 표현할 수 있다. 이는 A가 5번, B가 9번, A가 3번 연속된다는 의미이다. 이러한 특징 때문에 흰색과 검은색 외에 정보가 거의 없는 흑백 팩시밀리에서 많이 사용된다.

5. 1. 데이터 비연속성 문제

데이터가 연속되지 않으면 부호화 후 데이터 크기가 오히려 증가할 수 있다. 예를 들어, "A B C D A B C A B A B C D E"는 "A1B1C1D1A1B1C1A1B1A1B1C1D1E1"이 된다. 이 경우 압축률은 200%가 되어, 압축 데이터가 원래 데이터의 2배가 된다는 뜻이다.

이러한 문제를 방지하기 위한 방법 중 하나는 일정 수만큼 같은 데이터가 반복될 경우에만 런 렝스 압축을 적용하는 것이다. 다음은 그 예시를 나타낸 표이다.

원래 데이터일반적인 부호화 방법대책 완료된 부호화
ABCDDDDA1B1C1D4ABCDD2



위의 표에서 볼 수 있듯이, "대책 완료된 부호화" 방법을 사용하면 8바이트였던 원본 데이터가 6바이트로 줄어드는 것을 확인할 수 있다.

5. 2. 해결 방법

런 렝스 부호화(RLE)는 데이터가 연속되지 않으면 오히려 데이터 크기가 커지는 단점이 있다. 예를 들어 "A B C D A B C A B A B C D E"는 "A 1 B 1 C 1 D 1 A 1 B 1 C 1 A 1 B 1 A 1 B 1 C 1 D 1 E 1"로 압축되어 원래 데이터보다 2배 더 커진다.

이러한 문제를 해결하기 위해, 일정 횟수 이상 같은 데이터가 반복될 때만 RLE 압축을 적용하는 방법이 있다. 예를 들어, 아래 표와 같이 D가 4번 연속되는 경우에만 압축을 적용하면, 8바이트였던 데이터가 6바이트로 줄어든다.

원래 데이터ABCDDDD
일반적인 부호화 방법A1B1C1D4
대책이 적용된 부호화ABCDD2


5. 2. 1. PackBits

PackBits는 연속되지 않는 데이터가 발견되면, 연속되는 데이터가 나타날 때까지의 길이를 기록하는 방식이다. 아래 표는 그 예시를 보여준다.

원본 데이터AAAABBCCCCCCDEFG
부호화된 데이터4A2B6C-4DEFG



위 표에서 -4DEFG는 연속되지 않는 데이터 "DEFG"가 4글자 있다는 것을 의미한다. 즉, -가 붙은 (음수) 길이 데이터는 연속되지 않는 데이터의 길이를 나타내며, 이 예시에서는 "A"가 4개, "B"가 2개, "C"가 6개씩 이어지고, 압축할 수 없는 "DEFG"의 4글자가 있다는 의미로 부호화된다. 이 방법은 TIFF 및 PICT 등에서 사용된다.

5. 2. 2. Switched Run Length Encoding

Switched Run Length Encoding은 코드 변화 지점에서 연속 데이터와 비연속 데이터 취급을 번갈아 전환하는 방식이다. PackBits와 달리 플래그 비트[5]가 필요 없어 더 긴 길이(최대 256)를 표현할 수 있다. 이는 데이터 길이를 나타내는 부호가 연속/비연속 데이터 길이를 모두 나타내므로 표현 가능한 데이터 길이가 제한된다는 PackBits의 단점을 극복한 것이다.

데이터 "A B C D E E E E F F F F F F F"를 예로 들어 압축 방법을 설명하면 다음과 같다.

1. 먼저 비연속 데이터로 취급하여, PackBits와 마찬가지로 연속된 데이터가 나타날 때까지의 길이를 기록하고, 그 뒤에 비연속 데이터를 그대로 출력한다. (A B C D E E E E F F F F F F F → 5 A B C D E)

2. 연속된 데이터와 만나면, 다음에 연속되지 않은 데이터와 만날 때까지의 길이를 기록한다. (A B C D E E E E F F F F F F F → 5 A B C D E 3)

3. 다시, 연속된 데이터가 나타날 때까지의 길이를 기록하고, 그 뒤에 비연속 데이터를 그대로 출력한다. (A B C D E E E E F F F F F F F → 5 A B C D E 3 1 F)

4. 2와 3을 데이터의 끝까지 번갈아 반복한다. (A B C D E E E E F F F F F F F → 5 A B C D E 3 1 F 6)

복호화 방법은 다음과 같다.

1. 먼저 비연속 데이터로 취급하여, 첫 번째 문자를 읽어 길이를 구한 후, 뒤에 이어지는 비연속 데이터를 그대로 출력한다. (5 A B C D E 3 1 F 6 → A B C D E)

2. 복호화를 마치면 연속 데이터로 취급하도록 전환하여, 1개의 문자만 읽어 연속되는 길이를 구한 후, 복호화한 마지막 문자를 그 길이만큼 반복하여 출력한다. (5 A B C D E 3 1 F 6 → A B C D E E E E)

3. 다시 비연속 데이터로 취급하여, 1개의 문자를 읽어 길이를 구한 후, 이어지는 비연속 데이터를 그대로 출력한다. (5 A B C D E 3 1 F 6 → A B C D E E E E F)

4. 2와 3을 데이터의 끝까지 번갈아 반복한다. (5 A B C D E 3 1 F 6 → A B C D E E E E F F F F F F F)

참조

[1] 웹사이트 Run Length Encoding Patents http://www.ross.net/[...] Internet FAQ Consortium 1996-03-21
[2] 웹사이트 Method and system for data compression and restoration https://patents.goog[...] 1984-08-07
[3] 웹사이트 Data recording method https://patents.goog[...] 1983-08-08
[4] 웹사이트 more-itertools 10.4.0 documentation https://more-itertoo[...] 2024-08
[5] 문서 ここでは、PackBitsにおいて長さを表す符号の正負を表す1ビットで、非連続データか連続データかを区別するビット。符号付数値表現も参照
[6] 서적 멀티미디어 신호처리 사이텍미디어 2006


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com