如何计算启动步骤停止编码方案的最佳参数？

Question

启动步骤停止代码是一种数据压缩技术，用于压缩相对较小的数字。

代码的工作原理如下：它有三个参数，start，step和stop。 Start确定用于计算前几个数字的位数。当我们用完时，步骤确定要添加到编码的位数，并且停止确定用于编码数字的最大位数。

因此编码的长度由l = start + step * i。

给出

“i”使用一元编码特定代码的值。也就是说，多个1位后跟一个终止0位。如果我们已经达到停止，那么我们可以丢弃终止0位。如果i为零，我们只写出0位。

所以（1,2,5）启动步骤停止代码的工作原理如下：

值0，编码为：0 0
值1，编码为：0 1
值2，编码为：10 000
值9，编码为：10 111
值10，编码为：11 00000
值41，编码为：11 11111

因此，给定一个包含多个数字的文件，我们如何计算该文件的最佳启动步骤 - 停止代码？最佳参数定义为导致最大压缩比的参数。

Answer 1

这些“开始步骤停止”代码看起来像是一种不同的方式来调用霍夫曼代码。有关计算伪代码的概要，请参阅基本技术。

基本上这就是算法的作用：

在开始霍夫曼编码之前，您需要收集要压缩的每个符号的统计信息（它们在压缩文件中的总频率）。

完成后，使用该信息创建二叉树，以便最频繁使用的符号位于树的顶部（因此使用较少的位），并且没有编码具有前缀代码。因为如果编码具有公共前缀，则可能存在解压缩的歧义。

在Huffman编码结束时，您的起始值将是最浅叶节点的深度，您的步长将始终为1（逻辑上这是有道理的，为什么您会强制超过您需要的位数，只需一次添加一个，）你的停止值将是最深叶节点的深度。

如果频率统计未排序，则需要O（nlog n），如果它们按频率排序，则可以在O（n）中完成。

保证霍夫曼代码具有此类编码的最佳平均压缩率：

  

霍夫曼能够设计得最多   有效的压缩方法   类型：没有其他个人的映射   源符号到唯一的字符串   比特将产生较小的平均值   实际符号时的输出大小   频率与以前的频率一致   创建代码。

这可以帮助您实现问题的理想解决方案。

编辑：虽然相似，但这不是OP所寻求的。

这些代码的创建者提供的学术论文描述了开始 - 停止代码，开始 - 停止代码。然而，作者简要介绍了如何在第2节末尾附近获得最佳启动步骤 - 它包括使用统计随机变量或强力资助最佳组合。在没有任何文件的先验知识的情况下，算法是O（（log n）^ 3）。

希望这有帮助。

Answer 2

我使用的方法是一种简单的蛮力解决方案。该算法遵循以下基本步骤：

1. 计算文件中每个数字的频率。在同一过程中，计算文件中的总数量，并将最大数量确定为maxNumber。

2. 计算每个数字的概率作为其频率除以文件中的总数量。

3. 确定“optimalStop”等于log2（maxNumber）。这是在香农信息理论中应该用来表示maxNumber的理想比特数，因此是对特定数字编码中使用的最佳最大比特数的合理估计。

4. 对于每个“开始”值从1到“最佳停止”重复步骤5 - 7：

5. 对于每个“步骤”值从1到（“optimalStop” - “start”）/ 2，重复步骤6＆amp; 7：

6. 计算“停止”最接近“optimalStop”的值满足stop = start + step * i的某个整数i。

7. 计算此编码将使用的平均位数。这可以通过每个数字的概率乘以给定编码中的比特长度来计算。

8. 选择平均位数最低的编码。