java - Java源代码生成中的霍夫曼代码解码器编码器

Question

我想用Java创建一个快速的霍夫曼代码解码器，因此考虑了查找表。由于这些表占用内存，并且我们使用Java代码导航和访问表，因此可以轻松（或不容易）编写表示同一表的程序/方法。

这种方法的问题是，我不知道什么是最佳策略。我知道很多有关缓存和分支预测的内容。同样，切换案例的实现意味着实际的ASM不在我范围内。如果我有一个内存中查找表（或它的层次结构），则可以简单地跳入和跳出，但是出于我的目的，我建议将该表放入高速缓存中。

由于我实际上走了一棵树，因此可以像执行其他语句一样需要一定数量的比较来实现它，但是对于每个比较，则需要附加的二进制运算。

因此存在以下选项：


内存查找表中使用的通用算法
决策树的if / else表示
if / else表示法，使用小的switch语句查找正确的符号组（相同的位模式长度）（如果if语句较少，则可能是更多代码）。
代码的switch语句表示


编写和进行基准测试非常棘手，因此任何初步想法都会很棒。

起作用的另一个问题是位的顺序。最重要的位始终位于最前面，这意味着它以相反的顺序存储。


  如果您的树是A = 0，B = 10，C = 11以编写BAC，则它实际上是01 + 0 + 11（加上意味着追加）。


因此，实际上必须以相反的顺序编写代码。对组使用if / else或switch方法将不会有问题，因为屏蔽位很简单，并且位的反转也很可能，但是由于相反，它将失去使组内的索引脱离掩码的想法位顺序的添加和删除具有不同的含义，并且不可能进行简单的查找。

反转位是一项昂贵的操作（我使用4位查找表），不会超过二进制操作的性能损失。

但是，在旅途中反转位更适合此操作，并且每位需要进行四个操作（上移，屏蔽，加法以及下移输入）。由于我提前读取了所有这些位，因此所有这些操作都将在寄存器中完成，因此它们可能只需要几个周期。

这样，我可以使用switch，sub和if来找到正确的符号组并返回它们。

最后，我需要一些建议。由于我的代码在语言处理方面是全球通用的，因此可以进行硬连线（即在源代码中）。

我不知道像ANTRL这样的解析器生成器用来表达那些决定。由于他们也根据输入符号来缝制切换或是否/其他，这可能会给我一个提示。

[更新]

我发现了一种简化方法，可以避免反向位问题，但仍会增加每组的成本。因此，我最终按照要遍历的组的顺序编写了位。因此，我不需要每个位四个修改，而是每个组（不同的位长）。

对于每个组，我们有：
1.第一个元素的值，大小（以及该组中最后一个元素的值）。

因此，对于每个组，算法如下：
1.读取兆位并与当前读取值合并。
2.将值与该组的最后一个值进行比较，如果该值不在该组中，则该值在该组中较小。 ->继续阅读
3.如果它在组中，则可以访问值数组或使用switch语句。

这是完全通用的，可以不使用循环就可以有效地使用。同样，如果检测到该组，则代码的位长是已知的，并且可以从源中消耗这些位，因为代码看起来很远（从流中读取）。

[更新2]

要访问实际值，可以使用按组分组的单个大元素数组。由于按组分组的可传输性降低，因此很可能有相当一部分适合L2或L1缓存，从而加快了访问速度。

或者使用switch语句。

[更新3]

根据开关的情况，编译器会生成表开关或查找开关。查找开关的复杂度为O（log n），并且存储密钥，jmp偏移对，因此不理想。因此，检查组更适合if / else。

tableswitch本身仅使用跳转偏移量表，并且仅需进行减法，比较，访问，jmp即可到达目标，而它必须对常量执行返回值。

因此，表访问看起来更有希望。另外，为避免不必要的跳转，每个组可能包含访问和返回组符号表的逻辑。将所有内容存储在一个大表中是有希望的，因为每个符号可能是int或short，而我的代码通常最多只有1000到4000个符号，这实际上使它很短。

我将检查1-模式是否将使我有机会以更好的方式存储和访问掩码，从而允许二进制搜索正确的组而不是前进O（n），甚至可能在处理期间完全避免任何移位操作。

Answer 1

我无法理解您在（长）问题中写的大部分内容，但是有一个简单的方法。

我们将从一个表开始。假设您最长的霍夫曼代码是15位。 （实际上，deflate将其霍夫曼代码的大小限制为15位。）然后构造一个包含32768个条目的表，其中每个条目是下一个代码中的位数，以及该代码的符号。对于少于15位的代码，同一代码在表中有多个条目。例如。如果符号“ C”的代码是10010110（7位），则表xxxxxxxx10010110的所有索引都相同。这些条目都带有{7，'C'}。

然后，您从流中获得15位，并查找表中的下一个代码。您从该表条目中删除位数，并使用结果符号。现在，您需要从流中获取尽可能多的位，并具有15位，然后重复。因此，如果您使用了7位，则再增加8位回到15，然后查找下一个代码。

下一个微妙之处是，如果您的霍夫曼代码经常更改，那么您可能最终要花更多的时间为每个新的霍夫曼代码填充大表，而不是实际解码。为了避免这种情况，您可以创建一个两级表，该表具有一个用于代码第一部分的9位查找（512个条目）。如果代码为9位或更少，则按上述步骤进行。这将是最常见的情况，因为较短的代码会更频繁（这是霍夫曼编码的重点）。如果表条目表明代码中有10位或更多位（并且您还不知道还有多少位），那么您将消耗前9位，并转到第二级表以查找所指向的前9位按第一个表中的条目，它具有其余六个位的条目（64个条目）。这样可以解决代码的其余部分，从而告诉您要消耗多少位以及什么是符号。这种方法可以极大地减少花费在填充表上的时间，并且由于短代码更为常见，因此速度几乎一样快。这是inflate中zlib使用的方法。