// 레벤슈타인 코딩 - 점근적으로 최적인 재귀 보편 코드
0이 될 때까지 길이의 길이를 재귀적으로 인코딩합니다.
큰 정수에 대해 이론적 최소 길이에 근접합니다.
추가 매개변수 없이 모든 음이 아닌 정수에 사용할 수 있습니다.
레벤슈타인 코딩(Levenstein 또는 L* 코드라고도 함)은 수의 비트 길이를 재귀적으로 인코딩합니다. 이진 길이가 N인 정수 n에 대해, 먼저 C(N-1)을 재귀적으로 인코딩하고, '1'을 추가한 다음, 선행 1 비트를 제외한 n의 나머지 비트를 추가합니다. 재귀는 0에서 종료됩니다. 이로써 점근적으로 최적인 코드가 생성됩니다.
0 → 0 1 → 10 (C(0) + 1 + '') 2 → 110 (C(1) + 1 + '0') 3 → 111 (C(1) + 1 + '1') 4 → 11000 (C(2) + 1 + '00') 5 → 11001 (C(2) + 1 + '01') 재귀 구조: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
레벤슈타인 코딩(레벤슈타인 거리와는 다름)은 정수의 길이를 재귀적으로 인코딩하는 보편 코드입니다. Vladimir Levenshtein이 제안했으며, 큰 정수에 대해 점근적으로 최적입니다.
이 코드는 비트 길이에서 1을 뺀 값을 재귀적으로 인코딩합니다. N비트 정수 n을 인코딩할 때, 먼저 (N-1)을 인코딩하고 '1'을 추가한 뒤, n의 마지막 (N-1)비트를 추가합니다. 재귀는 0에서 멈추며, 0은 '0'으로 인코딩됩니다.
레벤슈타인 코딩은 Elias Omega와 마찬가지로 점근적으로 최적이지만, 다른 재귀 구조를 사용합니다. Elias Gamma/Delta보다 복잡하지만, 매우 큰 정수에 대해 더 나은 압축률을 제공합니다.
레벤슈타인 코딩은 주로 정보 이론과 콜모고로프 복잡도에서 이론적인 관심사입니다. 실제 시스템에서는 거의 사용되지 않지만, 최적 보편 코딩의 원리를 잘 보여 줍니다.