가변 길이 부호화

부호 이론에서 가변 길이 부호화(variable-length encoding)는 컴퓨터에서 표현하기 위한 문자 집합(기호 레퍼토리)을 부호화하는 데 길이가 다른 코드를 사용하는 문자 인코딩 방식이다. 컴퓨터 과학의 동등한 개념은 비트 문자열이다.

가변 길이 코드를 사용하면 소스를 오류 없이 압축 및 압축 해제할 수 있으며(비손실 데이터 압축) 여전히 심볼별로 읽을 수 있다. 독립 동일 분포 소스는 거의 엔트로피에 가깝게 압축될 수 있다. 이는 고정 길이 부호화 방식과 대조적으로, 고정 길이 부호화 방식에서는 대량의 데이터에 대해서만 데이터 압축이 가능하며, 가능한 총 가능성의 로그를 초과하는 모든 압축은 유한한(비록 임의로 작을지라도) 실패 확률을 수반한다.

이러한 이유로, 초기 마이크로컴퓨터용 어드벤처 게임에서 영어 텍스트를 더 적은 바이트로 압축하는 데 사용되기도 했다. 그러나 디스크, 컴퓨터 메모리 증가, 범용 압축 알고리즘의 발전으로 이러한 방법은 구식이 되었다.

멀티바이트 인코딩은 기존 제약 조건과의 하위 호환성을 깨지 않으면서 인코딩할 수 있는 문자 수를 늘려야 할 필요성 때문에 생겨났다. 예를 들어, 문자당 1바이트(8비트)로는 256개의 문자를 인코딩할 수 있다. 256개 이상의 문자를 인코딩하려면 인코딩 단위당 2바이트 이상을 사용하는 것이 명확한 선택이 될 것이다. 2바이트(16비트)는 65,536개의 문자를 허용하지만, 이러한 변경은 기존 시스템과의 호환성을 깨뜨리므로 전혀 실행 불가능할 수 있다.

가능성이 낮은 소스 심볼에는 더 긴 코드워드를 할당할 수 있고, 가능성이 높은 소스 심볼에는 더 짧은 코드워드를 할당할 수 있어 낮은 기대 코드워드 길이를 제공한다. 잘 알려진 가변 길이 부호화 전략의 예로는 허프먼 부호화, 렘펠-지브 부호화, 산술 부호화, 맥락 적응 가변 길이 부호화가 있다.

 일반적인 구조 
멀티바이트 인코딩 시스템은 일부 문자를 단일 단위 코드로 유지하고 다른 문자는 여러 단위를 요구함으로써 기존 소프트웨어에 대한 중단을 최소화한다. 이는 단일톤(단일 단위로 구성), 선행 단위(여러 단위 시퀀스에서 먼저 오는 단위), 후행 단위(여러 단위 시퀀스에서 나중에 오는 단위)의 세 가지 단위 유형을 생성한다. 입력 및 디스플레이 시스템은 이러한 구조를 처리해야 하지만, 대부분의 다른 소프트웨어는 그렇지 않다.

예를 들어, ""라는 네 글자 문자열은 UTF-8로 다음과 같이 인코딩된다(십육진법 바이트 값으로 표시): . 해당 시퀀스의 여섯 단위 중 , , 는 단일톤(각각 , , 에 해당), 는 선행 단위이고 와 는 후행 단위이다. 하트 기호는 선행 단위와 두 후행 단위의 조합으로 표현된다.

UTF-8은 단일톤, 선행 및 후행 단위를 겹치지 않는 값 범위로 명확하게 구분한다. 대조적으로, 오래된 인코딩은 종종 값을 재사용하여 텍스트를 올바르게 구문 분석하기 어렵게 만든다. 이는 검색에서 오탐을 유발하거나 손상된 바이트가 긴 시퀀스를 방해할 수 있다. UTF-8과 같이 잘 설계된 인코딩에서는 검색이 안정적으로 작동하며 손상은 잘못된 단위를 포함하는 문자만 영향을 미친다.

 코드 및 그 확장 
코드의 확장은 유한 길이 소스 시퀀스를 유한 길이 비트 문자열에 매핑하는 것으로, 소스 시퀀스의 각 심볼에 대해 해당 코드워드를 연결하여 얻어진다. 형식 언어 이론의 용어를 사용하면, 정확한 수학적 정의는 다음과 같다: 와 를 각각 소스 및 대상 알파벳이라고 불리는 두 개의 유한 집합이라고 하자. 코드 는 의 각 심볼을 에 대한 심볼 시퀀스에 매핑하는 전체 함수이며, 를 에서 로의 준동형으로 확장하는 것은 각 소스 심볼 시퀀스를 대상 심볼 시퀀스에 자연스럽게 매핑하며, 이를 그 확장이라고 한다.

