정수 문자열 압축 알고리즘

Question

누군가가 숫자 압축에 사용되는 기존 알고리즘을 명명 할 수 있습니까? 숫자는 공백과 소수 자리가없는 정수이고 완전히 무작위입니다 (예 : 35637462736423478235687479567456 .... N

아니라, 지금까지 내가 가진 모든이를, 그것은

function intergerToChar($v) 
{ 
    $buffer=""; 
    $charsLen=strlen($v); 
    for($i = 0; $i <= $charsLen; $i++) 
    {  
     $asc=$v[$i]; 
     if($asc==0){$buffer[]=0;} 
     elseif($asc==1){$buffer[]=$v[$i].$v[$i+1].$v[$i+2];$i=$i+2;} 
     elseif($asc==2) 
     { 
      if($v[$i+1]<5){$buffer[]=$v[$i].$v[$i+1].$v[$i+2];$i=$i+2;} 
      elseif($v[$i+1]==5 && $v[$i+2]<6){$buffer[]=$v[$i].$v[$i+1].$v[$i+2];$i=$i+2;} 
      else{$buffer[]=$v[$i].$v[$i+1];$i++;}  
     } 
     else{$buffer[]=$v[$i].$v[$i+1];$i++;} 
    } 
    return $buffer; 
} 

BTW 원래 크기의 약 40 %를 감소 ASCII로 정수 변환, 내가 PHP 의미하지 알고 압축 도구를 만들기위한 도구. I는 C가/C가 ++

UPDATE 이용 될 것이다 : 이것은 위의 코드보다 더 압축 결과 다른 PHP 코드, 그것은 66 % 개까지 압축 할 수없는 경우, 위치 1의 정수, 6, 12, th 등은 256보다 작은 값을 가지며 그 뒤에 오는 3 개의 정수는 앞의 3 개의 정수보다 256 이하의 값을 갖습니다. 예 : 59 ... 66까지 압축 할 수 있습니다 최적이 아닌 것으로 알고 있습니다. 제발 제안이나 수정을 부탁드립니다.

function intergerToChar2($v) 
{ 
    $buffer=""; 
    $charsLen=strlen($v); 
    for($i = 0; $i <= $charsLen; $i++) 
    {  
     if($v[$i].$v[$i+1].$v[$i+2]<256){$base=$v[$i].$v[$i+1].$v[$i+2];$i=$i+2;} 
     else{$base=$v[$i].$v[$i+1];$i=$i+1;}$i=$i+1; 

     if($v[$i].$v[$i+1].$v[$i+2]<256){$next=$v[$i].$v[$i+1].$v[$i+2];$i=$i+2;} 
     else{$next=$v[$i].$v[$i+1];$i=$i+1;} 

     if($next!=="") 
     { 
      $next=$next-$base; 
      if($next<0)$next=255+$next; 
     } 

     $buffer[]=$base; 
     $buffer[]=$next; 
    } 
    return $buffer; 
} 

btw, 10 비트 인코딩 또는 40 비트 인코딩은 base_convert() 또는 http://php.net/manual/en/ref.bc.php 페이지의 네 번째 주석을 사용하여 쉽게 수행 할 수 있습니다.이 페이지는 항상 약 58.6 %의 압축률을 나타냅니다.

Answer 1

숫자가 무작위 인 경우 정보 이론적 인 한계 인 10 비트/자릿수 이상으로 시퀀스를 압축 할 수 없습니다. 실제로 문자열의 정확한 길이가 고정되어 있지 않으면 그보다 약간 더 큽니다. 숫자를 (매우 긴) 2 진수로 표시하여 한계를 달성 할 수 있습니다. 그러나 압축하고 압축을 풀 때 시간이 많이 소요됩니다.

거의 최적의 솔루션은 1000이 2 보다 약간 작기 때문에 10 비트를 사용하여 3 자리를 나타낼 수 있습니다. 이론적으로 최적 인 3.32 비트/자릿수와 비교하면 3.33 비트/자릿수입니다. (즉, 약 99.7 % 최적입니다.)

실제로 1024 개의 가능한 10 비트 코드가 있기 때문에 3 자리 숫자를 나타내는 데 1000 개의 숫자가 필요하기 때문에 약간 남았습니다. 필요할 경우 스트림 중 하나를 사용하여 스트림의 끝을 표시 할 수 있습니다.

10 비트 숫자를 출력하는 데 약간 짜증이납니다. 40 비트는 정확히 5 바이트이므로 40 비트 숫자를 출력하는 것이 더 쉽습니다. 다행히 요즘 대부분의 언어는 40 비트 산술 (실제로는 64 비트 산술)을 지원합니다.

(참고 :이 솔루션에서 해당 다르지 않다하지만 좀 더 쉽게 그리고 좀 더 압축..)