#CSP202509C. HTTP 头信息

HTTP 头信息

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛大数据公司的服务器每天要处理海量的 HTTP 请求。为了提高传输效率，公司决定将所有服务器的 HTTP/1.1 版本升级到 HTTP/2 版本。小 C 作为一名实习生被分配到这个项目中，负责实现 HTTP 头信息的压缩算法 HPACK。HTTP（超文本传输协议）是万维网的基础协议。HTTP/1.1 版本中， 头信息使用纯文本格式传输，每个头字段占一行，字段名和字段值之间用冒号加空格分隔。HTTP/2 版本中， 头信息使用 HPACK（二进制格式）传输，减少了传输的数据量。

HTTP 的头信息，是一系列有序的键值对（key-value pairs），用于描述请求或响应的元数据，其中， 键是字段名，值是字段值，并且字段名是可以重复的。HPACK 引入了两张表格：静态表格和动态表格， 这两张表格中都存储有一系列的字段名和字段值。静态表格是预定义的，包含了一些常用的键值对； 而动态表格则是根据实际的请求和响应动态更新的。在解码开始前，动态表格为空。在解码过程中， 会不断向动态表格中添加新的键值对。动态表格的大小是有限的，当动态表格的条目数超过限制时， 会删除最旧的条目以腾出空间。静态表格和动态表格的条目可以出现重复，即可能存在字段名相同但字段值不同的条目； 也可能存在字段名和字段值都相同的条目。静态表格和动态表格的条目从 1 开始编号。假设静态表格有 SS 条目， 动态表格有 DD 条目，则静态表格中的条目依次编号为 1,2,…,S1,2,…,S，动态表格中的条目依次编号为 S+1,S+2,…,S+DS+1,S+2,…,S+D。当向动态表格中添加新的条目时，将新的条目插入到动态表格的最前面，即编号为 S+1S+1 的位置， 并将原有的条目依次向后移动一个位置。当动态表格中的条目数超过限制时，则去掉编号最大的条目。

HPACK 编码后的头信息由一系列的指令组成，每条指令表示一个头信息，将这些指令按顺序解码即可得到原始的头信息。 指令分为如下几种类型：

  • 表格引用指令：即直接按照编号输出静态或动态表格中的某个条目的字段名和字段值；
  • 字面量并索引指令：该指令包括一个编号，如果编号为 0，则另外跟随一个字符串，表示字段名；否则表示使用静态或动态表格中对应编号的条目的字段名。该指令还包括一个字符串，表示字段值。输出该字段名和字段值后，再将该键值对插入到动态表格；
  • 字面量不索引指令：该指令与字面量并索引指令类似，但不会将该键值对插入到动态表格中。

在前述指令中，出现的作为字段名或字段值的字符串，可以是原样输出的字符串，也可以是经过 Huffman 编码的字符串。

Huffman 编码是一种常用的无损数据压缩算法。它通过构造一棵二叉树来为每个字符分配一个唯一的二进制编码， 并使得常用字符的编码更短，从而减少整体数据的长度。在二叉树中，每个叶子节点表示一个字符，从根节点到叶子节点的路径表示该字符的编码：在路径上，向左走表示添加一个 0，向右走表示添加一个 1。这样，常用字符会出现在树的上层，拥有较短的编码，而不常用字符则会出现在树的下层，拥有较长的编码。

题目描述

为了表示一个 Huffman 编码树，对于 Huffman 树从根节点开始的每一个节点，如果这个节点是叶子节点， 那么输出 1，并且输出该节点对应的字符；否则输出 0，然后递归地对该节点的左子节点和右子节点进行同样的操作。 例如：

        *
       / \
      *   a
     / \
    b   *
       / \
      c   d

可以表示为 001b01c1d1a。根据该表示，即可还原出 Huffman 树。上面的树中，字符 a 的编码为 1；字符 b 的编码为 00；字符 c 的编码为 010；字符 d 的编码为 011。

对于前述三种指令，其格式约定如下：

  • 表格引用指令：1 i，其中 i 是一个正整数，表示引用编号为 ii 的条目；
  • 字面量并索引指令：2 0 k v 或 2 i v，其中 i 是一个正整数，表示使用编号为 ii 的条目的字段名；k 和 v 是字符串或 Huffman 编码的字符串，分别表示字段名和字段值；
  • 字面量不索引指令：3 0 k v 或 3 i v，其中 i 是一个正整数，表示使用编号为 ii 的条目的字段名；k 和 v 是字符串或 Huffman 编码的字符串，分别表示字段名和字段值。

