Кодируйте/сжимайте последовательность повторяющихся целых чисел
У меня есть очень длинные целочисленные последовательности, которые похожи на это (произвольная длина!):
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');
};
5 ответов
Он называется Run Length Encoding
Основной кодер в 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;
}
Просто к вашему сведению, вы могли бы сжать свои данные, и браузер автоматически разархивирует их. Для большинства реализаций это будет работать лучше, чем 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;
Вот наивная реализация того, что вы хотите.
$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 о, я вижу, вы хотите кодировать с помощью php; извините, я этого не знаю. Вот декодер в похожем духе:
function unsmush(str) {
return str.replace(/(.)(\d+)/g, function(_, x, n) {
return new Array(parseInt(n, 10) + 1).join(x);
});
}