### leetcode 271

凡人#分割法

```
class Codec {
public:
    string encode(vector<string>& strs) 
    {
        string res;
        for (int i = 0; i < strs.size(); i++) {
            // 使用 to_string 存储长度（文本格式）
            res += to_string(strs[i].size());
            res += '#'; // 添加分隔符避免歧义
            res += strs[i];
        }
        return res;
    }

    vector<string> decode(string s) {
        vector<string> res;
        int index = 0;
        while (index < s.size()) {
            // 找到 '#' 分隔符
            int pos = s.find('#', index);
            // 解析长度（文本转整数）
            int size = stoi(s.substr(index, pos - index));
            index = pos + 1;
            // 提取字符串内容
            res.push_back(s.substr(index, size));
            index += size;
        }
        return res;
    }
};
```

# 字符串序列化协议：基于长度前缀编码

## 引言

在分布式系统、网络通信和数据持久化场景中，我们经常需要将多个字符串序列化为单一的字节流进行传输或存储。一个设计良好的编码协议需要满足以下要求：

1. **无歧义性**：能够准确还原原始数据结构
2. **高效性**：编解码开销小，空间利用率高
3. **鲁棒性**：能够处理包含特殊字符的字符串

本文将分析一种基于**长度前缀编码（Length-Prefix Encoding）**的字符串序列化方案，并解读其C++实现的技术细节。

## 协议设计原理

### 核心思想

长度前缀编码的核心思想是：==在每个字符串前附加一个固定长度的整数字段==，表示后续字符串的字节长度。这种设计避免了使用分隔符可能带来的转义问题。

### 编码格式

对于字符串数组 `{"Hello", "World"}`，编码后的格式为：

```
[长度1][字符串1][长度2][字符串2]...
```

具体到二进制层面（假设32位整数，小端序）：

```
原始数据: {"Hello", "World"}
编码结果: \x05\x00\x00\x00Hello\x05\x00\x00\x00World
          └─────┬─────┘└──┬──┘└─────┬─────┘└──┬──┘
            长度=5    内容    长度=5    内容
```

### 协议优势

1. **无需转义**：字符串内容可以包含任意字节，包括空字符 `\0`
2. **定长头部**：==长度字段固定为 `sizeof(int)` 字节，解析效率高==
3. **流式处理**：支持顺序读取，内存占用可控

## 实现

### 代码

```cpp
#include <vector>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

class Codec {
public:
    /**
     * 编码函数：将字符串数组序列化为单一字符串
     * 
     * @param strs 待编码的字符串向量
     * @return 编码后的字节流字符串
     * 
     * 示例:
     *   输入: {"Hello", "World"}
     *   输出: "\x05\x00\x00\x00Hello\x05\x00\x00\x00World"
     */
    string encode(vector<string>& strs) {
        string res;
        
        // 预分配内存以提高性能（可选优化）
        size_t total_size = 0;
        for (const auto& str : strs) {
            total_size += sizeof(int) + str.size();
        }
        res.reserve(total_size);
        
        // 逐个编码字符串
        for (const auto& str : strs) {
            int size = str.size();
            
            // 1: 将整数的二进制表示直接写入字符串
            // string构造函数原型: string(const char* s, size_t n)
            // 功能: 从字符数组s复制前n个字节
            res += string(reinterpret_cast<const char*>(&size), sizeof(size));
            
            // 追加字符串内容
            res += str;
        }
        
        return res;
    }

    /**
     * 解码函数：从字节流还原字符串数组
     * 
     * @param s 编码后的字节流字符串
     * @return 解码后的字符串向量
     * 
     * 示例:
     *   输入: "\x05\x00\x00\x00Hello\x05\x00\x00\x00World"
     *   输出: {"Hello", "World"}
     */
    vector<string> decode(string s) {
        vector<string> res;
        size_t index = 0;
        
        while (index < s.size()) {
            // 2: 从字节流重建整数
            int size = 0;
            // void* memcpy(void* dest, const void* src, size_t n)
            // s.data()返回指向内部字符数组的指针（C++11前==c_str()）
            memcpy(&size, s.data() + index, sizeof(size));
            index += sizeof(size);
            
            // 提取指定长度的子字符串
            res.push_back(s.substr(index, size));
            index += size;
        }
        
        return res;
    }
};
```

### 解析

#### 1. 整数到字节流的转换

```cpp
int size = 5;
string length_field(reinterpret_cast<const char*>(&size), sizeof(size));
```

