2022-06-12 LZW压缩算法，单词查找树，二进制读写

• 前言
• 一、LZW是谁？
• 二、LZW压缩原理
• • 1.构建编码字典树及压缩文件
  • 2.压缩数据的还原
• 总结
• • 三向单词查找树
  • 二进制读写

霍夫曼压缩是一种将定长编码搞成变长编码的压缩方式，而LZW压缩算法则是将变长编码搞成定长编码的压缩方式，都是天才的算法。

A. Lempel、 J. Ziv 和 T. Welch。

好吧，计算机领域有很多能人，领域外的人不知道，所以就这样吧。

我们通过开始输入的编码流充实一个基于 ASCII 码为值，对应字符为键，构建的查找树 ST：

例如：

A B R A C A D A B R A B R A B R A

在查找树中，我们查找上述字符串的最长前缀，于是找到 A ，将A对应的值写入文件，扩充 AB 到字典树，并将 AB 对应的值设置为 256 + 1 （最大 ASCII 码 + 1）

继续在去除 A 后的子字符串中，查找最长前缀，于是找到 B，将B的值写入文件， 并将 BR 插入字典树，对应值为 256 + 2。

以此类推，随着字典树的扩充，和字符串的变短，我们会慢慢的找到更长的前缀，比如 AB，然后我们将 AB 对应的编码 257 写入文件，然后将 ABR 加入字典树。

我们设置写入文件的数字为 16 位的二进制编码。只要有重复的字符串，就会有一个 16 位二进制编码对应它，并写入文件，实现了压缩的目的。原算法是 12 位的，需要不停的对齐，同时字典树的大小限制在 4096 以内，不够快，但对小文件很合适。16 位写入速度可以将整体速度提升约 5 倍，对大文件压缩效率更高。

实现中，压缩的过程和编码树的构建是同时进行的。

由于需要构建一个所有 ASCII 码开头的单词查找树，我改用以每个 ASCII 码为头的单词查找树组成的 vector 数组，这种数据结构可以节省一定开销。当然，这也为自己埋了坑，因为 char 是 8 位有符号类，所以构造数组用 0 — 255 转换为 char 是可以的，但从 char 转回来可能是负值（一般文本文件不会遇到，但二进制文件可能性很高），需要显示转换为 unsigned char 否则会越界，好在这种转换基本无开销。

同时，使用一个定位器 chOrder 指示压缩字符串还没被处理的部分，同原始算法相比，不用不停的构造 substring ，节省了一定开销。对于 C++ 这种 string 不太完美的语言，可以平均节省约 10 倍的时间。

    void compress() const
    {
#ifdef _WIN64
        _setmode(_fileno(stdin), _O_BINARY);
        _setmode(_fileno(stdout), _O_BINARY);
#endif
        std::vector> stVec(alphaSize);
        std::string input;

        getStrTree(stVec, input);

        getCmprss(stVec, input);

#ifdef _WIN64
        _setmode(_fileno(stdin), _O_TEXT);
        _setmode(_fileno(stdout), _O_TEXT);
#endif
    }

private:
    //构造单词查找树，并构造预压缩字符串
    static void getStrTree(std::vector> &stVec,
                           std::string &input)
    {
        input.reserve(stringSize);

        for (int i = 0; i != alphaSize; ++i)
        {
            stVec[i].put({static_cast(i)}, i);
        }

        std::array chArray;
        size_t chCnt = codeSize;

        while (chCnt == codeSize)
        {
            chCnt = fread(chArray.data(), 1, codeSize, stdin);
            input.append(chArray.data(), chCnt);
        }
    }

    //根据字典树和预压缩字符串进行压缩，并输出至标准输出
    static void getCmprss(std::vector> &stVec,
                          std::string &input)
    {
        size_t strCode = alphaSize + 1;
        size_t chOrder = 0;
        size_t preStrSize = 0;
        size_t stVecIndex = 0;
        std::string preStr;

        while (input.size() > chOrder)
        {
            stVecIndex = static_cast(input[chOrder]);
            
            preStr = stVec[stVecIndex].longestPrefixOf(input, chOrder);
            
            BIO::bout.writeShort(
                static_cast(stVec[stVecIndex].get(preStr).second));
                
            preStrSize = preStr.size();
            
            if ((preStrSize + chOrder < input.size()) && strCode < codeSize)
            {
                stVec[stVecIndex].put(input.substr(chOrder, preStrSize + 1),
                                      strCode++);
            }
            
            chOrder += preStrSize;
        }

        BIO::bout.writeShort(alphaSize);
        BIO::bout.close();
    }

    static constexpr const size_t alphaSize = 0x100;
    static constexpr const size_t codeSize = 0x8000;
    static constexpr const size_t stringSize = 0x100000;

