Java 源代码生成中的 Huffman 代码解码器编码器
Huffman Code Decoder Encoder In Java Source Generation
我想在 Java 中创建一个快速的霍夫曼码解码器，因此考虑了查找 tables。由于那些 table 会消耗内存，而我们使用 Java 代码来导航和访问 table，因此可以轻松（或不）编写一个程序/方法来表达相同的 table.
这种方法的问题是，我不知道什么是最好的策略。我知道很多关于适合缓存和分支预测的内容。 switch case 实现也意味着实际的 ASM 超出了我的范围。如果我有一个内存查找 table（或它的层次结构），我将能够简单地跳入和跳出，但我怀疑 table 适合缓存。
因为我实际上是在遍历一棵树，所以可以将其实现为 if else 语句，需要一定数量的比较，但对于每个比较，它都需要额外的二元运算。
因此存在以下选项：
- 在内存查找中使用的通用算法 tables
- If/else 决策树的表示
- If/else 用小的 switch 语句表示以找到正确的符号组（相同的位模式长度）（更少的 if 语句，可能是更多的代码）。
- 代码的switch语句表示
编写和基准测试非常棘手，所以任何初步想法都会很棒。
另外一个问题是位的顺序。最高有效位总是在前，这意味着它以相反的顺序存储。
If your tree is A = 0, B = 10, C = 11 to write BAC it would actually be 01 + 0 + 11 (plus means append).
所以实际上代码必须倒序编写。对组使用 if /else 或 switch 方法不会有问题，因为屏蔽位很简单，并且位的反转很简单，但它会失去从掩码中获取组内索引的想法，因为反向位顺序添加和删除具有不同的含义，并且不可能进行简单的查找。
反转位是一项代价高昂的操作（我使用 4 位查找 tables）不超过二进制操作的性能损失。
但是在移动中反转位更适合于此，并且每位需要四次操作（向上移动、屏蔽掉、添加以及向下移动输入）。由于我提前读取位，所有这些操作都将在寄存器中完成，因此它们可能只需要几个周期。
这样我就可以使用 switch、sub 和 if 来找到正确的符号组以及 return 那些。
所以最后我需要建议。由于我的代码是语言处理的全局代码，它们可以是硬连线的（即在源代码中）。
我想知道像 ANTRL 这样的解析器生成器使用什么来表达这些决定。由于它们还根据输入符号接缝切换或if/else，这可能会给我一个线索。
[更新]
我发现了一种可以避免反向位问题但仍会增加每组成本的简化方法。所以我最终按照要遍历的组的顺序编写了这些位。所以我不需要对每个位进行四次修改，而是对每个组进行四次修改（不同的位长度）。
对于每个组，我们有：
1. 第一个元素的值，大小（因此也是该组中最后一个元素的值。
因此，对于每个组，算法如下所示：
1. 读取mbits 并结合当前读取值。
2. 将该值与该组的最后一个值进行比较，如果不是它的外部，它是否在该组内更小。 -> 继续阅读
3. 如果它在组内，则可以访问值数组或使用 switch 语句。
这是完全通用的，可以在没有循环的情况下使用，从而提高效率。此外，如果检测到该组，则代码的位长度是已知的，并且可以从源中使用这些位，因为代码看起来很远（从流中读取）。
[更新 2]
要访问实际值，可以使用按组分组的单个大型元素数组。由于组与组之间的概率降低，很可能很大一部分适合 L2 或 L1 缓存，从而加快了此处的访问速度。
或者使用 switch 语句。
[更新 3]
根据开关的情况，编译器生成 table开关或查找开关。查找开关的复杂度为 O(log n) 并存储键、jmp 偏移对，这是不可取的。因此，检查组更适合 if/else。
tableswitch 本身仅使用 table 的跳转偏移量，它只需要 substract、compare、access、jmp 即可到达目的地，而不是它必须执行 return常数值。
因此 table 访问看起来更有希望。此外，为了避免不必要的跳转，每个组可能包含访问逻辑和 return 组符号 table。将所有内容存储在一个大 table 中是有希望的，因为每个符号可能是 int 或 short，而我的代码通常最多只有 1000 到 4000 个符号，因此实际上很短。
我会检查 1 - 模式是否能让我有机会以更好的方式存储和访问掩码，从而允许二进制搜索正确的组而不是在 O(n) 中前进，甚至可能避免任何移位操作全部在处理中。
我无法理解你在（长）问题中写的大部分内容，但有一个简单的方法。
我们将从一个 table 开始。假设您最长的霍夫曼码是 15 位。 （实际上，deflate 将其霍夫曼代码的大小限制为 15 位。）然后构造一个具有 32768 个条目的 table，其中每个条目是下一个代码中的位数，以及该代码的符号。对于少于 15 位的代码，同一代码在 table 中有多个条目。例如。如果符号 'C' 的代码是 10010110（7 位），那么 table xxxxxxxx10010110 的所有索引都具有相同的内容。这些条目都有 {7, 'C'}.
然后从流中得到15位，在table中查找下一个代码。您从 table 条目中删除位数，并使用生成的符号。现在您从流中获得了 15 位所需的位，然后重复。所以如果你使用了 7 位，那么再得到 8 位就可以回到 15 位并查找下一个代码。
下一个微妙之处是，如果您的霍夫曼代码经常更改，您最终可能会花费比实际解码更多的时间来为每个新的霍夫曼代码填充那么大 table。为避免这种情况，您可以创建一个两级 table，例如，对代码的第一部分进行 9 位查找（512 个条目）。如果代码是 9 位或更少，则按上述方式进行。这将是最常见的情况，因为较短的代码更频繁（这就是霍夫曼编码的全部意义）。如果 table 条目表示代码中有 10 位或更多位（而您还不知道还有多少位），那么您将使用前九位并转到第二级 table 对于第一个 table 中的条目指向的那些初始九位，它具有剩余六位（64 个条目）的条目。这解决了代码的其余部分，因此告诉您要消耗多少位以及符号是什么。这种方法可以大大减少填充 table 所花费的时间，并且速度非常快，因为短代码更常见。这是 inflate in zlib.
使用的方法
最后很简单。我现在支持几乎所有的解决方案。可以测试每个符号组（相同的位长度），使用查找 table（10 位 + 10 位 + 10 位（仅 tables of 10bit，symbolscount + 1 是对这些表格的引用））并生成java（如果需要 javascript 但目前我使用 GWT 来翻译它）。
我什至使用长读取和移位操作来减少对二进制信息的访问。这样代码会变得更有效率，因为我只支持最大位大小（20 位（所以 table 的 table），这使得 2^20 个符号，因此最多一百万个）。
对于排序，我使用位掩码生成器，仅使用移位操作，不需要反转位顺序等。
table 查找也可以用 Java 表示，将 table 存储为数组的数组（有趣的是 java 文件在没有编译器的情况下可以有多大抱怨)).
我还发现有趣的是，由于比较是在表达一种排序（我猜是半阶），因此可以对符号进行排序，而不是映射映射比较索引的符号。通过比较两个索引，可以简单地对代码流进行排序，而无需太多接触。通过还存储第一个或前两个比较索引（16 位或 32 位），可以使用相同的霍夫曼代码对压缩字符串进行有效排序，从而对压缩字符串进行二进制排序，这使得它非常适合以某种语言压缩字符串。
我想在 Java 中创建一个快速的霍夫曼码解码器，因此考虑了查找 tables。由于那些 table 会消耗内存，而我们使用 Java 代码来导航和访问 table，因此可以轻松（或不）编写一个程序/方法来表达相同的 table.
这种方法的问题是，我不知道什么是最好的策略。我知道很多关于适合缓存和分支预测的内容。 switch case 实现也意味着实际的 ASM 超出了我的范围。如果我有一个内存查找 table（或它的层次结构），我将能够简单地跳入和跳出，但我怀疑 table 适合缓存。
因为我实际上是在遍历一棵树，所以可以将其实现为 if else 语句，需要一定数量的比较，但对于每个比较，它都需要额外的二元运算。
因此存在以下选项：
- 在内存查找中使用的通用算法 tables
- If/else 决策树的表示
- If/else 用小的 switch 语句表示以找到正确的符号组（相同的位模式长度）（更少的 if 语句，可能是更多的代码）。
- 代码的switch语句表示
编写和基准测试非常棘手，所以任何初步想法都会很棒。
另外一个问题是位的顺序。最高有效位总是在前，这意味着它以相反的顺序存储。
If your tree is A = 0, B = 10, C = 11 to write BAC it would actually be 01 + 0 + 11 (plus means append).
所以实际上代码必须倒序编写。对组使用 if /else 或 switch 方法不会有问题，因为屏蔽位很简单，并且位的反转很简单，但它会失去从掩码中获取组内索引的想法，因为反向位顺序添加和删除具有不同的含义，并且不可能进行简单的查找。
反转位是一项代价高昂的操作（我使用 4 位查找 tables）不超过二进制操作的性能损失。
但是在移动中反转位更适合于此，并且每位需要四次操作（向上移动、屏蔽掉、添加以及向下移动输入）。由于我提前读取位，所有这些操作都将在寄存器中完成，因此它们可能只需要几个周期。
这样我就可以使用 switch、sub 和 if 来找到正确的符号组以及 return 那些。
所以最后我需要建议。由于我的代码是语言处理的全局代码，它们可以是硬连线的（即在源代码中）。
我想知道像 ANTRL 这样的解析器生成器使用什么来表达这些决定。由于它们还根据输入符号接缝切换或if/else，这可能会给我一个线索。
[更新]
我发现了一种可以避免反向位问题但仍会增加每组成本的简化方法。所以我最终按照要遍历的组的顺序编写了这些位。所以我不需要对每个位进行四次修改，而是对每个组进行四次修改（不同的位长度）。
对于每个组，我们有： 1. 第一个元素的值，大小（因此也是该组中最后一个元素的值。
因此，对于每个组，算法如下所示： 1. 读取mbits 并结合当前读取值。 2. 将该值与该组的最后一个值进行比较，如果不是它的外部，它是否在该组内更小。 -> 继续阅读 3. 如果它在组内，则可以访问值数组或使用 switch 语句。
这是完全通用的，可以在没有循环的情况下使用，从而提高效率。此外，如果检测到该组，则代码的位长度是已知的，并且可以从源中使用这些位，因为代码看起来很远（从流中读取）。
[更新 2]
要访问实际值，可以使用按组分组的单个大型元素数组。由于组与组之间的概率降低，很可能很大一部分适合 L2 或 L1 缓存，从而加快了此处的访问速度。
或者使用 switch 语句。
[更新 3]
根据开关的情况，编译器生成 table开关或查找开关。查找开关的复杂度为 O(log n) 并存储键、jmp 偏移对，这是不可取的。因此，检查组更适合 if/else。
tableswitch 本身仅使用 table 的跳转偏移量，它只需要 substract、compare、access、jmp 即可到达目的地，而不是它必须执行 return常数值。
因此 table 访问看起来更有希望。此外，为了避免不必要的跳转，每个组可能包含访问逻辑和 return 组符号 table。将所有内容存储在一个大 table 中是有希望的，因为每个符号可能是 int 或 short，而我的代码通常最多只有 1000 到 4000 个符号，因此实际上很短。
我会检查 1 - 模式是否能让我有机会以更好的方式存储和访问掩码，从而允许二进制搜索正确的组而不是在 O(n) 中前进，甚至可能避免任何移位操作全部在处理中。
我无法理解你在（长）问题中写的大部分内容，但有一个简单的方法。
我们将从一个 table 开始。假设您最长的霍夫曼码是 15 位。 （实际上，deflate 将其霍夫曼代码的大小限制为 15 位。）然后构造一个具有 32768 个条目的 table，其中每个条目是下一个代码中的位数，以及该代码的符号。对于少于 15 位的代码，同一代码在 table 中有多个条目。例如。如果符号 'C' 的代码是 10010110（7 位），那么 table xxxxxxxx10010110 的所有索引都具有相同的内容。这些条目都有 {7, 'C'}.
然后从流中得到15位，在table中查找下一个代码。您从 table 条目中删除位数，并使用生成的符号。现在您从流中获得了 15 位所需的位，然后重复。所以如果你使用了 7 位，那么再得到 8 位就可以回到 15 位并查找下一个代码。
下一个微妙之处是，如果您的霍夫曼代码经常更改，您最终可能会花费比实际解码更多的时间来为每个新的霍夫曼代码填充那么大 table。为避免这种情况，您可以创建一个两级 table，例如，对代码的第一部分进行 9 位查找（512 个条目）。如果代码是 9 位或更少，则按上述方式进行。这将是最常见的情况，因为较短的代码更频繁（这就是霍夫曼编码的全部意义）。如果 table 条目表示代码中有 10 位或更多位（而您还不知道还有多少位），那么您将使用前九位并转到第二级 table 对于第一个 table 中的条目指向的那些初始九位，它具有剩余六位（64 个条目）的条目。这解决了代码的其余部分，因此告诉您要消耗多少位以及符号是什么。这种方法可以大大减少填充 table 所花费的时间，并且速度非常快，因为短代码更常见。这是 inflate in zlib.
使用的方法最后很简单。我现在支持几乎所有的解决方案。可以测试每个符号组（相同的位长度），使用查找 table（10 位 + 10 位 + 10 位（仅 tables of 10bit，symbolscount + 1 是对这些表格的引用））并生成java（如果需要 javascript 但目前我使用 GWT 来翻译它）。
我什至使用长读取和移位操作来减少对二进制信息的访问。这样代码会变得更有效率，因为我只支持最大位大小（20 位（所以 table 的 table），这使得 2^20 个符号，因此最多一百万个）。
对于排序，我使用位掩码生成器，仅使用移位操作，不需要反转位顺序等。
table 查找也可以用 Java 表示，将 table 存储为数组的数组（有趣的是 java 文件在没有编译器的情况下可以有多大抱怨)).
我还发现有趣的是，由于比较是在表达一种排序（我猜是半阶），因此可以对符号进行排序，而不是映射映射比较索引的符号。通过比较两个索引，可以简单地对代码流进行排序，而无需太多接触。通过还存储第一个或前两个比较索引（16 位或 32 位），可以使用相同的霍夫曼代码对压缩字符串进行有效排序，从而对压缩字符串进行二进制排序，这使得它非常适合以某种语言压缩字符串。