가변 길이 코드는 비특이 코드, 고유하게 해독 가능한 코드, 접두사 코드 순서로 엄격하게 중첩될 수 있다. 접두사 코드는 항상 고유하게 해독 가능하며, 이들은 항상 비특이적이다.

 비특이 코드 
코드는 각 소스 심볼이 다른 비어 있지 않은 비트 문자열에 매핑되는 경우 비특이적이다. 즉, 소스 심볼에서 비트 문자열로의 매핑이 단사적이다.

예를 들어, 매핑 는 와  모두 동일한 비트 문자열 에 매핑되므로 비특이적이지 않다. 이 매핑의 어떤 확장도 손실(비비손실) 부호화를 생성할 것이다. 이러한 특이 부호화는 일부 정보 손실이 허용될 때 유용할 수 있다(예를 들어, 이러한 코드가 오디오 또는 비디오 압축에 사용될 때, 손실 부호화는 소스 양자화와 동등해진다).

그러나 매핑 는 비특이적이다. 그 확장은 비손실 부호화를 생성하며, 이는 일반적인 데이터 전송에 유용할 것이다(그러나 이 기능이 항상 필요한 것은 아니다). 비특이 코드가 소스보다 더 작을 필요는 없다(그리고 많은 응용 프로그램에서 더 큰 코드가 유용하다. 예를 들어, 부호화 또는 전송 오류를 감지하거나 복구하는 방법으로, 또는 보안 응용 프로그램에서 소스를 감지 불가능한 변조로부터 보호하는 데).

 고유하게 해독 가능한 코드 
코드의 확장이 § 비특이적인 경우 코드는 고유하게 해독 가능하다. 주어진 코드가 고유하게 해독 가능한지 여부는 사르디나스-패터슨 알고리즘으로 결정할 수 있다.

매핑 는 고유하게 해독 가능하다(이는 맵에서 각 대상 비트 문자열 뒤의 follow-set을 보면 증명될 수 있다. 각 비트 문자열은 맵에서 기존 코드를 따라 더 긴 유효한 코드를 생성할 수 없는  비트를 보자마자 종료되지만, 새로운 코드를 명확하게 시작하기 때문이다).

이전 섹션의 코드 를 다시 고려해보자.이 코드는 Berstel et al. (2009), 예제 2.3.1, p. 63에서 찾은 예제를 기반으로 한다. 이 코드는 고유하게 해독 가능하지 않다. 왜냐하면 문자열 은 코드워드 시퀀스 으로 해석될 수 있지만, 코드워드 시퀀스 으로도 해석될 수 있기 때문이다. 이 인코딩된 문자열의 두 가지 가능한 해독은 와 이다. 그러나 이러한 코드는 가능한 모든 소스 심볼 집합이 완전히 알려져 있고 유한하거나, 이 확장의 소스 요소가 허용되는지 여부를 결정하는 제한(예: 형식 구문)이 있을 때 유용하다. 이러한 제한은 동일한 심볼에 매핑된 가능한 소스 심볼 중 어떤 것이 해당 제한하에서 유효한지 확인하여 원본 메시지를 해독할 수 있도록 한다.

 앞자리 부호 

코드는 매핑에서 어떤 대상 비트 문자열도 동일한 매핑 내의 다른 소스 심볼의 대상 비트 문자열의 접두사가 아닌 경우 앞자리 부호이다. 이는 심볼이 전체 코드워드를 수신한 후 즉시 해독될 수 있음을 의미한다. 이 개념에 대한 다른 일반적으로 사용되는 이름으로는 접두사-자유 코드, 즉시 코드 또는 문맥-자유 코드가 있다. 앞자리 부호의 특별한 경우는 블록 부호, LEB128, 가변 길이 수량(VLQ) 코드이다.

예를 들어, 위 매핑 은 접두사 코드가 아니다. 비트 문자열 을 읽은 후 그것이  소스 심볼을 인코딩하는지, 아니면  또는  심볼의 인코딩의 접두사인지 알 수 없기 때문이다. 앞자리 부호의 예시는 아래와 같다.
 심볼  코드워드            
 인코딩 및 디코딩 예시:
  →  →  → 

이 예시에서 의 확률이 라면, 위 코드를 사용하여 소스 심볼을 나타내는 데 사용되는 비트의 기대값은 다음과 같다:
 .
이 소스의 엔트로피가 심볼당 1.75비트이므로, 이 코드는 소스를 오류 없이 복구할 수 있도록 최대한 압축한다.

 같이 보기 
 골롬 부호화
 크루스칼 카운트

  와이드 문자
 로터스 멀티바이트 문자 집합 (LMBCS)
 트리플 바이트 문자 집합 (TBCS)
 더블 바이트 문자 집합 (DBCS)
 단일 바이트 문자 집합 (SBCS)

 내용주 

 각주 

 더 읽어보기 
  (xii+191 pages) Errata 1Errata 2
  Draft available online

분류:데이터 압축
분류:부호 이론