压缩是一个由字符串到定长编码的过程，还原则是反过程，由定长编码反推字符串。

构建编码到字符从查找字典数组：

首先，设置一个能容纳所有16位二进制数编码的数组，并将前 0 — 255 位置设为值为 ASCII 码字符的字符串，将 256 位置对应为空 “ ”。

然后读入16 位的编码，开始的编码必然是 ASCII 码，比如：

A B R A C A D A B R A B R A B R A

把 A 编码转为字符 A，输出到文件，再读入一个字符 B ，然后用前面的字符连接后面的字符，在字典数组中将连接的字符串 AB 赋值给 257 位置，BR 赋值给 258， RA 赋值给259，等等，这是一个反过程。最终随着字典的扩充，文件被还原了。

有个小问题：

A B A B A B A

编码是 65(A) 66(B) 257(AB) 259(ABA) 256(结束符)

我们可以很容易的得到 A ， B ， AB（通过前面的字符连接得到），但我们如何得到 ABA 呢？

重新梳理一下：

得到 A（65）A B A B A B A

得到 B（66）A ** B** A B A B A

基于 A 和 B 得到 AB （257）AB A B A B A

根据 B A B 得到 BA （258）A BA B A B A

259 编码一定是 AB + 某个字符，不是 BA 是因为 BA 编码没有出现，但 AB 的编码出现了，它要增加一个字母变成另一个编码 （259）

如果是前面没有出现的字符，比如C，则必须出现C的但字符编码，然而没有。

如果是B，则需要前面ABB，但第二个B的位置和其后序位置又应该是 AB，矛盾。

所以259只能是 AB 连接自己的第一个字符 ABA。所有相同情况都是如此，即前面编码出现的字符串与自己头字母的组合。

这个比较绕，需要好好思考一下。

    void expand() const
    {
#ifdef _WIN64
        _setmode(_fileno(stdin), _O_BINARY);
        _setmode(_fileno(stdout), _O_BINARY);
#endif
        std::vector stVec(codeSize); //单词字典数组
        size_t codeIndex = 0;                     //字典数组索引

        expVec(stVec, codeIndex);

        getExpand(stVec, codeIndex);

#ifdef _WIN64
        _setmode(_fileno(stdin), _O_TEXT);
        _setmode(_fileno(stdout), _O_TEXT);
#endif
    }

private:
    //构造单词查找Vector
    static void expVec(std::vector &stVec, size_t &codeIndex)
    {
        for (codeIndex = 0; codeIndex != alphaSize; ++codeIndex)
        {
            stVec[codeIndex] = {static_cast(codeIndex)};
        }
        stVec[codeIndex++] = " ";
    }

    static void getExpand(std::vector &stVec, size_t &codeIndex)
    {
        //编码值
        int16_t strCode = 0;

        //读取编码值
        BIO::bin.readShort(strCode);

        //编码对应的字符串值
        std::string codeStr = stVec[strCode];

        //编码还原后的字符串
        std::string expandStr;

        while (true)
        {
            fwrite(codeStr.data(), 1, codeStr.size(), stdout);
            BIO::bin.readShort(strCode);
            if (strCode == alphaSize)
            {
                break;
            }
            expandStr = stVec[strCode];
            if (codeIndex == strCode)
            {
                expandStr = codeStr + codeStr.at(0);
            }
            if (codeIndex < codeSize)
            {
                stVec[codeIndex++] = codeStr + expandStr.at(0);
            }
            codeStr = expandStr;
        }
        BIO::bout.close();
    }

留两个坑，下回填。

编写程序时候，用到单词查找树，我又发现以前写的三向单词树的问题，以及二进制文件读写问题。

最后说一下优化，正确使用string 类的 substr() 函数。

以前发的三向单词查找树中 search() 函数有问题，导致求得的最长前缀 longestPrefixOf 函数错误，已经修改。

// 基于三向单词查找树符号表
template  struct TST;

