imageCompressDp.cc

#include <bits/stdc++.h>

using namespace std;

const unsigned char imageGvalues[] = {10, 9, 12, 40,
                                      50, 35, 15, 12,
                                      8, 10, 9, 15,
                                      11, 130, 160, 240};

string toBits(unsigned char b)
{
    string ans;
    while (b)
    {
        ans.push_back((b & 1) + '0');
        b >>= 1;
    }
    for (size_t i = ans.size(); i < 8; i++)
    {
        ans.push_back('0');
    }
    reverse(begin(ans), end(ans));
    return ans;
}

string toBinary(const unsigned char arr[], size_t len)
{
    string ans;
    for (size_t i = 0; i < len; i++)
    {
        ans.append(toBits(arr[i]));
    }
    return ans;
}

size_t bmax(const string& bits, size_t l, size_t r)
{
    size_t _max = 0;
    for (size_t i = l; i < r; i += 8)
    {
        size_t cnt = 0;
        for (size_t j = i; j < i + 8; j++)
        {
            if (bits[j] == '1')
                break;
            cnt++;
        }
        if (cnt == 8)
            cnt = 7;
        _max = max(_max, 8 - cnt);
    }
    return _max;
}

vector<size_t> optimumSize, optLen, maxBitLen;
void compressImage(const string& bits)
{
    optimumSize.resize(bits.size() / 8 + 1);
    optLen.resize(bits.size() / 8 + 1);
    maxBitLen.resize(bits.size() / 8 + 1);
    optimumSize.front() = 0;
    optLen.front()      = 0;
    maxBitLen.front()   = 0;
    for (size_t i = 1; i < optimumSize.size(); i++)
    {
        optimumSize[i] = ULLONG_MAX;
        for (size_t k = 1; k <= min(i, 256ull); k++)
        {
            size_t tmp = k * bmax(bits, 8 * (i - k), 8 * i);
            if (11 + optimumSize[i - k] + tmp < optimumSize[i])
            {
                optimumSize[i] = tmp + 11 + optimumSize[i - k];
                optLen[i]      = k;
                maxBitLen[i]   = tmp / k;
            }
        }
        cout << "1 - " << i << " st pixel needs " << optimumSize[i] << " bits.And the last segement has " << optLen[i] << " pixels and each pixel needs " << maxBitLen[i] << " bits." << endl;
    }
}

vector<pair<size_t, size_t>> constructSolution()
{
    vector<pair<size_t, size_t>> res;
    size_t remain = optimumSize.size() - 1;
    while (remain != 0)
    {
        res.push_back({optLen[remain], maxBitLen[remain]});
        remain -= optLen[remain];
    }
    reverse(begin(res), end(res));
    return res;
}
struct Node
{
    unsigned char ch;
    int weight;
    struct Node *left, *right, *parent;
};

struct cmp
{
    bool operator()(const Node* a, const Node* b)
    {
        if (a->weight != b->weight)
            return a->weight > b->weight;
        return a->ch < b->ch;
    }
};

Node* encodeByHuffman(const string& bits, string& code)
{
    if (bits.size() / 8 < 2)
        return nullptr;
    unordered_map<unsigned char, size_t> frequencyOfChar;
    for (size_t i = 0; i < bits.size() / 8; i++)
    {
        unsigned char tmp = 0;
        for (size_t j = i * 8; j < i * 8 + 8; j++)
        {
            tmp = tmp * 2 + bits[j] - '0';
        }
        frequencyOfChar[tmp]++;
    }

    priority_queue<Node*, vector<Node*>, cmp> forest;
    vector<Node*> roofNode;
    for (auto&& i : frequencyOfChar)
    {
        Node* now   = new Node;
        now->ch     = i.first;
        now->weight = i.second;
        now->parent = now->left = now->right = nullptr;
        forest.push(now);
        roofNode.push_back(now);
    }
    while (forest.size() > 1)
    {
        Node* now            = new Node;
        now->ch              = 0;
        now->right           = forest.top();
        forest.top()->parent = now;
        forest.pop();
        now->left            = forest.top();
        forest.top()->parent = now;
        forest.pop();
        now->weight = now->left->weight + now->right->weight;
        forest.push(now);
    }
    Node* root = forest.top();
    forest.pop();
    unordered_map<unsigned char, string> haffmanCode;
    for (auto&& i : roofNode)
    {
        Node* t = i;
        string codeOfchar;
        while (t != root)
        {
            if (t->parent->left == t)
            {
                codeOfchar.push_back('0');
            }
            else if (t->parent->right == t)
            {
                codeOfchar.push_back('1');
            }
            t = t->parent;
        }
        reverse(codeOfchar.begin(), codeOfchar.end());
        haffmanCode.insert({i->ch, codeOfchar});
    }
    code.clear();
    for (size_t i = 0; i < bits.size() / 8; i++)
    {
        unsigned char tmp = 0;
        for (size_t j = i * 8; j < i * 8 + 8; j++)
        {
            tmp = tmp * 2 + bits[j] - '0';
        }
        code += haffmanCode[tmp];
    }
    return root;
}

string decodeByHuffman(Node* Huffman, const string& bit)
{
    vector<unsigned char> str;
    Node* now = Huffman;
    for (auto&& i : bit)
    {
        if (i == '0')
            now = now->left;
        else
            now = now->right;
        if (now->left == nullptr and now->right == nullptr)
        {
            str.push_back(now->ch);
            now = Huffman;
        }
    }
    string bits;
    for (auto&& i : str)
    {
        bits.append(toBits(i));
    }
    return bits;
}

signed main(void)
{
    auto bitsValue = toBinary(imageGvalues, sizeof(imageGvalues) / sizeof(imageGvalues[0]));
    compressImage(bitsValue);
    cout << "--------------------------" << endl;
    cout << "The optimal compress case:" << endl;
    auto solution = constructSolution();
    for (size_t i = 0; i < solution.size(); i++)
    {
        cout << i + 1 << " st segement has " << solution[i].first << " pixels and each pixel needs " << solution[i].second << " bits." << endl;
    }
    cout << "--------------------------" << endl;
    cout << "Origin image needs " << bitsValue.size() << " bits" << endl;
    cout << "Compressd image needs " << optimumSize.back() << " bits" << endl;
    cout << "--------------------------" << endl;
    string bit;
    Node* Huffman    = encodeByHuffman(bitsValue, bit);
    string decodeStr = decodeByHuffman(Huffman, bit);
    assert(decodeStr == bitsValue);
    cout << "Huffman compress the image needs " << bit.size() << " bits" << endl;
    cout << "--------------------------" << endl;

    return 0;
}