lzw编码

lzw编码也是一种压缩算法，相较于算术编码，这个的优势就是不存在稀奇古怪的精度问题，但是有一个问题就是，这个因为需要建立字典表，最终有可能造成字典表长度过长。不过这个字典表不是随着需要发送的信息一起发送的，所以最后影响的就是编码解码主机上内存占用过大。

这里有一个参考链接https://blog.csdn.net/hanzhen7541/article/details/91141112

首先，不管是编码还是解码都有一个默认的字典表，这个字典表只存最基本的字符，就比如我们这儿的字典表就只存了26个英文字母。

编码的时候我们有两个用来记录的字符串，一个叫pre，一个叫curr，开始时，pre和curr都是空串，每读入一个新的字符，令curr等于新读入的串，然后判断pre+curr是否在字典表里面，如果在的话，不输出，令pre=pre+curr，如果不在的话，此时的pre肯定在字典表里面的，然后输出此时的pre对应的编码，在字典表中添加pre+curr，然后更新pre=curr。最后新串读完后，再将此时对应的pre对应的编码添加到编码串最后。

解码的时候，我们同样设置两个记录串，一个叫pre一个叫curr。开始我们可以肯定第一个编码一定在默认字典表里面，令pre等于第一个解码出来的字符然后开始循环。循环的内容为，判断此时的编码信息是否能在字典表里面找到，若能找到的话，令curr等于该解码出来的值并直接输出为解码字符串，同时更新字典表，将pre+curr[1]添加到字典表的最后面并更新pre=curr。若不能找到的话，我们可以知道该编码值肯定由此时的pre和新加入的curr组成，而这个pre+curr肯定为下一次的pre，这样其第一个字符就是我们此时pre的第一个字符，这样我们就可以知道此时curr的值求出来就是pre+pre[0]。

下面是代码

#include <iostream>

#include <map>

#include <string>

#include <vector>



using namespace std;



int main()

{

    map<string, int> dictionary;

    map<int, string> reflect_decionary;

    string message;

    string pre = "", curr = "";

    vector<int> encoded_message;

    string tmp;

    int last = 26;



    cout << "please input your message to encode: ";

    cin >> message;



    for (int i = 0; i < 26; ++i)

    {

        tmp.push_back('a' + i);

        dictionary[tmp] = i;

        reflect_decionary[i] = tmp;

        tmp.clear();

    }



    for (int i = 0; i < message.length(); ++i)

    {

        curr = message[i];

        if (dictionary.count(pre + curr) == 0)

        {

            encoded_message.push_back(dictionary[pre]);

            dictionary[pre + curr] = last++;

            pre = curr;

        }

        else

        {

            pre = pre + curr;

        }

    }



    encoded_message.push_back(dictionary[pre]);



    pre.clear();

    curr.clear();

    message.clear();

    last = 26;



    cout << "encoded message: " << encoded_message[0] << " ";



    pre = reflect_decionary[encoded_message[0]];

    message += pre;



    for (int i = 1; i < encoded_message.size(); ++i)

    {

        cout << encoded_message[i] << " ";

        if (reflect_decionary.count(encoded_message[i]))

        {

            message += reflect_decionary[encoded_message[i]];

            curr = reflect_decionary[encoded_message[i]];

            reflect_decionary[last++] = pre + curr[0];

            pre = curr;

        }

        else

        {

            tmp = pre + pre.substr(0, 1);

            message += tmp;

            reflect_decionary[last++] = tmp;

            pre = tmp;

        }

    }

    cout << endl;



    cout << "decoded message: " << message << endl;



    return 0;

}