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

Question

В классе мы говорили о 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"; 
     } 
} 

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

Answer 1

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

<length> <value> 

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

<value> 

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

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

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

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

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

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

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

Почему значение теперь между 0 и 255?

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