Elias Gamma编码与上界

Question

在阅读关于维基百科上的Elias编码时，我看到它提到：

"Gamma编码用于无法提前知道最大编码值的应用程序。“

而这一点：

“最常用的方法是对上界无法预先确定的整数进行编码。”

我真的不明白这些句子是什么意思，因为每当这个算法被编码时，测试数据的最大值或测试数据的范围就会在掌握之前就知道了。任何帮助都是非常感谢的！

Answer 1

就我所熟悉的Elias-gamma/delta编码而言，第一句简单地指出这些压缩方法是全局的，这意味着它不依赖于输入数据来生成代码。换句话说，这些方法在执行压缩之前不需要处理输入(就像本地方法一样)；它使用一个不依赖于数据库信息的函数对数据进行压缩。

至于第二句，可以作为保证，虽然可能有一些非常大的整数，但编码仍能很好地执行(并以可行的字节数表示这些值，即它是一个普适方法)。注意，如果您知道最大的整数，一些方法(如最小散列)的性能会更好。

最后，您提到的同一页还指出：

伽马编码用于无法提前知道最大编码值的应用程序，或用于压缩数据，其中小值比大值要频繁得多。

这可以通过从原始整数列表生成差异列表来获得，并将这些差异传递给压缩。例如，在数量增加的列表中，可以生成：

list: 1 5 29 32 35 36 37
diff: 1 4 24 3  3  1  1

这将给你更多的小数字，因此一个更大的压缩水平，比第一个列表。