Huffman table 在流末尾查找
Huffman table lookup at end of stream
我刚刚了解了基于 table 的高效霍夫曼解码算法。可以在此处找到简短描述：（使用两级 tables）。主要目标是通过花费有限的内存来减少解码时间。我想我理解这些算法是如何工作的。
我不明白的是：每个真实的比特流都是有限的。这意味着在某些时候（在流的末尾）它不会剩下 9 位（在 9 位 LUT 的情况下需要将其作为 LUT 的索引）但对于较短的代码可能只有几位。使用这些位作为索引是行不通的。
每次从流中获取位并附加足够的 0 位以始终获得完整索引时，我都可以检查剩余位的数量。然而，这会为每个代码查找添加一个比较操作，这是一种浪费，因为它只对潜在大流的最后几位有效。
是否有更有效的方法来处理该问题？
“将这些位用作索引将不起作用。”
实际上，是的。
对于膨胀，位从最低位开始。然后你的位累加器在底部有可用位，在上面有零或垃圾。这些位是什么并不重要。在您的查找中使用它 table。如果得到的解码代码长度小于或等于可用位数，则处理该代码，丢弃累加器中的位，然后重复。
对于正确的流，您最终会在累加器中得到零位。如果您得到的解码代码的长度大于剩余的可用位数，那么您的流是无效的。您的流中最后可用的位已确定为较长代码的前缀。
我刚刚了解了基于 table 的高效霍夫曼解码算法。可以在此处找到简短描述：
我不明白的是：每个真实的比特流都是有限的。这意味着在某些时候（在流的末尾）它不会剩下 9 位（在 9 位 LUT 的情况下需要将其作为 LUT 的索引）但对于较短的代码可能只有几位。使用这些位作为索引是行不通的。 每次从流中获取位并附加足够的 0 位以始终获得完整索引时，我都可以检查剩余位的数量。然而，这会为每个代码查找添加一个比较操作，这是一种浪费，因为它只对潜在大流的最后几位有效。
是否有更有效的方法来处理该问题？
“将这些位用作索引将不起作用。”
实际上，是的。
对于膨胀，位从最低位开始。然后你的位累加器在底部有可用位，在上面有零或垃圾。这些位是什么并不重要。在您的查找中使用它 table。如果得到的解码代码长度小于或等于可用位数，则处理该代码，丢弃累加器中的位，然后重复。
对于正确的流，您最终会在累加器中得到零位。如果您得到的解码代码的长度大于剩余的可用位数，那么您的流是无效的。您的流中最后可用的位已确定为较长代码的前缀。