7
\$\begingroup\$

I have made two quite basic algorithms used for lossless data compression.

This is my RLE:

#include <string>

std::string rle(const std::string& input) // encode (aaaaeecd -> 4a2e1c1d)
{
    std::string output;

    int n = input.size();
    int i = 0;
    while(i < n)
    {
        int run_count = 1;
        int max_run_count = std::min(255, n - i); // condition: i + run_count < n, runcount <= 255
        while(run_count < max_run_count && input[i + run_count] == input[i])
            run_count++;
        output += run_count; // run_count is between 0 and 255 (unsigned char)
        output += input[i];
        i += run_count;
    }

    return output;
}

std::string irle(const std::string& input) // decode (4a2e1c1d -> aaaaeecd)
{
    std::string output;

    for(int i = 0; i < input.size(); i += 2)
    {
        int nb = (int)(unsigned char)input[i]; // range between 0 and 255
        for(int k = 0; k < nb; k++)
            output += input[i+1];
    }

    return output;
}

and here goes my MTF:

#include <string>
#include <deque>
#include <list>
#include <algorithm>

/*
if alphabet A = {'a', 'b', 'c'}
    then string "accbc" is encoded 02021
    (a is at index 0, alphabet remains {'a', 'b', 'c'}, outputs 0 ;
     c is at index 2, alphabet becomes {'c', 'a', 'b'}, outputs 2 ;
     c is at index 0, alphabet remains {'c', 'a', 'b'}, outputs 0 ;
     b is at index 2, alphabet becomes {'b', 'c', 'a'}, outputs 2 ;
     a is at index 1, alphabet becomes {'a', 'b', 'c'}, outputs 1)
*/
std::string mtf(const std::string& input)
{
    std::string output;

    std::list<char> alphabet; // constant erase/insert
    for(int i = 0; i <= 255; i++)
        alphabet.push_back((char)i);

    for(char c: input)
    {
        auto c_it = find(alphabet.begin(), alphabet.end(), c); // find char c in the alphabet
        output += distance(alphabet.begin(), c_it); // output index of char c in the alphabet
        // move character to the front of the alphabet
        alphabet.erase(c_it);
        alphabet.insert(alphabet.begin(), c);
    }

    return output;
}

/*
reverse operation:
    for each number, outputs the character at the corresponding index in the alphabet
        then move this character to the front of the alphabet
        and keep going
*/
std::string imtf(const std::string& input)
{
    std::string output;

    std::deque<char> alphabet; // constant erase (begin) & operator[] ; insert (middle) is O(n)
    for(int i = 0; i <= 255; i++)
        alphabet.push_back((char)i);

    for(unsigned char n: input)
    {
        char temp_c = alphabet[n];
        output += temp_c;
        alphabet.erase(alphabet.begin() + n);
        alphabet.insert(alphabet.begin(), temp_c);
    }

    return output;
}

I know there are many possible improvments possible, especially for the RLE algorithm. I would just like a review on the C++ syntax I've used, especially on the structures I have chosen.

\$\endgroup\$
4
\$\begingroup\$

Looks quite nice, but let's get down to ripping it apart.

First your runlength-encoding:

  1. Try to use the same type for size-variables / indices throughout:
    std::basic_string<...> uses std::size_t.
    That way you would also heal the one sign-mismatch.

  2. Your comment about the encoded form // encode (aaaaeecd -> 4a2e1c1d) is wrong.
    You probably meant: // encode (aaaaeecd -> \x04a\x02e\x01c\x01d)

  3. You are wasting \x00 and thus the chance to encode runs of length 256.
    (Yes, the comment // run_count is between 0 and 255 (unsigned char) is wrong.)

  4. You are missing the header <algorithm>.

Next your Move-To-Front:

  1. I suggest you move from std::list to std::array.
    A list is a far too heavy data-structure, jumping every-which-way in memory kills your performance quite easily.

  2. The std::deque is a bit better, but using a std::array would probably still handily beat it due to simplicity.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.