Целочисленный алгоритм сжатия строк

Question

может кто-нибудь назвать существующий алгоритм, который используется для сжатия чисел? числа - целые и вполне случайные, без пробелов и десятичных знаков, например. 35637462736423478235687479567456 .... п

хорошо, до сих пор, все у меня есть это, он преобразует целых чисел на ASCII восстанавливающих прибл 40% от первоначального размера

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; 
} 

Кстати, я знаю, PHP не означает, для создания инструмента сжатия. Я буду использовать C/C++

UPDATE: Это еще один PHP код с более сжимающей результат, чем приведенный выше код, он может сжать Шифрование до 66%, если целые числа на позиции 1, 6, 12, th и т. д. имеет значения менее 256, а последующие целые числа имеют значения не более 256, чем предыдущие 3 целые числа, например, 59 .... можно сжать до 66 % i knw не является оптимальным, пожалуйста, не стесняйтесь делать предложения/исправления

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() или 4-го комментария от страницы http://php.net/manual/en/ref.bc.php, которая всегда показывает сжатие около 58,6%.

Answer 1

Если цифры являются случайными, вы не можете сжимать последовательность больше, чем теоретико-информационный предел, который является журналом 10 бит/цифра. (На самом деле, это немного больше, чем если фиксированная длина строки не исправлена.) Вы можете достичь этого предела, представляя цифры как (очень длинное) двоичное число; однако это неудобно и требует времени для сжатия и декомпрессии.

Очень близкое оптимальное решение получается из-за того, что 1000 только немного меньше 2 , поэтому вы можете представить 3 цифры с использованием 10 бит. Это 3,33 бит/цифры, по сравнению с теоретически оптимальными 3,32 бит/цифрой. (Другими словами, это примерно на 99,7% оптимально.)

Так как на самом деле 1024 возможных 10-битных кодов, и вам нужно только 1000 из них, чтобы представить 3 цифры, у вас есть несколько оставшихся; один из них может быть использован для указания конца потока, если это необходимо.

Это немного раздражает вывод 10-битных чисел. Легче выводить 40-битные числа, так как 40 бит - это точно пять байтов. К счастью, большинство языков в наши дни поддерживают 40-битную арифметику (фактически 64-битную арифметику).

(Примечание: Это не то, что отличается от вашего решения, но это немного легче и немного более сжатым.).