编码/压缩连续重复整数序列

Question

我有非常长的整数序列，看起来像这样（长度任意！）：

0000000001110002220033333

现在我需要一些算法将这个字符串转换成类似于压缩的东西。

a9b3a3c3a2d5

这段文本的含义是：“重复9次a，然后重复3次b，接着重复3次a”，以此类推。其中，“a”代表0，“b”代表1，“c”代表2，“d”代表3。

您要如何实现这个过程呢？目前我没有想到合适的方法，而且我在谷歌上也没有找到相关信息，因为我不知道该搜索什么。这种编码/压缩方式叫什么？

附注：我将使用PHP进行编码，使用JavaScript进行解码。

编辑：非常感谢大家！

以下是我的编码函数：

protected function numStringToRle($s){          
        $rle    = '';
        $count = 1;
        $len    = strlen($s);
        for($i = 0; $i < $len; $i++){
            if($i != $len && isset($s[$i+1]) && $s[$i] == $s[$i+1]){
                $count++;                
            } else {
                $rle .= chr($s[$i] + 97).( $count == 1 ? '' : $count);                                
                $count = 1;
            }
        }
        return $rle;            
}

并且对于解码：

var decodeCoords = function(str) {

   str = str.replace(/(.)(\d+)/g, function(_, x, n) {
       return new Array(parseInt(n, 10) + 1).join(x);
   });

   return str.
     replace(/a/g, '0').
     replace(/b/g, '1').
     replace(/c/g, '2').
     replace(/d/g, '3');     
};

- Alex

---

你具体是用这个做什么的？你确定不能使用Gzip进行压缩吗？这样在时间和空间上都更加高效，而且已经有现成的实现了。 - ryeguy

gzip不是一个选项，因为我需要用JavaScript解码它。我将其用作2D游戏的一种位掩码。 - Alex

Answer 1

这被称为 行程长度编码

PHP的基本编码器：

function numStringToRle($s){
    $rle = '';
    $count = 1;
    $len = strlen($s);
    for ( $i = 0; $i < $len; $i++ ){
        if ( $i != $len && $s[$i] == $s[$i+1] ){
            $count++;                
        }else{
          $rle .= chr($s[$i] + 97).$count;    
          $count = 1;
        }
    }
    return $rle;
}

请注意，如果使用类似以下字符串的话，性能可能会受到影响：

 123456789123456789

如果您将要处理的字符串可能包含许多单个字符，那么最好增加一些复杂性，并且当运行长度为1时不写入运行长度。

//change
$rle .= chr($s[$i] + 97).$count;    

//to
$rle .= chr($s[$i] + 97).( $count == 1 ? '' : $count );   

//or
$rle .= chr($s[$i] + 97)
if ( $count != 1 ){
    $rle .= $count;
}

- Yacoby

---

我正在寻找这个算法的名称。谢谢！ - Jack

请您详细说明一下+97是什么意思，它的作用是什么，为什么需要它？ - bugmenot123

Answer 2

这是一个简单的实现，你想要的功能可以通过以下方式实现。

$toEncode = '0000000001110002220033333';
$currentChar = '-1';
$length = strlen($toEncode);
$encoded = '';
$currentNbrChar = 0;
for($i = 0; $i < $length; $i++){
  if($toEncode[$i] != $currentChar){
    if($currentChar != '-1'){
      $encoded .= chr(97 + $currentChar).$currentNbrChar;
    }
    $currentNbrChar = 0;
    $currentChar = $toEncode[$i];
  }
  $currentNbrChar ++;
}
if($currentChar != '-1'){
  $encoded .= chr(97 + $currentChar).$currentNbrChar;
}
echo $encoded;

- Arkh

Answer 3

这是一个更简短的版本：

function smush(str) {
  return str.replace(/((.)\2*)/g, function(_, w, x) {
    return x + w.length;
  });
}

编辑 哦，我看到您想要使用PHP编码; 对不起我不知道。这里有一个类似精神的解码器：

function unsmush(str) {
  return str.replace(/(.)(\d+)/g, function(_, x, n) {
    return new Array(parseInt(n, 10) + 1).join(x);
  });
}

- Pointy

Answer 4

$str="0000000001110002220033333";

//$c will count the number of occurances.

$c=1;

$lastInt=substr($str,0,1);

$str=substr($str,1);

$resultStr='';

$loopEnd=strlen($str);


for($i=1; $i<=$loopEnd+1;$i++)

{

    $nowInt=substr($str,0,1);   
    if($lastInt==$nowInt)
    {
        $c++;
        $str=substr($str,1);
    }
    else
    {
        $char=chr((int)$lastInt + 97);
        $resultStr=$resultStr.$char.$c;
        $str=substr($str,1);
        $c=1;
        $lastInt=$nowInt;
    }
}

// we use if condition since for loop will not take the last integer if it repeats.

if($c>1)
{

$char=chr((int)$lastInt + 97);

$resultStr=$resultStr.$char.$c;

}

echo $resultStr;

- nik

Answer 5

顺便提一下，您可以对数据进行gzip压缩，浏览器会自动解压缩。对于大多数实现而言，这比RLE更好用。但显然不太有趣。

- James Westgate

Answer 6

function compress( $str) {
$strArr = str_split($str.'0');
$count = 0;
$resStr = '';
$strCheck = $strArr[0];
foreach($strArr as $key => $value)
{
    if($strCheck == $value)
    {
       $count++;
    } 
    else
    {
        if($count == 1)
        {
            $strCheck = $value;
            $resStr .= $strArr[$key-1];
            $count=1;
        }
        elseif($count == 2)
        {
            $strCheck = $value;
            $resStr .= $strArr[$key-1].$strArr[$key-1];
            $count=1;
        }
        else
        {
            $strCheck = $value;
            $resStr .= $strArr[$key-1].$count;
            $count=1;
        }
    } 

} 
return $resStr;

}

- Harish Lalwani