compression - 我没有得到 Golomb/Rice 编码 : It does make more bits of the input, 还是它？

Question

或者，也许，我没有得到的是 unary coding :

在 Golomb, or Rice, coding , 你拆分了一个号码 N将其除以另一个数字 M 分成两部分然后用一元编码该除法的整数结果，用二进制编码余数。

在维基百科 example ，他们使用 42 作为 N和 10 为 M ，所以我们最终得到商 q 4(一元:1110)和余数 r 2(二进制 010)，所以结果消息是 1110,010 , 或 8 位(逗号可以跳过)。 42 的简单二进制表示是 101010 , 或 6 位。

对我来说，这似乎是由于 q 的一元表示它总是必须比二进制多。

显然，我在这里遗漏了一些重要的观点。它是什么？

Answer 1

重要的一点是，哥伦布码并不意味着比一个特定数字的最短二进制编码更短。相反，通过提供特定类型的 variable-length encoding , 他们 与固定宽度编码相比，减少每个编码值的平均长度，如果编码值来自一个大范围，但最常见的值通常很小(因此大多数时间只使用该范围的一小部分)。

例如，如果您要传输 0 到 1000 范围内的整数，但大部分实际值都在 0 到 10 之间的范围内，在固定宽度编码中，大多数传输的代码将具有前导不包含任何信息的 0:

要覆盖 0 到 1000 之间的所有值，您需要使用 10 位宽的固定宽度二进制编码。现在，由于您的大多数值都低于 10，因此大多数数字的前 6 位至少为 0，并且携带的信息很少。

要使用 Golomb 代码纠正此问题，您可以通过将数字除以 10 并分别对商和余数进行编码来拆分数字。对于大多数值，必须传输的只是余数，最多可以使用 4 位进行编码(如果对余数使用截断的二进制，则可以更少)。然后以一元形式传输商，其编码为单个 0小于 10 的所有值的位，如 10对于 10..19，110 20..29 等

现在，对于您的大多数值，您已将消息大小减少到最大 5 位，但您仍然可以在没有分隔符的情况下明确传输所有值。

对于较大的值(例如，范围 990..999 中的值需要 100 位作为商)，这带来了相当高的成本，这就是编码对于 2 边几何分布是最佳的原因。

较大值的商中 1 位的长游程可以通过后续游程长度编码来解决。但是，如果商在结果消息中占用太多空间，这可能表明其他代码可能比 Golomb/Rice 更合适。