Encode/comprimere sequenza di interi ripetizione

Question

ho molto lunghe sequenze di interi che assomigliano a questo (lunghezza arbitraria!):

0000000001110002220033333 

Ora ho bisogno di qualche algoritmo per convertire questa stringa in qualcosa compressa come

a9b3a3c3a2d5 

Che significa "a 9 volte, poi b 3 volte, poi a 3 volte" e così via, dove "a" sta per 0, "b" per 1, "c" per 2 e "d" per 3.

Come lo faresti? Finora non mi è venuto in mente nulla di adatto, e non ho avuto fortuna con Google perché non sapevo davvero cosa cercare. Come si chiama questo tipo di codifica/compressione?

PS: Sto andando a fare la codifica con PHP, e la decodifica in JavaScript.

Modifica: Grazie a tutti!

Ho finito con questa funzione per la codifica:

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

E che per la decodifica:

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

Si chiama Run Length Encoding

codificatore di base 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; 
} 

Badate che sarà preforme male problemi con una stringa come

123456789123456789 

Se si stavano per essere gestire una stringa che può avere un sacco di singoli singoli caratteri si sarebbe meglio aggiungere una certa complessità e non scrivere la lunghezza della corsa se la lunghezza della corsa è 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

Ecco un'implementazione ingenuo di quello che volete.

$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

Ecco una versione più breve:

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

modificare Oh, vedo che si desidera codificare con php; scusa, non lo so. Ecco un decoder in uno spirito simile:

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

Answer 4

Cordiali saluti, probabilmente si potrebbe gzip i vostri dati e la ricerca vengono automaticamente decomprimerlo. Per la maggior parte delle implementazioni funzionerà meglio di RLE. Ma meno divertente, ovviamente.

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; 

}