Кодировка длины выполнения (целые числа)

В классе мы говорили о RLE, и наш профессор показал нам следующий код. Я пытался это понять, но не совсем понял. Поэтому я был бы очень благодарен, если бы кто-нибудь мог объяснить мне, как работает RLE в этом примере.
Я понимаю, как добиться сжатия данных, но я не понимаю реализацию программы. В комментариях вы найдете мои вопросы.

// Example implementation of a simple variant of // run-length encoding and  decoding of a byte sequence

#include <iostream>
#include <cassert>

// PRE: 0 <= value <= 255
// POST: returns true if value is first byte of a tuple, otherwise false

bool is_tuple_start(const unsigned int value)
{
assert(0 <= value && value <= 255);
return value >= 128; //Why is it: value>=128 for first Byte of tuple?
}

// PRE: 1 <= runlength <= 127 //Why must runlength be in this range?
// POST: returns encoded runlength byte

unsigned int make_tuple_start(const unsigned int run_length)
{
assert(1 <= run_length && run_length <= 127);
return run_length + 128; //Why do I add 128?
}

// PRE: n/a
// POST: returns true if value equals the maximal run-length

bool is_max_runlength(const unsigned int value)
{
return value == 127; //same question: why is max. range 127?
}

// PRE: 128 <= value <= 255 //Why this range for value?
// POST: returns runlength of tuple

unsigned int get_runlength(const unsigned int value)
{
assert(128 <= value && value <= 255);
return value - 128; //Why -128?
}

// PRE: n/a
// POST: outputs value and adds a newline

void out_byte(const unsigned int value)
{
std::cout << value << "\n";
}

// PRE: 1 <= runlength <= 127 and 0 <= value <= 255
// POST: outputs run length encoded bytes of tuple

void output(const unsigned int run_length, const unsigned int value)
{
assert(1 <= run_length && run_length <= 127);
assert(0 <= value && value <= 255); //Why is value now between 0 and 255?

if (run_length == 1 && !is_tuple_start(value))
{
out_byte(value);
}
else
{
out_byte(make_tuple_start(run_length));
out_byte(value);
}
}

// PRE: n/a
// POST: returns true if 0 <= value <= 255, otherwise false

bool is_byte(const int value)
{
return 0 <= value && value <= 255;
}

// PRE: n/a
// POST: outputs error if value does not indicate end of sequence

void check_end_of_sequence(const int value)
{
if (value != -1)
{
std::cout << "error\n";
}
}

// PRE: n/a
// POST: reads byte sequence and outputs encoded bytes

void encode()
{
std::cout << "--- encoding: enter byte sequence, terminate with -1\n";
int value;

std::cin >> value;

if (is_byte(value))
{
int prev_value = value; //When/Where does value Change?
unsigned int run_length = 1;

while(true)
{
// read next byte, stop if invalid or end of sequence

std::cin >> value;
if (!is_byte(value))
{ break; }

// output if value has changed or maximal runlength is reached
// otherwise increase length of current run

if (value != prev_value || is_max_runlength(run_length))
{
output(run_length, prev_value);
run_length = 1;
prev_value = value;
}
else { ++run_length; }
}
output(run_length, prev_value);
}

// output "error" if sequence terminated incorrectly

check_end_of_sequence(value);
}

// PRE: n/a
// POST: reads byte sequence and outputs decoded bytes

void decode()
{
std::cout << "--- decoding: enter byte sequence, terminate with -1\n";
int value;

while(true) {

// read next byte, stop if invalid or end of sequence

std::cin >> value; //is value only a Byte? Or the whole sequence?

if (!is_byte(value))
{ break; }

// if this is a tuple output read next byte, otherwise output directly

if (is_tuple_start(value))
{
unsigned int run_length = get_runlength(value);

// next must be a valid byte, otherwise this is an error
std::cin >> value;

if (!is_byte(value))
{
value = 0;
// trigger error in case value = -1
break;
}

// output uncompressed tuple

for(int i = 0; i < run_length; ++i)
{
out_byte(value);
}
}

else { out_byte(value); }
}

// output "error" if sequence terminated incorrectly

check_end_of_sequence(value);
}int main(const int argc, const char* argv[])
{
std::cout << "--- select mode: 0 = encode / 1 = decode\n";

unsigned int mode;
std::cin >> mode;

if (mode == 0)
{
encode();
}
else if (mode == 1)
{
decode();
}
else
{
std::cout << "--- unknown mode, must be 0 (encode) or 1 (decode)\n";
}
}

Я надеюсь получить ответы на мои вопросы и то, что код читабелен, что было в основном копией + вставкой из моих лекционных заметок.

0

Решение

Способ кодирования работает так: последовательность повторяющихся значений хранится в виде:

<length> <value>

в то время как неповторяющееся значение сохраняется просто как:

<value>

Но когда вы видите число в закодированной последовательности, как вы узнаете, является ли оно частью длины первого формата или единственным неповторяющимся значением? Это делается с помощью правила, которое мы добавляем к длине 128, прежде чем кодировать его. Таким образом, любое число> 128 является <length> байт, который запускает первый формат.

Но что, если стоимость неповторяющегося предмета была выше 128? Решением для этого является использование первого формата для больших значений, рассматривая его как повторяющееся значение с runlength = 1,

Это должно ответить на большинство ваших вопросов, которые касаются всех дополнений и вычитаний диапазона.

Почему длина пробега должна быть в этом диапазоне?

Мы храним все в байтах от 0 до 255. Если длина была> 127, то, когда мы добавим к ней 128, мы получим число> 255, которое не помещается в байт.

значение только Байт? Или вся последовательность?

Декларация int value;так что это просто одно число. Каждый раз cin >> value; он получает следующий байт в последовательности.

Почему значение сейчас между 0 и 255?

Значение всегда может быть целым байтом, только длина ограничена 127, потому что мы добавляем к ним 128. См. Объяснение выше, что высокие значения всегда кодируются как кортеж с длиной в первую очередь.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]