algorithm - 逆霍夫曼编码

Question

假设我有一个带有预定义二进制前缀代码的单词集合给定一个非常大的随机二进制数据块，我可以使用前缀代码将该块解析为单词。
我想确定，至少对于每一个单词的点击数的期望值（大约是非常大的长度的随机块）（在解码文本中提到了多少次）。
乍一看，这个问题似乎微不足道——从随机位池扫描每个字的概率完全由其长度决定（因为每个位可以是0或1）。但我怀疑这是对上述问题的错误回答，因为单词的长度不同，因此这种可能性与预期的命中次数（除以数据块的长度）不同。
UPD：我被要求（在下面的评论中）用数学的方法来陈述这个问题，所以就这样。
让我们列出一个只有0和1的单词（我们的字母表只有两个字母）此外，w中没有任何单词是任何其他单词的前缀。因此w形成合法的二进制前缀码。我想知道（至少大约是）命中的平均值，对于w中的每个单词，在所有可能的固定大小的二进制数据块上的平均值都可以非常大，比我们的单词长度要大得多。然而，词的长度不同，这一点不容忽视。
如果你能提及解决这个问题的方法，我将不胜感激。

Answer 1

我的简短回答是：可以为每个给定的单词列表计算预期的点击次数（或者更确切地说，预期的点击比例）。
我将不描述完整的算法，而只是做下面的例子详细说明：让我们修复以下三个单词的非常简单的列表：0，10，11。
对于每一个n，都有不同长度的2^n数据块（我的意思是n位），每个数据块以相同的概率出现。
第一个观察是，并不是所有的数据块都能被精确解码-例如，数据n，当你解码时，最终会有一个2^(-n)。
让我们为能被正确解码的长度0101数据块的数量写1，为其他数据块（即最后有额外U(n)的数据块）写n。以下重复关系很清楚：
V(n)
1
初始值U(n) + V(n) = 2^n=1和V(n) = U(n - 1).
一个简单的计算得出：
U(0)。
现在让我们（分别V(0) = 0，U(n) = (2^(n + 1) + (- 1)^n) / 3）是单词的点击数之和（分别为A(n)，B(n)）用于所有精确的数据块，并让C(n)（分别0，10）是所有不精确数据块的相同和（在这种情况下，最后一个11不计算在内）。
那么我们有以下关系：
U(n)，a(n)，b(n)
c(n)
V(n)
1
对关系的解释2 3 4：
如果a(n) = A(n - 1)是长度为b(n) = B(n - 1)的精确数据块，则有三种可能：
c(n) = C(n - 1)以A(n) = A(n - 1) + U(n - 1) + A(n - 2) + A(n - 2)结尾，删除此B(n) = B(n - 1) + B(n - 2) + U(n - 2) + B(n - 2)将生成长度为C(n) = C(n - 1) + C(n - 2) + C(n - 2) + U(n - 2)的精确数据块；
D以n结尾，删除此D将生成长度为0的精确数据块；
0以n - 1结尾，删除此D将生成长度为10的精确数据块。
因此，例如，当我们将所有长度为10的精确数据块中n - 2的所有命中数相加时，这三种情况的贡献分别为D、11、11。其他两个平局也一样。
现在，求解这些递推关系，我们得到：
n - 2
0
自从n后，我们的结论是，在A(n - 1) + U(n - 1)，A(n - 2)命中A(n - 2)，A(n) = 2/9 * n * 2^n + (smaller terms)命中B(n) = C(n) = 1/9 * n * 2^n + (smaller terms)。
注意，如果我们也考虑到不精确的数据块，同样的比例也适用，因为U(n) = 2/3 * 2^n + (smaller terms)，n/3，0，n/6和10，n/6，11，V(n)之间的关系。
这种方法可推广到任何单词表。这与使用动态编程-创建状态、查找递归关系和建立转换矩阵来解决此问题的思路相同。
更进一步
我认为下面的说法也可能是正确的，这将进一步简化答案。
让A(n)，…，B(n)作为列表中的单词，让C(n)，…，U(n)作为它们的长度。
对于每个a(n)，设b(n)为c(n)的命中率，即对于长度V(n)的数据块，w_1的预期命中数为w_k。
然后，我的感觉（推测）是l_1对所有l_k都是一样的，即如果一个单词比另一个单词长一点，那么它的命中率是另一个单词的一半。
这一猜想如果正确的话，可能不太难证明。但我现在懒得想…
如果这是真的，那么我们可以很容易地计算出那些i = 1, ..., k，因为我们有一个恒等式：
a_i。
让我用上面的例子来说明这一点。
我们有w_i，n，w_i，因此有a_i * n + (smaller terms)，a_i * 2^(l_i)。
根据推测，我们应该有i。因此a_i和sum (a_i * l_i) = 1上述等式变成：
w_1 = 0
因此，w_2 = 10，我们得到了w_3 = 11，l_1 = 1，这可以通过上述计算得到验证。