比较简单的两种字符串的编码与解码

摘要: 字符串的编码解码，分隔符、分块编码

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 哈夫曼树与哈夫曼编码 和 k叉哈夫曼树 中，我们学习了 2 叉和 k 叉哈夫曼树和哈夫曼编码，并用于了字符串编解码问题中。本文我们回顾一下力扣 271. 字符串的编码与解码，看一下比较简单的两种字符串的编解码方式：

• 用非 ASCII 作分隔符, 类似于树的序列化。
• 分块编码(HTTP v1.1 使用的编码)。

---

题目

• 271. 字符串的编码与解码

请你设计一个算法，可以将一个 字符串列表 编码成为一个 字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

1 号机（发送方）有如下函数：

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

2 号机（接收方）有如下函数：

vector<string> decode(string s) {
  //... your code
  return strs;
}

1 号机（发送方）执行：

string encoded_string = encode(strs);

2 号机（接收方）执行：

vector<string> strs2 = decode(encoded_string);

此时，2 号机（接收方）的 strs2 需要和 1 号机（发送方）的 strs 相同。

请你来实现这个 encode 和 decode 方法。

注意：

因为字符串可能会包含 256 个合法 ascii 字符中的任何字符，所以您的算法必须要能够处理任何可能会出现的字符。
请勿使用 “类成员”、“全局变量” 或 “静态变量” 来存储这些状态，您的编码和解码算法应该是非状态依赖的。
请不要依赖任何方法库，例如 eval 又或者是 serialize 之类的方法。本题的宗旨是需要您自己实现 “编码” 和 “解码” 算法。

题解

算法1: 用非 ASCII 分隔符

每个字符串可以包含 256 个有效的 ASCII 码字符。因此可以用非 ASCII 字符作为分隔符, 例如 (char)256。

用非 ASCII 作分隔符, 类似于树的序列化，比如以下这些问题：

• 449. 序列化和反序列化二叉搜索树
• 428. 序列化和反序列化 N 叉树
• 297. 二叉树的序列化与反序列化

代码(c++)

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        if(strs.empty()) return "";
        string result;
        char p = (char)256;
        for(const string& str: strs)
            result += str + p;
        return result;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        if(s.empty()) return {};
        vector<string> result;
        int n = s.size();
        int left = 0;
        char p = (char)256;
        while(left < n)
        {
            int right = left;
            while(right < n && s[right] != p)
                ++right;
            result.push_back(s.substr(left, right - left));
            left = right + 1;
        }
        return result;
    }
};

算法2: 分块编码

分块编码是 HTTP v1.1 采用的编码, 不依赖于输入字符集，因此比方法一更具有通用性和有效性。

HTTP 1.1 中 Transfer-Encoding chunked 编码
当不能预先确定报文体的长度时，不可能在头中包含 Content-Length 域来指明报文体长度，此时就需要通过 Transfer-Encoding 域来确定报文体长度。
通常情况下，Transfer-Encoding 域的值应当为 chunked,表明采用chunked编码方式来进行报文体的传输。chunked编码是HTTP/1.1 RFC里定义的一种编码方式，因此所有的HTTP/1.1应用都应当支持此方式。
chunked 编码的基本方法是将大块数据分解成多块小数据，每块都可以自指定长度

数据流被分成块，每个块前面都有其字节大小。

以 [["abcfe", "uv", "hij"]] 为例, 编码后的字符串, 结构如下图

编码

遍历字符串数组，计算字符串的长度，将长度换为 4 个字节的字符串(一个 char 一字节)。

长度装换为 4 字节字符串不能直接 to_string, 因为规定了长度为 4 字节, 而to_string 不会补前导零, 例如 36 会转换成 “36”, 而不是 “0036”。

可以借助 stringstream 和 <iomanip> 中的 setw(4) 和 setfill('0')。

int n = 36;
string str;
stringstream ss;
ss << setw(4) << setfill('0') << n;
ss >> str;

将长度信息的字符串添加到编码字符串的前面。

• 前面 4 个字节表示了编码字符串的长度。
• 后面跟这字符串本身。

返回编码后的字符串。

解码

初始化指针 left = 0 然后在字符串上推进 left，当 left < n：

• 读四个字节 s[left..left+4]，得当前字符串的长度，将 s[left..left+4] 转为整数 len。
• 推进 left += 4。
• 添加当前字符串到答案 s.substr(left, len)。
• 推进 left += length。

返回解码后的字符串数组。

代码(c++)

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        if(strs.empty()) return "";
        string result = "";
        for(const string& str: strs)
        {
            string len_str;
            int len = str.size();
            stringstream ss;
            ss << setw(4) << setfill('0') << len;
            ss >> len_str;
            result += len_str + str;
        }
        return result;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        if(s.empty()) return {};
        vector<string> result;
        int n = s.size();
        int left = 0;
        while(left < n)
        {
            string len_str = s.substr(left, 4);
            stringstream ss;
            int len;
            ss << len_str;
            ss >> len;
            left += 4;
            string str = s.substr(left, len);
            result.push_back(str);
            left += len;
        }
        return result;
    }
};

扩展1: 字符串的哈夫曼编码

• 哈夫曼树与哈夫曼编码
• k叉哈夫曼树

扩展2: Redis 中字符串的编码

• Redis中字符串的编码

---