최적의 매개 변수를 시작 단계 스톱 코딩 체계로 어떻게 계산할 수 있습니까?

Question

시작 단계 스톱 코드는 비교적 작은 숫자를 압축하는 데 사용되는 데이터 압축 기술입니다.

코드는 다음과 같이 작동합니다. 세 가지 매개 변수, 시작, 단계 및 중지가 있습니다. 시작 처음 몇 숫자를 계산하는 데 사용되는 비트의 양을 결정합니다. 단계는 숫자를 인코딩하는 데 사용되는 최대 비트의 비트를 결정할 때 인코딩에 추가 할 비트 수를 결정합니다.

따라서 인코딩의 길이는 l = start + step * i로 주어집니다.

특정 코드의 "I"값은 unery를 사용하여 인코딩됩니다. 즉, 다수의 1 비트에 이어 0 비트가 끝납니다. 우리가 정지에 도달하면 종료 0 비트를 떨어 뜨릴 수 있습니다. 내가 0이라면 0 비트 만 씁니다.

따라서 (1, 2, 5) start-step-stop 코드는 다음과 같이 작동합니다.

값 0, 다음과 같이 인코딩되었습니다. 0 0
값 1, 다음과 같이 인코딩되었습니다. 0 1
값 2, 로코딩 : 1000
값 9, 로코딩 : 10 111
값 10, 로코딩 : 11 00000
값 41, 로코딩 : 11 11111

그렇다면 여러 숫자가 포함 된 파일이 주어지면 해당 파일의 최적의 시작 단계 스톱 코드를 어떻게 계산할 수 있습니까? 최적의 매개 변수는 압축 비율이 가장 큰 매개 변수로 정의됩니다.

Answer 1

이 "시작 단계 스톱"코드는 다른 호출 방식처럼 보입니다. 허프만 코드. 참조 기본 기술 의사 코드를 계산하기위한 의사 코드의 개요.

본질적으로 이것은 알고리즘이하는 일입니다.

허프만 인코딩을 시작하기 전에 압축 할 각 기호의 통계를 수집해야합니다 (파일의 총 주파수 압축).

당신이 그 후에 당신은 a를 만듭니다 이진 트리 가장 자주 사용되는 기호가 트리의 맨 위에 있고 (따라서 적은 비트를 사용), 인코딩이 없음 접두사 코드. 인코딩에 공통 접두사가있는 경우 모호성 감압이있을 수 있습니다.

허프만의 끝에서 시작 값을 인코딩하면 가장 얕은 잎 노드의 깊이가 될 것입니다. 단계는 항상 1이됩니다 (논리적으로 이것은 의미가 있습니다. 왜 필요한 것보다 더 많은 비트를 강요하고, 한 번에 하나씩 추가). 정지 값은 가장 깊은 잎 노드의 깊이입니다.

주파수 통계가 정렬되지 않으면 o (nlog n)를 수행하는 데 사용됩니다. 주파수별로 정렬되면 O (n)에서 수행 할 수 있습니다.

Huffman 코드는 이러한 유형의 인코딩에 대해 최고의 평균 압축을 보장합니다.

Huffman 은이 유형의 가장 효율적인 압축 방법을 설계 할 수있었습니다. 실제 기호 주파수가 코드를 작성하는 데 사용 된 것과 동의 할 때 개별 소스 기호를 고유 한 비트에 대한 다른 매핑은 더 작은 평균 출력 크기를 생성하지 않습니다.

이를 통해 문제에 대한 이상적인 솔루션을 구현하는 데 도움이됩니다.

편집하다: 비슷하지만 이것은 OP가 찾고 있던 것이 아닙니다.

이것 학문 이 코드의 제작자에 의해 시작 단계-스톱 코드, 시작-스톱 코드의 일반화를 설명합니다. 그러나 저자는 섹션 2의 끝 근처에서 최적의 시작 단계 스톱을 얻는 방법을 간략하게 설명합니다. 통계 랜덤 변수를 사용하거나 최상의 조합을 사용하는 무차별적인 자금 지원이 포함됩니다. 파일에 대한 사전 지식이 없으면 알고리즘은 O ((log n)^3)입니다.

도움이 되었기를 바랍니다.

Answer 2

내가 사용한 접근법은 간단한 무차별 힘 솔루션이었습니다. 알고리즘은 다음과 같은 기본 단계를 따랐습니다.

1. 파일의 각 숫자의 빈도를 계산하십시오. 동일한 패스에서 파일의 총 숫자 양을 계산하고 MaxNumber로 가장 큰 숫자를 결정하십시오.

2. 주파수를 파일의 총 숫자 양으로 나눈 값으로 각 숫자의 확률을 계산하십시오.

3. "OptimalStop"을 Log2 (MaxNumber)와 동일하게 결정하십시오. 이것은 Shannon Information 이론에서와 같이 MaxNumber를 나타내는 데 사용되어야하는 이상적인 비트 수이며, 따라서 특정 숫자의 인코딩에 사용되는 최적의 최대 량의 비트에 대한 합리적인 추정치입니다.

4. 1에서 "OptimalStop"까지의 모든 "시작"값에 대해 5-7 단계를 반복하십시오.

5. 1에서 ( "OptimalStop" - "start") / 2의 모든 "step"값에 대해 6 번과 7 단계를 반복하십시오.

6. 정지 = 시작 + step * i를 만족시키는 "OptimalStop"에 가장 가까운 "정지"값을 계산하십시오.

7. 이 인코딩에서 사용될 평균 비트 수를 계산하십시오. 주어진 인코딩에서 각 숫자의 확률에 비트 길이를 곱하면 계산할 수 있습니다.

8. 가장 낮은 평균 비트 수로 인코딩을 선택하십시오.