optimization - 如何计算开始-步骤-停止编码方案的最佳参数？

Question

start-step-stop 码是一种数据压缩技术，用于压缩相对较小的数字。

该代码的工作原理如下:它具有三个参数，start、step 和 stop。 Start 确定用于计算前几个数字的位数。 Step 确定当我们用完时要添加多少位到编码中并停止确定用于对数字进行编码的最大位数。

因此，编码的长度由 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 codes .见basic technique用于计算它们的伪代码的概要。

本质上，这就是算法的作用:

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

之后，您创建一个 binary tree使用该信息，使最常用的符号位于树的顶部(因此使用较少的位)，并且没有编码具有 prefix code .因为如果编码具有公共(public)前缀，则解压缩可能会产生歧义。

在霍夫曼编码结束时，您的起始值将是最浅叶节点的深度，您的步长将始终为 1(从逻辑上讲，这是有道理的，为什么要强制比您需要的更多位，一次只添加一个，)和您的停止值将是最深叶节点的深度。

如果频率统计数据未排序，则需要 O(nlog n) 来完成，如果它们按频率排序，则可以在 O(n) 中完成。

对于这种类型的编码，霍夫曼编码保证具有最佳的平均压缩率:

Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code.

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

编辑:虽然相似，但这不是 OP 想要的。

这个 academic paper由这些代码的创建者描述了一个概括的开始-步骤-停止代码，开始-停止代码。然而，作者在第 2 节末尾简要描述了如何获得最佳开始-步骤-停止。它涉及使用统计随机变量，或暴力资助最佳组合。在没有任何文件先验知识的情况下，算法为 O((log n)^3)。

希望这可以帮助。