런 길이 인코딩

Run-length encoding
런 길이 제한과 혼동하지 마십시오.

RLE(Run-Length Encryption, RLE)는 데이터의 런(많은 연속적인 데이터 요소에서 동일한 데이터 값이 발생하는 순서)을 원본 런이 아닌 단일 데이터 값과 카운트로 저장하는 무손실 데이터 압축의 한 형태다.이는 아이콘, 선 도면, 콘웨이 게임, 애니메이션과 같은 간단한 그래픽 이미지 등 많은 실행이 포함된 데이터에서 가장 효율적이다.실행 횟수가 많지 않은 파일의 경우 RLE는 파일 크기를 늘릴 수 있다.

RLE는 또한 흑백 이미지를 압축하기 위해 CompuServe가 지원하는 초기 그래픽 파일 형식을 참조하기 위해 사용될 수 있지만, 그들의 후기 GIF(Graphics Interchange Format)로 대체되었다.RLE는 또한 확장자가 있는 Windows 3.x에서 거의 사용되지 않는 이미지 형식을 가리킨다.rle윈도우즈 3.x 시작 화면을 압축하는 데 사용되는 런 길이 인코딩 비트맵입니다.

예

가상의 스캔 라인 위에 흰색 바탕에 일반 흑색 텍스트가 포함된 화면을 다음과 같이 렌더링할 수 있다.

12W1B12W3B24W1B14W

이는 12 Ws, 1 B, 12 Ws, 3 B 등의 순서로 해석할 수 있으며, 단 18개에서 원래의 67자를 나타낸다.영상의 저장에 사용되는 실제 형식은 이와 같은 ASCII 문자보다는 일반적으로 이진 형식이지만 원칙은 그대로 유지된다.심지어 이진 데이터 파일도 이 방법으로 압축할 수 있다; 파일 형식 사양은 종종 파일의 반복 바이트를 패딩 공간으로 명령한다.그러나 DEFLATE와 같은 새로운 압축 방법은 LZ77 기반 알고리즘을 사용하는 경우가 많은데, 이 알고리즘은 문자열을 사용할 수 있는 런 길이 인코딩의 일반화(예:BWWBWWBWWBWW).

런 길이 인코딩은 데이터 속성과 추가 압축 알고리즘을 수용하기 위해 여러 가지 방법으로 표현할 수 있다.예를 들어, 하나의 인기 있는 방법은 두 개 이상의 문자로만 실행 길이를 인코딩하고, 실행을 식별하기 위해 "탈출" 기호를 사용하거나, 문자 자체를 탈출구로 사용하여, 문자가 두 번 나타날 때마다 실행을 나타낸다.앞의 예에서, 이것은 다음과 같은 것을 제공할 것이다.

WW12BWW12BB3WW24BWW14

이것은 12W의 달리기, B의 달리기, 12W의 달리기, 3B의 달리기 등으로 해석될 것이다.실행 빈도가 낮은 데이터에서는 압축률을 크게 개선할 수 있다.

한 가지 다른 문제는 추가 압축 알고리즘의 적용이다.런을 추출하더라도 다른 문자의 빈도가 커서 추가 압축이 가능할 수 있지만, 런이 발생한 위치의 파일에 런 길이가 기록되면 이러한 숫자의 존재는 정상적인 흐름을 방해하고 압축을 어렵게 한다.이를 극복하기 위해 일부 런 길이 인코더는 데이터 및 이스케이프 기호를 런 길이와 구분하여 두 개를 독립적으로 처리할 수 있도록 한다.예제 데이터의 경우, 이렇게 하면 두 개의 출력, 즉 문자열 "이 된다.WWBWWBBWWBWW" 및 숫자 (12,12,3,24,14).

기록 및 응용 프로그램

RLE(Run-Length Encryption) 체계는 1967년까지 아날로그 텔레비전 신호 전송에 사용되었다.[1]1983년, 런 길이 인코딩은 히타치에 의해 특허를 받았다.[2][3][4]RLE는 특히 컴퓨터 아이콘과 같은 팔레트 기반의 비트맵 이미지에 잘 어울리며 GIF와 같은 보다 정교한 포맷이 등장하기 전 CompuServe와 같은 초기 온라인 서비스에서 인기 있는 이미지 압축 방식이었다.[5]영상 블록을 변환하고 정량화한 후 남는 계수에 JPEG가 사용하지만 사진 등 연속 톤 영상에 대해서는 잘 작동하지 않는다.

런 길이 인코딩 데이터의 일반적인 형식에는 Truevision TGA, PackBits, PCX 및 ILBM이 포함된다.국제전기통신연합은 또한 T.45로 알려진 팩스기의 런-길이 색상을 인코딩하는 표준을 설명한다.[6]수정 허프먼 코딩에 다른 기법과 결합한 이 표준은 팩스로 된 대부분의 문서는 일반적으로 백색 공간이며, 때때로 흑색 간섭이 발생하기 때문에 비교적 효율적이다.[citation needed]

참고 항목

참조

  1. ^ Robinson, A. H.; Cherry, C. (1967). "Results of a prototype television bandwidth compression scheme". Proceedings of the IEEE. IEEE. 55 (3): 356–364. doi:10.1109/PROC.1967.5493.
  2. ^ "Run Length Encoding Patents". Internet FAQ Consortium. 21 March 1996. Retrieved 14 July 2019.
  3. ^ "Method and system for data compression and restoration". Google Patents. 7 August 1984. Retrieved 14 July 2019.
  4. ^ "Data recording method". Google Patents. 8 August 1983. Retrieved 14 July 2019.
  5. ^ Dunn, Christopher (1987). "Smile! You're on RLE!" (PDF). The Transactor. Transactor Publishing. 7 (6): 16–18. Retrieved 2015-12-06.
  6. ^ Recommendation T.45 (02/00): Run-length colour encoding. International Telecommunication Union. 2000. Retrieved 2015-12-06.

외부 링크