// 三向字符查找树链表节点
template  struct NodeT
{
    NodeT() = default;
    ~NodeT()
    {
        delete lft;
        delete mid;
        delete rht;
        delete val;
    }
    friend struct TST;

  private:
    unsigned char ch = 0;
    NodeT *lft = nullptr;
    NodeT *mid = nullptr;
    NodeT *rht = nullptr;
    V *val = nullptr;
};

// 基于三向单词查找树符号表
template  struct TST
{

    TST() = default;
    ~TST()
    {
        delete root;
        root = nullptr;
        cnt = 0;
    }

    // 键key所对应的值（如果键不存在则返回null)
    auto get(const std::string &key) const -> std::pair
    {
        NodeT *nodePtr = get(root, key, 0);
        if (nodePtr != nullptr && nodePtr->val != nullptr)
        {
            return {true, *nodePtr->val};
        }
        return {false, V()};
    }

    // 向表中插入键值对（如果值为null则删除键key）
    void put(const std::string &key, const V &val)
    {
        root = put(root, key, val, 0);
    }

    // str 中 order 位置开始的前缀中最长的键
    auto longestPrefixOf(const std::string &str, size_t order) const
        -> std::string
    {
        if (str.size() <= order)
        {
            return "";
        }
        int length = search(root, str, order, order);
        return str.substr(order, length - order);
    }

  private:
    // 递归获取 key 对应的 NodeT 指针
    auto get(NodeT *nodePtr, const std::string &key, int chOrder) const
        -> NodeT *
    {
        if (nodePtr == nullptr || key.empty())
        {
            return nullptr;
        }
        unsigned char chr = key.at(chOrder);
        if (chr < nodePtr->ch)
        {
            return get(nodePtr->lft, key, chOrder);
        }
        if (chr > nodePtr->ch)
        {
            return get(nodePtr->rht, key, chOrder);
        }
        if (chOrder < key.size() - 1)
        {
            return get(nodePtr->mid, key, chOrder + 1);
        }
        return nodePtr;
    }

    auto put(NodeT *NodeTptr, const std::string &key, const V &val,
             int chOrder) -> NodeT *
    {
        unsigned char c = key.at(chOrder);
        if (NodeTptr == nullptr)
        {
            NodeTptr = new NodeT();
            NodeTptr->ch = c;
        }
        if (c < NodeTptr->ch)
        {
            NodeTptr->lft = put(NodeTptr->lft, key, val, chOrder);
        }
        else if (c > NodeTptr->ch)
        {
            NodeTptr->rht = put(NodeTptr->rht, key, val, chOrder);
        }
        else if (chOrder < key.size() - 1)
        {
            NodeTptr->mid = put(NodeTptr->mid, key, val, chOrder + 1);
        }
        else
        {
            if (NodeTptr->val == nullptr)
            {
                ++cnt;
                NodeTptr->val = new V(val);
            }
            else
            {
                *NodeTptr->val = val;
            }
        }
        return NodeTptr;
    }

    auto search(NodeT *nodePtr, const std::string &str, int chOrder,
                int length) const -> int
    {
        if (nodePtr == nullptr || chOrder == str.size())
        {
            return length;
        }
        unsigned char ch = str.at(chOrder);
        if (ch > nodePtr->ch)
        {
            return search(nodePtr->rht, str, chOrder, length);
        }
        if (ch < nodePtr->ch)
        {
            return search(nodePtr->lft, str, chOrder, length);
        }
        chOrder++;
        if (nodePtr->val != nullptr)
        {
            length = chOrder;
        }
        return search(nodePtr->mid, str, chOrder, length);
    }

    NodeT *root = nullptr;
    unsigned cnt = 0;
};

二进制读写时，我发现无法使用 int16_t 类型与 char 类型的变量进行 “位或” 运算，使用 “ int16_t |= char ” 会得到错误值。显示转换也都不行，所以还是用 memcpy 大法，用 char[2] 去模拟 int16_t，都占两字节。

这也给自己埋了个坑，内存布局和我想的不一样，一般人都会顺序读两个 char 然后拷贝给 int16_t，对吧，但是反了，应该倒着读两个 char 然后拷贝给 int16_t 才是对的，给个小程序，自己debug一下，用 16 进制看。

#include 
#include 
#include 

auto main(int , char *argv[]) -> int
{
    int16_t x = 0;
    char a[] = {'a', 'b'};
    memcpy(&x, a, 2);
    return 0;
}

//a[0] = 0x61
//a[1] = 0x62
//x = 0x6261

