Codificar/comprimir secuencia de enteros que se repiten

Question

que tienen secuencias de números enteros muy largas que se ven así (longitud arbitraria!):

0000000001110002220033333 

Ahora necesito algún algoritmo para convertir esta cadena en algo comprimido como

a9b3a3c3a2d5 

Lo que significa "a 9 veces, luego b 3 veces, luego 3 veces" y así sucesivamente, donde "a" representa 0, "b" para 1, "c" para 2 y "d" para 3.

¿Cómo harías eso? Hasta ahora no se me ocurrió nada adecuado, y no tuve suerte con Google porque realmente no sabía qué buscar. ¿Cómo se llama este tipo de codificación/compresión?

PS: Voy a hacer la codificación con PHP , y la decodificación en JavaScript.

Editar: ¡Gracias a todos!

que terminó con esta función para la codificación:

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

Y que para la decodificación:

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

Answer 1

Se llama Run Length Encoding

codificador básico en 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; 
} 

ten en cuenta que se preformas mal problemas con una cadena como

123456789123456789 

Si se va a estar manejando una cadena que puede tener una gran cantidad de caracteres individuales individuales que sería mejor añadir un poco de complejidad y no escribir la longitud de la ejecución si la duración de la ejecución es 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; 
} 

Answer 2

Aquí hay una implementación ingenua de lo que desea.

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

Answer 3

Aquí hay una versión más corta:

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

edición oh veo que quiere codificar con php; lo siento, no lo sé. He aquí un decodificador en un espíritu similar:

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

Answer 4

Para su información, es probable que podría gzip sus datos y la exploración se descomprime automáticamente. Para la mayoría de las implementaciones, esto funcionará mejor que RLE. Pero menos divertido, obviamente.

Answer 5

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

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; 

}