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

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

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


person Viviane    schedule 07.11.2016    source источник
comment
Также был приведен пример ввода: Кодировать: 0 42 42 85 85 85 85 172 172 172 13 13 42 -1 и Декодировать: 1 2 42 4 85 3 172 2 13 1 42 -1   -  person Viviane    schedule 07.11.2016
comment
Добавьте это к вопросу, а не к комментарию.   -  person Barmar    schedule 08.11.2016


Ответы (1)


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

<length> <value>

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

<value>

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

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

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

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

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

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

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

Почему сейчас значение находится в диапазоне от 0 до 255?

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

person Barmar    schedule 07.11.2016
comment
Большое спасибо за этот просветительский ответ! Еще один вопрос, знаете ли вы, почему value > 127 указывает на is_tuple_start ? в моем понимании закодированные нормальные символы тоже могут быть больше 127, так что не обязательно значит это начало кортежа? - person Crystina; 18.11.2020
comment
Вот как он говорит, является ли байт длиной или байтом данных. - person Barmar; 18.11.2020
comment
но я думал, что 128-256 - это расширенные символы ASCII, которые также могут быть в байтах данных? Или мы просто предполагаем, что они не включены в данные? - person Crystina; 19.11.2020
comment
Вы не можете сделать их как один байт. Если вам нужен байт 200, вы должны представить его как 129 200: длина 1, значение байта 200. Вы можете представлять только значения ниже 128 как один байт. - person Barmar; 19.11.2020
comment
В противном случае невозможно определить, является ли это длиной или данными. - person Barmar; 19.11.2020
comment
и это будет означать, что эти расширенные символы ascii могут быть представлены в большем количестве байтов после сжатия, я думаю? так как теперь мы должны сохранить байт для длины - person Crystina; 19.11.2020
comment
да. RLE обеспечивает хорошее сжатие только в том случае, если у вас много повторяющихся байтов. - person Barmar; 19.11.2020
comment
Также обратите внимание, что традиционный RLE использует длину перед всем: length1 byte1 length2 byte2 .... Подход здесь может использовать 1 байт, когда длина = 1 и байт ‹ 128, так что на самом деле это улучшение. - person Barmar; 19.11.2020
comment
Я вижу, спасибо за все эти хорошие подробные объяснения! - person Crystina; 19.11.2020