런 길이 부호화
런 길이 부호화은 연속해서 반복되는 같은 기호를 반복 횟수와 기호의 묶음으로 표현한다 무손실 데이터 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 무손실 데이터 압축 |
|---|---|
| 주요 목적 | 연속해서 반복되는 같은 기호를 반복 횟수와 기호의 묶음으로 표현한다 |
| 핵심 방법 | 현재 기호와 동일한 다음 기호를 세다가 기호가 달라지면 run의 길이와 값을 출력한다 |
| 복잡도 | 입력·출력 크기에 선형 O(n) 시간, 일정한 작업 공간 가능 |
| 적용 조건 | run의 표현과 길이 한계, 압축되지 않는 구간의 처리 규칙이 필요하다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
런 길이 부호화은 연속해서 반복되는 같은 기호를 반복 횟수와 기호의 묶음으로 표현한다 무손실 데이터 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 현재 기호와 동일한 다음 기호를 세다가 기호가 달라지면 run의 길이와 값을 출력한다. 매우 긴 run과 리터럴 처리 방식은 파일 형식에 따라 달라진다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 입력·출력 크기에 선형 O(n) 시간, 일정한 작업 공간 가능 실제 구현에는 run의 표현과 길이 한계, 압축되지 않는 구간의 처리 규칙이 필요하다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 팩스·비트맵 및 전처리 압축에 사용한다. 반복이 적은 데이터에서는 오히려 출력 크기가 증가할 수 있다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]