其中，字符串是由小写字母、大写字母、数字（a-zA-Z0-9）组成的，其格式约定如下：

  • 普通字符串：s，当 s 的开头不是 H 时，表示原样输出字符串 s；当 s 的开头是 HH 时，表示输出字符串 s 去掉开头的第一个 H 后的部分；
  • Huffman 编码的字符串：Hb，其中 b 是一个由偶数个 0-9a-f 组成的字符串，表示原始字符串经过 Huffman 编码后得到的二进制数据序列（以十六进制显示）。其中，原始字符串靠前的字符对应的编码，存储于每一字节较高的位；每个字符的编码的高位存储于每一字节较高的位；每个字符的编码按位连续存储；最后一字节的低位补 0，并增加一字节表示补 0 的个数 pp（0≤p≤70≤p≤7）。例如，按前述 Huffman 树对字符串 abcd 进行编码，得到的二进制数据序列为 100010011，补 0 后为 10001001 10000000，最后一字节补了 7 个 0，因此表示为 H898007。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 SS 和 DD，分别表示静态表格和动态表格的条目数。接下来 SS 行，每行包含空格分隔的两个字符串，依次表示静态表格中每个条目的字段名和字段值。

接下来的一行包含一个字符串，表示 Huffman 树的表示。接下来的一行包含一个整数 NN，表示指令的条数。接下来 NN 行，每行表示一条指令，格式如前述所述。

输出格式

输出到标准输出。

输出 NN 行，每行表示解码后的头信息，格式为 key: value，其中 key 和 value 分别表示字段名和字段值。对于输入中的“普通字符串”和“使用霍夫曼编码的字符串”，需输出解码后得到的原始字符串。

3 3
Foo Bar
Foo Barz
bar barzz1
001b01c1d1a
11
1 1
3 3 ABCD
3 0 H898007 HHIJK
2 0 H898007 EFGH
1 4
2 0 DDDD EEEE
2 5 GGGG
1 4
1 6
2 0 HHHH IIII
1 4

Foo: Bar
bar: ABCD
abcd: HIJK
abcd: EFGH
abcd: EFGH
DDDD: EEEE
abcd: GGGG
abcd: GGGG
abcd: EFGH
HHH: IIII
HHH: IIII

样例 1 解释

输入首先给出了静态表的内容，和动态表的大小限制 D=3D=3。接着给出了 Huffman 树的表示 001b01c1d1a， 该表示即题目描述中的示例。接下来，输入给出了 11 个指令。其中，第一个指令表示引用静态表中编号为 1 的条目，因此直接输出 Foo: Bar。第二个指令表示使用静态表中第 3 项的字段名作为字段名，字段值为给定的 ABCD， 因此输出 bar: ABCD。第三个指令中，字段名使用了 Huffman 编码。其中，最后的 07 表示最后一个字节补了 7 个 0，因此十六进制串 8980 对应的二进制数据序列为 100010011， 解码后得到字符串 abcd。第三个指令中，字段值前有两个 H，需要去掉一个，因此得到输出为 abcd: HIJK。 第四个指令与第三个指令类似，但是要将得到的键值对插入到动态表中。第五个指令引用了编号为 4 的项目， 即动态表的第一项，因此输出 abcd: EFGH。第六个指令继续向动态表中插入新的键值对，此时动态表中已有两项。 第七个指令中，字段名使用了编号为 5 的条目，即动态表的第二项。需要注意的是，每次向动态表中插入新的条目时， 都将新的条目插入到动态表的最前面，并将原有的条目依次向后移动一个位置。因此，此时的动态表的第二项， 即为第四个指令中插入的条目，所以输出为 abcd: GGGG，然后再将该条目插入到动态表中。 第八个指令引用了编号为 4 的条目，即动态表的第一项，因此输出 abcd: GGGG。 第九个指令引用了编号为 6 的条目，即动态表的第三项，因此输出 abcd: EFGH。 第十个指令向动态表中继续插入一个条目，插入前动态表已满，因此需要在插入新条目前， 先丢弃最后一个条目，再将新条目插入到动态表的最前面。第十一个指令引用了编号为 4 的条目， 即动态表的第一项，因此输出 HHH: IIII。

子任务

对于 20%20\% 的数据，仅包含表格引用指令；

对于 40%40\% 的数据，仅包含表格引用指令和字面量不索引指令，且不包含 Huffman 编码的字符串；

对于 60%60\% 的数据，含有所有类型的指令，且字面量并索引指令的数目不超过 DD；

对于 100%100\% 的数据，有：1≤S≤641≤S≤64；1≤D≤1201≤D≤120；Huffman 树中字符的 01 编码长度不超过 8 位；1≤N≤10001≤N≤1000；表示字段名和字段值的字符串在解码前后的长度均不超过 150。

提示

本题提供了一些大语言模型生成的代码模块辅助解题，你可以参考、使用这些代码，也可以忽略它们自己手动实现全部功能，详情如下。

小 C 打开了某个大语言模型，并向它提问，以下是提问和回答：

