编码/压缩重复整数序列 [英] Encode/compress sequence of repeating integers

问题描述

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

  0000000001110002220033333 
  

现在我需要一些算法将这个字符串转换成压缩的像

  a9b3a3c3a2d5 
  

这意味着a 9次，然后b 3次，然后3次等等，其中a表示0，b表示1，c表示2，d表示3.

<你会怎么做的？
到目前为止没有什么合适的想法，我没有运气与谷歌，因为我真的不知道要搜索什么。这种编码/压缩叫什么？

PS：我将使用 PHP 执行编码，并在 JavaScript 中解码。

编辑：谢谢大家！

我最后使用此函数进行编码：

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

解决方案

它被称为运行长度编码

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 = 1; 
} 
} 
 return $ rle; 
} 
  

警告它会对类似

  123456789123456789 
  

你将要处理一个可能有很多单个单个字符的字符串，最好添加一些复杂性，如果运行的长度为1，不写入运行的长度。

  // change 
 $ rle。= chr（$ s [$ i] + 97）。 
 
 //到
 $ rle。= chr（$ s [$ i] + 97）（$ count == 1？''：$ count）; 
 
 //或
 $ rle。= chr（$ s [$ i] + 97）
 if（$ count！= 1）{
 $ rle。 = $ count; 
} 
  

I have very long integer sequences that look like this (arbitrary length!):

0000000001110002220033333

Now I need some algorithm to convert this string into something compressed like

a9b3a3c3a2d5

Which means "a 9 times, then b 3 times, then a 3 times" and so on, where "a" stands for 0, "b" for 1, "c" for 2 and "d" for 3.

How would you do that? So far nothing suitable came to my mind, and I had no luck with google because I didn't really know what to search for. What is this kind of encoding / compression called?

PS: I am going to do the encoding with PHP, and the decoding in JavaScript.

Edit: Thank you all!

I ended up with this function for encoding:

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

And that for decoding:

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

解决方案

It is called Run Length Encoding

Basic encoder in 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;
}

Be warned it will preform badly issues with a string like

 123456789123456789

If you were going to be handling a string that may have a lot of individual single characters you would be better to add some complexity and not write the length of the run if the length of the run is 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;
}

这篇关于编码/压缩重复整数序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！