同时我尝试用 C 的 fwrite ，fread 代替 cin.write ，cin.read，效果非常好，所以对于基本类型读写，建议还是 C 比较有效率。

namespace BIO
{
struct binstream
{
    //不允许进行构造
    binstream(const binstream &) = delete;
    //不允许进行构造
    binstream(binstream &&) = delete;
    //不允许进行拷贝
    auto operator=(const binstream &) -> binstream & = delete;
    //不允许进行拷贝
    auto operator=(binstream &&) -> binstream & = delete;

    //返回局部静态变量
    static auto getbin() -> binstream &
    {
        static binstream bin;
        return bin;
    }

    //比特流是否为空
    inline auto isEmpty() -> bool
    {
        return feof(stdin) != 0;
    }

    //读取1位数据并返回一个bool值
    auto readBool(bool &bit) -> bool
    {
        if (N == 0)
        {
            fillBuffer();
        }
        bit = inbuffer[--N];
        return !isEmpty();
    }

    //读取8位数据并返回一个char值
    auto readChar(char &ch) -> bool
    {
        if (N == 0)
        {
            fillBuffer();
        }
        if (N == buffersize)
        {
            memcpy(&ch, &inbuffer, 1);
            fillBuffer();
            return true;
        }
        if (N >= 0)
        {
            int oldN = N;
            auto tempBuff = inbuffer;
            tempBuff <<= (buffersize - N);
            fillBuffer();
            N = oldN;
            tempBuff |= (inbuffer >> N);
            memcpy(&ch, &tempBuff, 1);
            return !isEmpty();
        }
        return false;
    }

    //读取int16值
    auto readShort(int16_t &num) -> bool
    {
        char tempbuff[2];
        readChar(tempbuff[1]);
        readChar(tempbuff[0]);
        memcpy(reinterpret_cast(&num), tempbuff, 2);
        return !isEmpty();
    }

    //关闭比特流
    void close()
    {
        fclose(stdin);
    }

    //恢复流状态
    void clear()
    {
        clearerr(stdin);
    }

  private:
    //私有化默认构造，用于单例模式
    binstream() = default;

    //读流到缓冲区
    void fillBuffer()
    {
        if (fread(reinterpret_cast(&inbuffer), 1, 1, stdin) != 0U)
        {
            N = buffersize;
        }
        else
        {
            N = -1;
        }
    }

    static constexpr int buffersize = 8;
    //缓冲区
    std::bitset inbuffer = 0;
    //缓冲区比特指针
    int N = 0;
};

auto &bin = BIO::binstream::getbin();

struct boutstream
{
    boutstream(const boutstream &) = delete;
    boutstream(boutstream &&) = delete;
    auto operator=(const boutstream &) -> boutstream & = delete;
    auto operator=(boutstream &&) -> boutstream & = delete;

    //取得局部静态变量
    static auto getbout() -> boutstream &
    {
        static boutstream bout;
        return bout;
    }

    //写入指定的比特
    void writeBool(bool bit)
    {
        outbuffer <<= 1;
        if (bit)
        {
            outbuffer[0] = true;
        }
        N++;
        if (N == buffersize)
        {
            fwrite(reinterpret_cast(&outbuffer), 1, 1, stdout);
            fflush(stdout);
            N = 0;
            outbuffer = 0;
        }
    }

    //写入指定的8位字符
    void writeChar(char ch)
    {
        if (N == 0)
        {
            fwrite(&ch, 1, 1, stdout);
            return;
        }
        std::bitset bf = ch;
        for (int i = buffersize - 1; i != -1; --i)
        {
            writeBool(bf[i]);
        }
    }

    //写入int16值
    void writeShort(int16_t num)
    {
        writeChar(static_cast(num >> 8));
        writeChar(static_cast(num >> 0));
    }

    //关闭比特流, 刷新缓冲流
    void close()
    {
        clearBuffer();
        fflush(stdout);
    }

  private:
    boutstream() = default;

    void clearBuffer()
    {
        if (N <= 0)
        {
            return;
        }
        if (N > 0)
        {
            outbuffer <<= (buffersize - N);
        }
        fwrite(&outbuffer, 1, 1, stdout);
        N = 0;
        outbuffer = 0;
    }

    static constexpr int buffersize = 8;
    //缓冲区
    std::bitset outbuffer = 0;
    //缓冲区比特指针
    int N = 0;
};

auto &bout = BIO::boutstream::getbout();

} // namespace BIO