-1

有人可以命名一个用于压缩数字的现有算法吗？数字是整数，完全随机，没有空格和小数，例如。35637462736423478235687479567456....n

好吧，到目前为止，我所拥有的就是这个，它将整数转换为 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++

更新：这是另一个压缩结果比上面代码更好的 PHP 代码，如果位置 1st、6th、12、th 等的整数的值小于 256 并且后面的 3 个整数，它可以压缩高达 66%它们的值不超过前 3 个整数的 256，例如134298156286159.... 可以压缩到 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;   
}

顺便说一句，10 位编码或 40 位编码可以使用 base_convert() 或http://php.net/manual/en/ref.bc.php页面中的第 4 条评论轻松完成，该页面始终显示大约 58.6% 的压缩率。

4

1 回答 1

4

如果数字是随机的，那么您不能将序列压缩超过信息理论限制，即 log 2 10 bits/digit。（实际上，除非字符串的精确长度是固定的，否则它会稍微多一点。）您可以通过将数字表示为（非常长的）二进制数来实现该限制；但是，压缩和解压缩既麻烦又耗时。

由于 1000 仅略小于 2 10，因此您可以使用 10 位表示 3 位数字，从而得出非常接近最优的解决方案。与理论上最佳的 3.32 位/位相比，这是 3.33 位/位。（换句话说，它大约是 99.7% 的最佳值。）

由于实际上有 1024 个可能的 10 位代码，而您只需要其中的 1000 个来表示 3 个数字，因此您还有一些剩余；如有必要，其中之一可用于指示流的结束。

输出 10 位数字有点烦人。输出 40 位数字更容易，因为 40 位正好是 5 个字节。幸运的是，如今大多数语言都支持 40 位算术（实际上是 64 位算术）。

（注意：这与您的解决方案并没有什么不同。但它更容易一点，也更压缩一点。）

于 2013-08-07T03:51:08.370 回答