런 길이 인코딩 (정수)

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"; 
     } 
} 

내 질문에 대한 답변을 얻고 코드가 기본적으로 복사하여 붙여 넣을 수 있기를 바랍니다. 반복되지 않는 값이 단순히 저장하는 동안

<length> <value> 

:이 인코딩 작동

Answer 1

방법은 같은 반복 값의 순서가 저장되어 있다는 점이다

<value> 

그러나 당신이 볼 때 인코딩 된 시퀀스의 숫자, 첫 번째 형식의 길이 부분인지 또는 반복되지 않는 단일 값인지 어떻게 알 수 있습니까? 128을 인코딩하기 전에 길이에 추가하는 규칙을 사용하여이 작업을 수행합니다. 따라서 128보다 큰 숫자는 첫 번째 형식을 시작하는 <length> 바이트입니다.

하지만 반복되지 않는 항목의 값이 128보다 큰 경우에는 어떻게해야합니까? 이에 대한 해결책은 큰 값에 대해 첫 번째 형식을 사용하고이 값을 runlength = 1으로 반복 된 값으로 처리하는 것입니다.

모든 범위 추가 및 빼기에 대한 대부분의 질문에 대답해야합니다.

왜 런 타임이이 범위 내에 있어야합니까?

우리는 모든 것을 0에서 255까지의 바이트로 저장합니다. 길이가 127보다 길면 128을 더하면 128보다 큰 숫자를 얻을 수 있습니다.이 값은 바이트에 맞지 않습니다.

은 가치가 있습니까? 아니면 전체 시퀀스?

선언문은 int value;이므로 하나의 숫자 일뿐입니다. cin >> value; 때마다 시퀀스의 다음 바이트를 가져옵니다.

왜 이제 0과 255 사이의 값입니까?

값은 항상 전체 바이트 일 수 있으며 길이는 128자를 추가하기 때문에 127 자로 제한됩니다. 위의 설명에서 높은 값은 항상 길이가 첫 번째 인 튜플로 인코딩된다는 것을 알 수 있습니다.