LZW压缩算法

超、凢脫俗 2022-09-27 04:54 144阅读 0赞

**1.LZW压缩适用的场景：**

**对于有大量重复出现的字符或者字符串，可以将重复出现的多个串用一个字符表示，并写进文件。比如可以压缩这个字符串：“TOBEORNOTTOBEORTOBEORNOT ”，这个字符串中出现了大量的TO，BE，OR，NOT等等字符，我们就可以将这些重复出现的字符压缩写进文件。这里只是说明算法，并没有涉及写进文件的操作。**

**2.压缩和解压缩的原理：**

**（1）压缩：这里定义一个字典，字典里存放字符或者字符串的编码。一开始字典被初始化为：**

**A:1 B:2 C:3 D:4 ..... Y:25 Z:26**

**之后，出现字母T，我们就将20（ASCII中20对应的字符）写进压缩文件，然后将TO写进字典并编号27.下一个读到字符O，将15写进压缩文件，OB写进字典等等。所以，字典就会被扩充。**

**TO:27**

**OB:28**

**BE:29**

**EO:30**

**等等。**

**所以，压缩的时候，只需要将出现的字符或者字符串（有在字典中出现过）的编码写进压缩文件即可，（比如，TO在字典中出现过，我们就将TO的编码写进文件，不会单独记录T和O），并将当前的字符或者字符串与下一个字符组成新的串写进字典。**

**（2）解压缩：用编码找到对应的字符或者字符串，然后写进解压缩文件（比如，看到编码15，就会将T写入解压缩文件）。**

**3.代码实现：**

#include<iostream>
    using namespace std;
    #include<string>
    //LZW压缩和解压缩
    typedef struct Dict
    {
           string _s;
           int _code;
    }Dict;
    class Compress
    {
    public:
           Compress(int maxSize,string text)
           {
                  _maxSize = maxSize;
                  _code = new int[maxSize];
                  _size = 0;
                  _text = text;
                  _dict = new Dict[_maxSize];
                  _dictSize = 0;
                  //过滤0号位置
                  Insert("#");
                  //向字典中插入26个字母
                  string s = "A";
                  for (int i = 0; i < 26; ++i)
                  {
                         Insert(s);
                         s[0]++;
                  }
           }
           ~Compress()
           {
                  delete[] _code;
                  delete[] _dict;
                  _code = NULL;
                  _dict = NULL;
                  _maxSize = 0;
                  _size = 0;
           }
           string Encode()
           {
                  string s;//存储压缩后的字符串
                  string cur;
                  char next;
                  int i = 0;
                  while (i < _text.size())
                  {
                         cur.insert(cur.size(),1, _text[i]);
                         i++;
                         next = _text[i];
                         while (FindCode(cur) != -1)//当前串在字典中
                         {      
                               cur.insert(cur.size(), 1, next);
                               ++i;
                               if (i != _text.size())
                                      next = _text[i];
                               else
                                      break;
                         }
                         if (i != _text.size())
                         {
                               char c = cur.at(cur.size() - 1);
                               cur.erase(cur.end()-1);
                               _code[_size] = FindCode(cur);
                               ++_size;
                               cur += c;
                               c =  _code[_size-1];
                               s.push_back(c);
                               Insert(cur);
                         }             
                         if(i == _text.size() && FindCode(cur) != -1)
                         {
                               _code[_size] = FindCode(cur);
                               s.push_back(_code[_size]);
                               break;
                         }             
                         --i;
                         cur.clear();
                  }
                  return s;
           }
           string Decode(const string& s)
           {
                  string text;
                  string cur;
                  if (s.size() <= 0)
                         return s;
                  int code;
                  for (int i = 0; i < s.size(); ++i)
                  {
                         code = (int)(s[i]);
                         cur = FindSeq(code);
                         text += cur;
                  }
                  return text;
           }
           void PrintDict()
           {
                  cout<<"seq  code"<<endl;
                  for (int i = 0; i < _dictSize; ++i)
                  {
                         cout << _dict[i]._s << "     " << _dict[i]._code<<endl;
                  }
           }
    protected:
           int FindCode(const string& s)
           {
                  for (int i = 0; i < _dictSize; ++i)
                  {
                         if (s == _dict[i]._s)
                               return i;
                  }
                  return -1;
           }
           string FindSeq(int code)
           {
                  return _dict[code]._s;
           }
           void Insert(string seq)
           {
                  _dict[_dictSize]._s = seq;
                  _dict[_dictSize]._code = _dictSize;
                  _dictSize++;
           }
    private:
           Dict* _dict;
           int _dictSize;
           int* _code;
           int _size;
           int _maxSize;
           string _text;
    };
    int main()
    {
           string text;
           cin >> text;
           Compress c(100,text);
           //c.PrintDict();
           string s = c.Encode();
         //  c.PrintDict();
           //cout << s;
           cout<<c.Decode(s)<<endl;
           system("pause");
           return 0;
    }

**代码运行结果：**

**![Center][]**

**当然了，要实现真正的压缩，就要把压缩信息写进文件。如果要将压缩和解压缩进行分离的话，还需要在解压缩的时候，完成一次字典的填充工作。**

**这里只是为了说明算法而已。**

[Center]: /images/20220708/a621f1efa5ee45d6b4c86519ffecee8f.png