在 HTTP/2 中解码霍夫曼编码
Decode Huffman encoding in HTTP/2
我正在尝试了解如何对 HTTP/2 header 进行霍夫曼解码。我看到的大多数文档都在谈论频率为 table 的二叉树，但对于 HTTP/2，它只是一个静态查找 table。我的编码部分工作正常，但解码让我感到困惑，因为我不知道如何告诉我每次应该占用多少位。
霍夫曼编码是 prefix-free code。这意味着没有编码符号是任何其他编码符号的前缀。
如果存在由位串 00111 表示的符号，则不可能有 001110 或 001111 或 0011100110011 表示的符号 - 没有别的将从 00111 开始。如果您已经阅读了位串 00111，则不需要标记来告诉您您位于符号的末尾。如果您可以从您目前已读取的位生成输出符号，则您必须生成该输出符号并开始读取下一个。
当你读完0011后，你将无法输出任何东西，因为0011不是一个符号。不可能，因为它是 00111.
的前缀
霍夫曼编码总是为每个可能的位串赋予某种意义（除了过早结束的位串）。 0011 本身没有意义，这意味着必须至少有 2 个以 0011 开头的符号代码。至少一个以 00110 开头，至少一个以 00111.
开头
要解码输入比特流，您从代表无输入的状态开始，然后读取一位，然后移动到代表您目前已读取的比特的状态。例如，如果您处于状态 00 并且您读取了 1，则您移动到状态 001。当你到达对应于一个符号的状态时，你输出那个符号并在读取下一位之前回到初始状态。
（请注意，检测流的结尾不在霍夫曼编码的范围内。包含的协议必须告诉您如何知道您何时到达比特流的结尾。）
由于每个状态恰好有2个可能的后继状态（对应一个0位和一个1位），状态转换形成一个二叉树。在每个 non-leaf 节点，您正在阅读一些内容来决定是向左 child 还是向右 child，并且在每个叶节点您已经完成对符号的解码，您输出那个符号，然后回到根。
您可以从符号列表及其编码构建树，然后遍历树以解码输入。编写构建树的代码可能会给您带来真正理解霍夫曼代码的体验。
当你有一个像
这样的输入列表时
A 00
B 010
C 011
D 100
E 1010
F 1011
G 1100
H 1101
I 1110
J 1111
你的树结构应该满足
root->symbol is null
root->left->symbol is null
root->left->left->symbol = A
root->left->right->left->symbol = B
root->left->right->right->symbol = C
...
（在这个伪代码中，每个节点都有 3 个属性，但在真实的语言中，您可能会找到更有效的表示。每个节点都需要有一个 symbol 或一对 pointers/references 到 left 和 right child 个节点。）
因为你有一个静态代码列表，你只需要构建一次树，你可以在程序的整个生命周期中重复使用它。
我正在尝试了解如何对 HTTP/2 header 进行霍夫曼解码。我看到的大多数文档都在谈论频率为 table 的二叉树，但对于 HTTP/2，它只是一个静态查找 table。我的编码部分工作正常，但解码让我感到困惑，因为我不知道如何告诉我每次应该占用多少位。
霍夫曼编码是 prefix-free code。这意味着没有编码符号是任何其他编码符号的前缀。
如果存在由位串 00111 表示的符号，则不可能有 001110 或 001111 或 0011100110011 表示的符号 - 没有别的将从 00111 开始。如果您已经阅读了位串 00111，则不需要标记来告诉您您位于符号的末尾。如果您可以从您目前已读取的位生成输出符号，则您必须生成该输出符号并开始读取下一个。
当你读完0011后，你将无法输出任何东西，因为0011不是一个符号。不可能，因为它是 00111.
霍夫曼编码总是为每个可能的位串赋予某种意义（除了过早结束的位串）。 0011 本身没有意义，这意味着必须至少有 2 个以 0011 开头的符号代码。至少一个以 00110 开头，至少一个以 00111.
要解码输入比特流，您从代表无输入的状态开始，然后读取一位，然后移动到代表您目前已读取的比特的状态。例如，如果您处于状态 00 并且您读取了 1，则您移动到状态 001。当你到达对应于一个符号的状态时，你输出那个符号并在读取下一位之前回到初始状态。
（请注意，检测流的结尾不在霍夫曼编码的范围内。包含的协议必须告诉您如何知道您何时到达比特流的结尾。）
由于每个状态恰好有2个可能的后继状态（对应一个0位和一个1位），状态转换形成一个二叉树。在每个 non-leaf 节点，您正在阅读一些内容来决定是向左 child 还是向右 child，并且在每个叶节点您已经完成对符号的解码，您输出那个符号，然后回到根。
您可以从符号列表及其编码构建树，然后遍历树以解码输入。编写构建树的代码可能会给您带来真正理解霍夫曼代码的体验。
当你有一个像
这样的输入列表时A 00
B 010
C 011
D 100
E 1010
F 1011
G 1100
H 1101
I 1110
J 1111
你的树结构应该满足
root->symbol is null
root->left->symbol is null
root->left->left->symbol = A
root->left->right->left->symbol = B
root->left->right->right->symbol = C
...
（在这个伪代码中，每个节点都有 3 个属性，但在真实的语言中，您可能会找到更有效的表示。每个节点都需要有一个 symbol 或一对 pointers/references 到 left 和 right child 个节点。）
因为你有一个静态代码列表，你只需要构建一次树，你可以在程序的整个生命周期中重复使用它。