이 질문은 범위를 저장하는 데 필요한 비트 수에 관한 것입니다. 또는 주어진 비트 수에 대해 저장할 수있는 최대 범위는 어떻게됩니까?
0-255 범위 내에서 하위 범위를 저장한다고 가정합니다.
예를 들어 45-74입니다.
위의 예제를 부호없는 2 바이트로 저장할 수 있지만 정보가 중복되어 있어야합니다. 우리는 두 번째 값이 첫 번째 값보다 크므로 첫 번째 값이 큰 경우 두 번째 값에 필요한 비트 수가 적고 두 번째 값이 큰 경우 첫 번째 값에 필요한 비트 수가 적습니다 .
압축 기술이 약간의 결과를 낳을 것으로 생각되므로 “1 바이트에 저장할 수있는 최대 범위는 얼마입니까?”라고 묻는 것이 더 좋습니다. 두 숫자를 별도로 저장하여 달성 할 수있는 것보다 커야합니다.
이런 종류의 일을하는 표준 알고리즘이 있습니까?
답변
가능한 범위의 수를 세십시오. 하한 0 (0-0, 0-1, … 0-254, 0-255)의 256 개 범위, 하한 1의 255 범위, … 및 하한 255의 마지막 범위 255 (255- 255). 따라서 총 수는 (256 + 255 + … + 1) = 257 * 128 = 32,896입니다. 이 값이 2 15 = 32,768 보다 약간 높 으므로이 정보를 저장하려면 최소한 16 비트 (2 바이트)가 필요합니다.
일반적으로 0에서 n-1까지의 숫자의 경우 가능한 범위의 수는 n * (n + 1) / 2입니다. n이 22 이하인 경우 256보다 작습니다. n = 22는 22 * 23 / 2 = 253 가능성을 제공합니다. 따라서 1- 바이트 는 0-21의 하위 범위에 충분합니다 .
문제를 보는 또 다른 방법은 다음과 같습니다. 0에서 n-1 사이의 정수 쌍을 저장하는 것은 0- (n-1)의 하위 범위와 첫 번째 숫자를 결정 하는 단일 비트 를 저장하는 것과 거의 같습니다. 두 번째보다 낮거나 높습니다. (두 정수가 같을 때와 차이가 있지만 n이 커질수록이 기회는 점점 작아집니다.) 따라서이 기술을 사용하여 단일 비트에 대해서만 저장할 수 있으며, 거의 사용되지 않는 주된 이유 일 수 있습니다.
답변
작은 비트 수의 경우 Glorfindel이 지적한 것처럼 많은 비트를 저장하는 것은 불가능합니다 . 그러나 사용중인 도메인에 비트가 몇 개 더 있으면 시작 값과 델타로 범위를 인코딩하여 평균 사례를 크게 절약 할 수 있습니다.
도메인이 정수이므로 32 비트라고 가정하겠습니다. 순진한 접근 방식으로 범위를 저장하려면 64 비트 (시작, 끝)가 필요합니다.
(start, delta) 인코딩으로 전환하면 그 범위의 끝을 구성 할 수 있습니다. 최악의 경우 시작은 0이고 델타는 32 비트입니다.
2 ^ 5는 32이므로 델타의 길이를 5 비트 (0 길이 없음, 항상 1 추가)로 인코딩하면 인코딩은 (시작, 길이, 델타)가됩니다. 최악의 경우, 32 * 2 + 5 비트이므로 69 비트입니다. 최악의 경우 모든 범위가 길면 순진 인코딩보다 나쁩니다.
가장 좋은 경우에는 32 + 5 + 1 = 38 비트가 필요합니다.
즉, 많은 범위를 인코딩해야하고 해당 범위가 각각 도메인의 작은 부분에만 적용되는 경우이 인코딩을 사용하면 평균적으로 더 적은 공간 을 사용하게됩니다. 시작에 항상 32 비트가 걸리기 때문에 시작이 어떻게 분배되는지는 중요하지 않지만 범위의 길이가 어떻게 분배되는지는 중요합니다. 길이가 짧을수록 압축률이 높을수록 도메인의 전체 길이를 포괄하는 범위가 많을수록이 인코딩이 더 나빠집니다.
당신이 가지고있는 경우, 많은 유사한 시작점 주위 그룹화 범위를 (예를 들어 당신이 센서의 값을 얻을 수 있기 때문에), 당신은 더 큰 절감 효과를 얻을 수 있습니다. 동일한 값을 시작 값에 적용하고 바이어스를 사용하여 시작 값을 오프셋 할 수 있습니다.
범위가 10000이라고 가정하겠습니다. 범위는 특정 값을 기준으로 그룹화됩니다. 바이어스를 32 비트로 인코딩합니다.
순진한 접근 방식을 사용하면 모든 범위를 저장하려면 32 * 2 * 10 000 = 640 000 비트가 필요합니다.
바이어스 인코딩에는 32 비트가 필요하며 각 범위를 인코딩하는 데 가장 적합한 경우 5 + 1 + 5 + 1 = 12 비트가 사용되며 총 120 000 + 32 = 12032 비트가됩니다. 최악의 경우 총 740 032 비트에 5 + 32 + 5 + 32 비트가 필요하므로 74 비트가 필요합니다.
이는 인코딩에 32 비트가 걸리는 도메인의 10,000 값에 대해
- 최상의 경우 스마트 델타 인코딩을 사용한 12032 비트
- 순진한 시작, 끝 인코딩을 사용하는 640 000 비트 (항상 최상의 경우는 없음)
- 최악의 경우 스마트 델타 인코딩으로 740 032 비트
순진한 인코딩을 기준으로 삼 으면 최대 81.25 % 또는 최대 15.625 % 더 많은 비용을 절약 할 수 있습니다.
귀하의 가치가 어떻게 분배되는지에 따라, 이러한 절감 효과는 상당합니다. 귀하의 비즈니스 도메인을 알고 계십시오! 인코딩하려는 것을 알고 있습니다.
확장으로 바이어스를 변경할 수도 있습니다. 데이터를 분석하고 값 그룹을 식별하는 경우 데이터를 버킷으로 정렬하고 각 버킷을 고유 한 바이어스로 개별적으로 인코딩 할 수 있습니다. 즉,이 방법을 단일 시작 값을 기준으로 그룹화 된 범위뿐만 아니라 여러 값을 기준으로 그룹화 된 범위에도 적용 할 수 있습니다.
시작점이 균등하게 분배되면이 인코딩이 실제로 제대로 작동하지 않습니다.
이 인코딩은 인덱스하기에 매우 나쁘다. 단순히 x 번째 값을 읽을 수 없습니다. 순차적으로 만 읽을 수 있습니다. 네트워크 또는 벌크 스토리지 (예 : 테이프 또는 HDD)를 통한 스트리밍과 같은 일부 상황에 적합합니다.
데이터를 평가, 그룹화 및 올바른 바이어스를 선택하는 것은 상당한 작업 일 수 있으며 최적의 결과를 얻으려면 약간의 조정이 필요할 수 있습니다.
답변
이러한 종류의 문제는 Claude Shannon의 주요 논문 인 “수학적 커뮤니케이션 이론 (The Mathematical Theory of Communication )” 의 주제입니다 .
일반적인 아이디어는 범위를 인코딩하는 데 사용되는 비트 수가 해당 범위가 발생할 확률에 반비례한다는 것입니다. 예를 들어, 45-74 범위가 약 1/4의 시간이라고 가정하십시오. 시퀀스 00은 45-74에 해당한다고 말할 수 있습니다. 범위 45-74를 인코딩하려면“00”을 출력하고 거기서 멈 춥니 다.
99-100과 140-155의 범위가 각각 시간의 약 1/8이라고 가정합시다. 각각 3 비트 시퀀스로 인코딩 할 수 있습니다. 45-74 범위로 이미 예약 된 “00”으로 시작하지 않는 한 3 비트는 작동합니다.
00: 45-74
010: 99-100
101: 140-155
가능한 모든 범위에 인코딩이있을 때까지이 방식으로 계속할 수 있습니다. 가능한 최소 범위는 100 비트 이상이 필요할 수 있습니다. 그러나 거의 나타나지 않기 때문에 괜찮습니다.
최적의 코딩을 찾는 알고리즘 이 있습니다 . 여기서 설명하지는 않겠지 만 위의 링크를 방문하거나“Information Theory”,“Shannon-fano coding”또는“Huffman coding”을 검색하면 자세한 내용을 확인할 수 있습니다.
다른 사람들이 지적했듯이 시작 번호와 시작 번호와 끝 번호의 차이를 저장하는 것이 좋습니다. 확률 분포가 서로 다르기 때문에 시작에 다른 코딩과 차이에 다른 코딩을 사용해야합니다. polygnome이 제안했듯이 최상의 알고리즘은 도메인에 따라 다릅니다.
답변
@Glorfindel의 답변을 확장하려면 :
n → ∞, (n-1) → n으로. 따라서 Ω (범위) → n² / 2 및 log (Ω (범위)) → (2n-1). 순진 인코딩은 2n 비트를 취하기 때문에 점근 최대 압축은 1 비트 만 절약합니다.
답변
비슷한 대답이 있지만 최적의 압축을 얻으려면 다음이 필요합니다.
- 최적의 엔트로피 인코딩 방법 ( 산술 코딩 및 본질적으로 동등한 압축 비율, 약간 더 빠르지 만 파악하기 어려운 ANS )
- 데이터 분포에 관한 가능한 많은 정보. 결정적으로 이것은 하나의 숫자가 얼마나 자주 나타날지 “추측”하는 것이 아니라 특정 가능성을 배제 할 수도 있습니다. 예를 들어, 유효한 간격을 정의하는 방법에 따라 음의 크기 간격과 0 크기의 간격을 배제 할 수 있습니다. 한 번에 인코딩 할 간격이 여러 개인 경우 너비를 줄이거 나 시작 / 종료 값을 늘리는 순서로 정렬하고 많은 값을 배제 할 수 있습니다 (예 : 너비를 줄임으로써 순서를 보장하는 경우 이전 간격 너비가 100이고 다음 값의 시작 값이 47이면 끝 값의 경우 147까지만 고려하면됩니다.
중요한 것은 숫자 2는 가장 유익한 값 (비트 당 인코딩 된 값)이 먼저 나오는 방식으로 인코딩하려는 것을 의미합니다. 예를 들어, 정렬 된 목록을 “있는 그대로”인코딩하는 것이 좋지만 일반적으로 “이진 트리”로 인코딩하는 것이 더 현명합니다. 즉, 너비별로 정렬되고 len요소 가있는 경우 요소 인코딩으로 시작합니다 len/2. 너비가 w라고 가정하십시오. 이제 [0, w] 어딘가에 너비를 갖기 전의 모든 요소와 [w, 허용하는 최대 값] 어딘가에 너비가있는 모든 요소를 알았습니다. len요소를 다룰 때까지 반복적으로 반복합니다 (각 반 목록을 반으로 다시 나누는 등) (고정되지 않는 한 인코딩하려는 경우)len먼저 엔딩 토큰을 신경 쓸 필요가 없습니다). “최대 허용 값”이 실제로 열려 있으면 데이터에 실제로 나타나는 가장 높은 값, 즉 마지막 요소를 먼저 인코딩 한 다음 이진 분할 을 수행하는 것이 좋습니다. 다시, 비트 당 가장 유익한 것이 무엇이든 먼저.
또한 간격의 너비를 먼저 인코딩하고 처리 할 수있는 최대 값을 알고 있다면 오버플로가되는 모든 시작 값을 배제 할 수 있습니다 … 아이디어를 얻습니다. 디코딩 할 때 나머지 데이터에 대해 가능한 많이 추론 할 수있는 방식으로 데이터를 변환하고 정렬하십시오. 최적의 엔트로피 인코딩 알고리즘을 사용하면 “이미 알고있는”비트 인코딩 정보를 낭비하지 않습니다. .