Codificare / comprimere sequenza di numeri interi ripetitive

Question

Non ho molto tempo intero sequenze che assomigliano a questo (lunghezza arbitraria!):

0000000001110002220033333

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

a9b3a3c3a2d5

che significa "9 volte, allora B 3 volte, poi un 3 volte" e così via, dove "A" sta per 0, "B" per 1, "c" per 2 e "d" per 3.

Come l'hai fatto? Fin qui niente di adatto è venuto in mente, e non ho avuto fortuna con Google, perché non ho davvero sapere cosa cercare. Che cosa è questo tipo di codifica / compressione chiamato?

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 questo 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 del percorso è di 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;
  });
}

modifica Oh, vedo che si desidera codificare con php; mi dispiace 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 decomprimere esso. Per la maggior parte delle implementazioni questo sta andando a lavorare 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;

}