LZW编码解码cpp实现

编码过程：

• 1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。
• 2：当前字符 C=字符流中的下一个字符。

• 3：判断 P+C 是否在词典中

  (1) 如果“是”，则用C扩展P，即让P=P+C，返回步骤2

  (2) 如果“否”，则:

  输出与当前前缀P相对应的码字W；

  将P＋C添加到词典中；

  令P=C，并返回步骤2

实际上就是从字典中匹配最长的串，输出其码字

然后该串加上下一个字符必定是不在字典中的，再将其加入字典即可

注意最后处理尾部

#include<iostream>
#include<string>
#include<map>
using namespace std;

int main(){
    string s;
    cin>>s;
    int index = ;
    map<string, int> m;
    string ts;
    for(int i=; i<; i++){
        char c[] = {i, '\0'};
        m[c] = i;
    }

    string p;
    string c;
    for(int i=; i<s.size(); i++){
        c = s[i];
        ts = p+c;
        if(m.find(ts) != m.end()){
            //在词典中: 更新前缀
            p = ts;
        }else{
            //不在词典中: 添加至字典，并输出前缀词典值
            int w =  m[p];
            cout<<w<<" ";
            m.insert(pair<string, int>(ts, index++));
            p = c;
        }
    }
    //尾处理
    int w =  m[p];
    cout<<w<<" ";
    cout<<endl<<endl;

    //打印字典
    map<string, int>::iterator it = m.begin();
    for(; it != m.end(); it++){
        if(it->second > )
            cout<<it->first<<"\t"<<it->second<<endl;
    }
    return ;
}
           

解码：

当 当前码字cw不在词典中时，唯一可能的情况是：下一个需要添加到词典中的串 就是cw所代表的串

#include<iostream>
#include<string>
#include<map>
using namespace std;

int main(){
    int index = ;
    map<int, string> m;
    string ts;
    for(int i=; i<; i++){
        char c[] = {i, '\0'};
        m[i] = string(c);
    }
    int i=;
    string p;
    string c;
    int pw = -; //前一码字
    int cw = -; //当前码字
    cin>>pw;
    cout<<m[pw];
    while(cin>>cw){
        if(m.find(cw) != m.end()){
            //cw在词典中，直接输出
            p = m[cw];
        }else{
            //cw不在词典中
            p = m[pw];
            p = p+c;
        }
        cout<<p;
        c = p.substr(, );
        m[index++] = m[pw]+c;
        pw = cw;
        i++;
        //if(i == 5) break;
    }
    cout<<endl;
    //打印字典
    map<int, string>::iterator it = m.begin();
    for(; it != m.end(); it++){
        if(it->first > )
            cout<<it->first<<"\t"<<it->second<<endl;
    }
    return ;
}