산술 부호화, 종료 기호 및 빈 문자열

Question

소스 알파벳이 종료 기호로 a를 갖는 a, b, c이고 따라서 단위 간격이 [0, P (a), P a) + P (b), 1].

a (종료 기호)로 끝나는 b와 c의 묶음으로 구성된 문자열은 인코딩에 유효합니다. 중간에 a가있는 문자열은 인코딩에 유효하지 않은 것으로 간주됩니다.

그래서 [P (a), 1) 간격으로 인코딩 된 문자열을 쉽게 만들 수 있습니다. 그러나 산술적 인 코딩은 어떤 문자열에 간격 [0, P (a)]의 인코딩을 할당합니까? 빈 문자열이 [0, P (a)]에있는 비트 스트링으로 인코딩되는 것으로 자격을 부여합니까? 빈 문자열은 문자열 "a"또는 종료 기호로 생각할 수 있습니다.

빈 문자열을 인코딩 할 때 공간을 할당하는 것이 단위 간격의 첫 번째 부분을 [0, (P (b) -P (a))/(1-P (a) P (a), P (a) + P (b), 1]을 매핑하여 단위 구간을 채운다. 이후의 정제 부문은 평소처럼 [0, P (a), P (a) + P (b), 1]을 사용할 것입니다.

Answer 1

예, 빈 문자열은 해당 간격 (예 : 0)입니다. 이것은 문자열이 인코딩 된 표현의 길이에서 길이가 0이라는 것을 추론 할 수 있으므로 중복 될 수 있으므로 제외 할 수 있습니다. 더 일반적으로, 이 기호의 이전 부분을 기반으로 불가능하다고 추측 할 수있는 경우이를 제외하고 (다른 기호에 간격을 더 많이 부여) 작은 공간을 절약 할 수 있습니다. 그러나 당신이 이것을하는 유일한 경우가 첫 번째 기호와 함께라면, 공간 절약은 특별한 특별한 경우의 복잡성을 정당화하기에는 너무 무시할 만합니다.