**技术原理**：
- `&size` 获取整数的内存地址
- `reinterpret_cast<const char*>` ==将整数指针重新解释为字符指针==
- `string` 构造函数从字符数组复制 `sizeof(int)` 个字节

**内存布局示例**（32位小端序系统）：
```
整数 5 的内存表示:
地址:  0x1000  0x1001  0x1002  0x1003
内容:  0x05    0x00    0x00    0x00
       └────────────┬────────────┘
              转换为字符串
              "\x05\x00\x00\x00"
```

#### 2. 字节流到整数的重建

```cpp
int size = 0;
memcpy(&size, s.data() + index, sizeof(size));
```

**技术原理**：
- `s.data()` 返回指向字符串内部缓冲区的指针
- `memcpy` 从指定位置复制 `sizeof(int)` 个字节到 `size` 变量
- 这是C语言风格的类型转换，效率高

**API对比**：

```cpp
// C++11之前
const char* ptr = s.c_str();  // 返回C风格字符串

// C++11之后
const char* ptr = s.data();   // 功能相同，但语义更清晰
```

#### 3. 字符串构造函数的巧妙运用

```cpp
// 构造函数原型
string(const char* s, size_t n);
```

**使用场景**：
```cpp
// 场景1: 从字节数组构造（可能包含\0）
char buffer[] = {0x48, 0x00, 0x69};  // "H\0i"
string str(buffer, 3);  // 正确处理内嵌空字符
cout << str.size();     // 输出: 3

// 场景2: 提取子字符串
string full = "Hello World";
string sub(full.data() + 6, 5);  // "World"
```

### 优化

#### 1. 内存预分配

```cpp
string encode(vector<string>& strs) {
    // 计算总大小
    size_t total_size = 0;
    for (const auto& str : strs) {
        total_size += sizeof(int) + str.size();
    }
    
    // 一次性分配内存，避免多次重新分配
    string res;
    res.reserve(total_size);
    
    // ... 编码逻辑
}
```

**性能提升**：避免 `string` 多次扩容带来的内存拷贝开销。

#### 2. 使用变长整数编码（VarInt）

对于大量短字符串的场景，固定4字节的长度字段存在浪费。可以采用变长编码：

```cpp
// VarInt编码示例（类似Protocol Buffers）
string encodeVarInt(int value) {
    string result;
    while (value >= 0x80) {
        result += static_cast<char>((value & 0x7F) | 0x80);
        value >>= 7;
    }
    result += static_cast<char>(value);
    return result;
}
```

**优势**：
- 小于128的长度只占1字节
- 小于16384的长度只占2字节

#### 3. 批量处理优化

```cpp
// 使用ostringstream减少临时对象创建
#include <sstream>

string encode(vector<string>& strs) {
    ostringstream oss;
    for (const auto& str : strs) {
        int size = str.size();
        oss.write(reinterpret_cast<const char*>(&size), sizeof(size));
        oss.write(str.data(), str.size());
    }
    return oss.str();
}
```

## 应用场景

### 1. 网络协议设计

```cpp
// TCP消息帧格式
struct MessageFrame {
    uint32_t length;  // 消息长度（网络字节序）
    char data[];      // 消息内容
};

// 使用本协议编码多个消息
vector<string> messages = {"MSG1", "MSG2", "MSG3"};
string encoded = codec.encode(messages);
send(socket_fd, encoded.data(), encoded.size(), 0);
```

### 2. 数据库序列化

```cpp
// 将多列字符串数据序列化存储
class RowSerializer {
    Codec codec;
public:
    string serialize(const vector<string>& row) {
        return codec.encode(const_cast<vector<string>&>(row));
    }
    
    vector<string> deserialize(const string& data) {
        return codec.decode(data);
    }
};
```

### 3. 缓存系统

```cpp
// Redis-like缓存的批量操作
class CacheClient {
    Codec codec;
public:
    void mset(const vector<string>& keys, const vector<string>& values) {
        vector<string> combined;
        combined.insert(combined.end(), keys.begin(), keys.end());
        combined.insert(combined.end(), values.begin(), values.end());
        
        string encoded = codec.encode(combined);
        // 发送到缓存服务器
    }
};
```

## 边界情况与错误处理

### 1. 空字符串处理

```cpp
vector<string> test = {"", "Hello", ""};
string encoded = codec.encode(test);
// 编码结果: "\x00\x00\x00\x00\x05\x00\x00\x00Hello\x00\x00\x00\x00"
```

### 2. 大字符串处理

