séquence de codage / de compression d'entiers répétitifs
-
24-09-2019 - |
Question
J'ai de très longues séquences entières qui ressemblent à ceci (longueur arbitraire!):
0000000001110002220033333
Maintenant, je dois un algorithme pour convertir cette chaîne en quelque chose comme comprimé
a9b3a3c3a2d5
Ce qui signifie "une 9 fois, puis b 3 fois, puis une 3 fois" et ainsi de suite, où "a" est égal à 0, "b" pour 1, "c" pour 2 et "d" pour trois.
Comment voulez-vous faire? Jusqu'à présent, rien de convenable est venu à mon esprit, et je pas eu de chance avec Google parce que je ne savais pas vraiment quoi chercher. Qu'est-ce que ce type de codage / compression appelé?
PS: Je vais faire l'encodage avec PHP , et le décodage JavaScript
.Modifier : Merci à tous!
J'ai fini avec cette fonction pour l'encodage:
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;
}
Et pour le décodage:
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');
};
La solution
Il est appelé Run Length Encoding
encodeur de base 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;
}
vous ça va mal avec la préforme émet une chaîne comme
123456789123456789
Si vous allez manipuler une chaîne qui peut avoir beaucoup de caractères simples individuels que vous seriez mieux d'ajouter une certaine complexité et ne pas écrire la longueur de la course si la longueur de la course est 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;
}
Autres conseils
Voici une implémentation naïve de ce que vous voulez.
$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;
Voici une version plus courte:
function smush(str) {
return str.replace(/((.)\2*)/g, function(_, w, x) {
return x + w.length;
});
}
modifier oh je vois que vous voulez encoder avec php; désolé, je ne sais pas. Voici un décodeur dans un esprit similaire:
function unsmush(str) {
return str.replace(/(.)(\d+)/g, function(_, x, n) {
return new Array(parseInt(n, 10) + 1).join(x);
});
}
Juste Pour votre information, vous pourriez probablement gzip vos données et la navigation décompresse automatiquement. Pour la plupart des implémentations cela va fonctionner mieux que RLE. Mais moins amusant évidemment.
$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;
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;
}