У меня очень длинные целые последовательности, которые выглядят так (произвольная длина!):
0000000001110002220033333 Теперь мне нужен алгоритм для преобразования этой строки в нечто сжатое
a9b3a3c3a2d5
Это означает «9 раз, затем b 3 раза, затем 3 раза» и т. Д., Где «a» обозначает 0, «b» для 1, «c» для 2 и «d» для 3.
Как бы Вы это сделали? До сих пор мне ничего не приходило в голову, и мне не повезло с Google, потому что я действительно не знал, что искать. Что называется кодировкой / сжатием?
PS: Я собираюсь сделать кодировку с PHP и расшифровать в JavaScript .
Редактировать : Спасибо всем!
Я получил эту функцию для кодирования:
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; }
И это для декодирования:
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'); };
Он называется кодировкой Run Length
Базовый кодер в 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; }
Будьте предупреждены, что это приведет к серьезным проблемам со строкой, подобной
123456789123456789
Если вы собираетесь обрабатывать строку, которая может содержать много отдельных отдельных символов, вам лучше добавить некоторую сложность и не писать длину прогона, если длина пробега равна 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; }
Вот наивная реализация того, что вы хотите.
$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;
Вот более короткая версия:
function smush(str) { return str.replace(/((.)\2*)/g, function(_, w, x) { return x + w.length; }); }
edit oh Я вижу, что вы хотите кодировать с помощью php; извините, я этого не знаю. Вот декодер в подобном духе:
function unsmush(str) { return str.replace(/(.)(\d+)/g, function(_, x, n) { return new Array(parseInt(n, 10) + 1).join(x); }); }
Просто FYI, вы могли бы gzip ваши данные, и просмотр автоматически распакует его. Для большинства реализаций это будет работать лучше, чем RLE. Но менее забавно.
$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;
}