```cpp
// 对于超大字符串，考虑使用64位长度字段
class Codec64 {
    string encode(vector<string>& strs) {
        string res;
        for (const auto& str : strs) {
            uint64_t size = str.size();  // 使用64位
            res += string(reinterpret_cast<const char*>(&size), sizeof(size));
            res += str;
        }
        return res;
    }
};
```

### 3. 数据校验

```cpp
vector<string> decode(string s) {
    vector<string> res;
    size_t index = 0;
    
    while (index < s.size()) {
        // 边界检查
        if (index + sizeof(int) > s.size()) {
            throw runtime_error("Corrupted data: incomplete length field");
        }
        
        int size = 0;
        memcpy(&size, s.data() + index, sizeof(size));
        index += sizeof(int);
        
        // 长度校验
        if (size < 0 || index + size > s.size()) {
            throw runtime_error("Corrupted data: invalid length");
        }
        
        res.push_back(s.substr(index, size));
        index += size;
    }
    
    return res;
}
```

## 跨平台兼容性考虑

### 字节序问题

不同CPU架构的字节序可能不同（大端序 vs 小端序）。对于跨平台传输，需要统一字节序：

```cpp
#include <arpa/inet.h>  // Linux/Unix
// #include <winsock2.h> // Windows

string encode(vector<string>& strs) {
    string res;
    for (const auto& str : strs) {
        uint32_t size = str.size();
        uint32_t network_size = htonl(size);  // 转换为网络字节序（大端序）
        res += string(reinterpret_cast<const char*>(&network_size), sizeof(network_size));
        res += str;
    }
    return res;
}

vector<string> decode(string s) {
    vector<string> res;
    size_t index = 0;
    
    while (index < s.size()) {
        uint32_t network_size = 0;
        memcpy(&network_size, s.data() + index, sizeof(network_size));
        uint32_t size = ntohl(network_size);  // 转换为主机字节序
        index += sizeof(network_size);
        
        res.push_back(s.substr(index, size));
        index += size;
    }
    
    return res;
}
```

## 性能基准测试

```cpp
#include <chrono>

void benchmark() {
    // 生成测试数据
    vector<string> test_data;
    for (int i = 0; i < 10000; i++) {
        test_data.push_back(string(100, 'A' + (i % 26)));
    }
    
    Codec codec;
    
    // 编码性能测试
    auto start = chrono::high_resolution_clock::now();
    string encoded = codec.encode(test_data);
    auto end = chrono::high_resolution_clock::now();
    auto encode_time = chrono::duration_cast<chrono::microseconds>(end - start);
    
    // 解码性能测试
    start = chrono::high_resolution_clock::now();
    vector<string> decoded = codec.decode(encoded);
    end = chrono::high_resolution_clock::now();
    auto decode_time = chrono::duration_cast<chrono::microseconds>(end - start);
    
    cout << "编码时间: " << encode_time.count() << " μs\n";
    cout << "解码时间: " << decode_time.count() << " μs\n";
    cout << "原始大小: " << test_data.size() * 100 << " bytes\n";
    cout << "编码大小: " << encoded.size() << " bytes\n";
    cout << "空间开销: " << (encoded.size() - test_data.size() * 100) << " bytes\n";
}
```

**典型测试结果**（10000个100字节字符串）：
```
编码时间: 1523 μs
解码时间: 1876 μs
原始大小: 1000000 bytes
编码大小: 1040000 bytes
空间开销: 40000 bytes (4%)
```

## 总结

本文介绍的长度前缀编码方案是一种经典且高效的字符串序列化协议，其核心优势在于：

1. **简洁性**：实现仅需不到50行代码
2. **高效性**：编解码时间复杂度为线性，空间开销固定
3. **鲁棒性**：支持任意字节内容，无需转义处理
4. **实用性**：广泛应用于网络协议、数据库、缓存等系统

在实际应用中，可以根据具体场景进行优化：
- 对于短字符串场景，使用变长整数编码减少空间开销
- 对于跨平台传输，统一使用网络字节序
- 对于性能敏感场景，使用内存预分配和批量处理

这种设计思想也体现了计算机系统设计的核心原则：**==在简洁性和效率之间寻找最佳平衡点==**。

---

**参考资源**：
- [LeetCode 271: Encode and Decode Strings](https://leetcode.cn/problems/encode-and-decode-strings/)
- [Protocol Buffers Encoding](https://developers.google.com/protocol-buffers/docs/encoding)
- [C++ String Reference](https://en.cppreference.com/w/cpp/string/basic_string)