提问：为了表示一个 Huffman 编码树，对于 Huffman 树从根节点开始的每一个节点，如果这个节点是叶子节点， 那么输出 1，并且输出该节点对应的字符；否则输出 0，然后递归地对该节点的左子节点和右子节点进行同样的操作。请根据上述表示的办法，将 Huffman 编码树恢复为树状结构。请分别给出 C++、Python、Java 语言的实现。

回答：我将为您提供C++、Python和Java三种语言的Huffman树恢复实现。

C++ 实现

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

struct Node {
    char data;
    shared_ptr<Node> left;
    shared_ptr<Node> right;

    Node(char d) : data(d), left(nullptr), right(nullptr) {}
    Node() : data('\0'), left(nullptr), right(nullptr) {}
};

shared_ptr<Node> rebuildHuffmanTree(const string& s, int& index) {
    if (index >= s.length()) return nullptr;

    if (s[index] == '1') {
        index++; // 跳过'1'
        char ch = s[index++]; // 读取字符
        return make_shared<Node>(ch);
    } else if (s[index] == '0') {
        index++; // 跳过'0'
        auto node = make_shared<Node>();
        node->left = rebuildHuffmanTree(s, index);
        node->right = rebuildHuffmanTree(s, index);
        return node;
    }
    return nullptr;
}

// 辅助函数：打印树结构（前序遍历）
void printTree(const shared_ptr<Node>& root, string prefix = "") {
    if (!root) return;

    if (root->data != '\0') {
        cout << prefix << "Leaf: " << root->data << endl;
    } else {
        cout << prefix << "Internal Node" << endl;
    }
    printTree(root->left, prefix + "  ");
    printTree(root->right, prefix + "  ");
}

int main() {
    string encodedTree = "001a1b1c"; // 示例：0表示内部节点，1表示叶子节点
    int index = 0;
    auto root = rebuildHuffmanTree(encodedTree, index);

    cout << "Rebuilt Huffman Tree:" << endl;
    printTree(root);

    return 0;
}

Python 实现

class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

def rebuild_huffman_tree(s, index):
    if index[0] >= len(s):
        return None

    if s[index[0]] == '1':
        index[0] += 1  # 跳过'1'
        ch = s[index[0]]
        index[0] += 1  # 读取字符
        return Node(ch)
    elif s[index[0]] == '0':
        index[0] += 1  # 跳过'0'
        node = Node()
        node.left = rebuild_huffman_tree(s, index)
        node.right = rebuild_huffman_tree(s, index)
        return node
    return None

# 辅助函数：打印树结构
def print_tree(root, prefix=""):
    if root is None:
        return

    if root.data is not None:
        print(f"{prefix}Leaf: {root.data}")
    else:
        print(f"{prefix}Internal Node")
    print_tree(root.left, prefix + "  ")
    print_tree(root.right, prefix + "  ")

# 使用示例
if __name__ == "__main__":
    encoded_tree = "001a1b1c"  # 示例编码
    index = [0]  # 使用列表来传递可变索引
    root = rebuild_huffman_tree(encoded_tree, index)

    print("Rebuilt Huffman Tree:")
    print_tree(root)

Java 实现

class Node {
    Character data;
    Node left;
    Node right;

    Node(Character data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    Node() {
        this.data = null;
        this.left = null;
        this.right = null;
    }
}

public class HuffmanTreeRebuilder {

    public static Node rebuildHuffmanTree(String s, int[] index) {
        if (index[0] >= s.length()) {
            return null;
        }

        if (s.charAt(index[0]) == '1') {
            index[0]++; // 跳过'1'
            char ch = s.charAt(index[0]);
            index[0]++; // 读取字符
            return new Node(ch);
        } else if (s.charAt(index[0]) == '0') {
            index[0]++; // 跳过'0'
            Node node = new Node();
            node.left = rebuildHuffmanTree(s, index);
            node.right = rebuildHuffmanTree(s, index);
            return node;
        }
        return null;
    }

    // 辅助函数：打印树结构
    public static void printTree(Node root, String prefix) {
        if (root == null) {
            return;
        }

        if (root.data != null) {
            System.out.println(prefix + "Leaf: " + root.data);
        } else {
            System.out.println(prefix + "Internal Node");
        }
        printTree(root.left, prefix + "  ");
        printTree(root.right, prefix + "  ");
    }

    public static void main(String[] args) {
        String encodedTree = "001a1b1c"; // 示例编码
        int[] index = {0}; // 使用数组来传递可变索引
        Node root = rebuildHuffmanTree(encodedTree, index);

        System.out.println("Rebuilt Huffman Tree:");
        printTree(root, "");
    }
}
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 湘ICP备2024052008号 | Copyright © 2025 - 至今 水木清研. All rights reserved.
  3. Worker 0, 73ms
  4. Powered by Hydro v5.0.0-beta.2 Community