런렝스 인코딩
IT 위키
런렝스 인코딩(영어: Run-Length Encoding, RLE)은 동일한 값이 연속적으로 반복되는(run) 구간을 압축하여, 데이터 크기를 줄이는 단순한 무손실 압축 기법이다. 주로 데이터에 반복 구간이 많거나 희소 데이터(sparse data)에서 효과적이다.
개요[편집 | 원본 편집]
- 연속된 동일 값을 (값, 반복 길이) 쌍으로 표현한다.
- 예: [0, 0, 0, 3, 3, 1, 0, 0] → [(0,3), (3,2), (1,1), (0,2)]
- 일반적으로 흑백 이미지, 단순 그래픽, 희소 행렬 등에서 많이 사용된다.
- 단순성과 구현 용이성 때문에 가장 오래되고 널리 쓰이는 압축 방식 중 하나이다.
원리[편집 | 원본 편집]
- 원본 데이터에서 연속(run) 구간을 찾는다.
- 해당 값을 기록하고, 연속 길이를 함께 저장한다.
- 디코딩 시에는 (값, 길이) 쌍을 풀어서 원래 데이터로 복원한다.
특징[편집 | 원본 편집]
- 장점
- 구현이 매우 단순하고 인코딩/디코딩 속도가 빠르다.
- 반복 구간이 많을수록 압축 효율이 높다.
- 텍스트, 이미지, 희소 데이터 등 다양한 도메인에 적용 가능하다.
- 단점
- 반복 구간이 적을 경우 압축 효율이 떨어지고, 오히려 데이터가 더 커질 수 있다.
- 임의 접근(random access)이 어렵다.
응용[편집 | 원본 편집]
- 이미지 압축 : TIFF, BMP 같은 포맷에서 픽셀 데이터 압축에 사용
- 팩스 전송 : 흑백 문서의 빈 공간(white run)과 글자 부분(black run)을 압축하여 전송
- 데이터베이스 : 희소 데이터 표현 최적화
- 머신러닝 : 희소 텐서 표현, 딥러닝 모델 파라미터 압축
변형[편집 | 원본 편집]
- RLC(Run-Length Coding)라고도 불리며, 동일한 개념으로 사용된다.
- 희소 행렬 표현에서는 값과 0의 길이를 분리하여 저장하는 변형이 사용되기도 한다.
- 허프만 코딩이나 다른 엔트로피 인코딩과 결합하여 효율을 높이는 경우도 있다.
같이 보기[편집 | 원본 편집]
참고 문헌[편집 | 원본 편집]
- Khalid Sayood, Introduction to Data Compression, Morgan Kaufmann, 2017.
- David Salomon, Data Compression: The Complete Reference, Springer, 2007.
