3

我真的不知道这个问题的名称是什么，但它有点像有损压缩，我的英语不好，但我会尽可能多地描述它。

假设我有来自未知来源的未排序唯一数字列表，长度通常在 255 到 512 之间，范围从 0 到 512。
我想知道是否有某种算法可以读取数据并返回类似种子号的东西我可以用它来生成一个接近原始但有一定程度错误的列表。

例如

  • 原始清单

    {5, 13, 25, 33, 3, 10}

  • 重新生成的列表

    {4, 10, 30, 30, 5, 5} or {8, 20, 20, 35, 5, 9} //and so on

这个问题有名字吗，有没有可以做我刚才描述的算法？它是否与蒙特卡洛方法
相同，因为据我了解它不是。

是否可以使用有损压缩中使用的一些技术来获得这种近似值？

我试图解决这个问题的方法是使用一个简单的 16 位 RNG 并蛮力将所有可​​能的值与原始列表进行比较，然后选择差异最小的那个，但我认为这种方式相当愚蠢且效率低下.

4

1 回答 1

2

这确实是有损压缩。

您没有告诉我们列表中值的范围。从您提供的样本中，我们可以推断它们每个至少计算 6 位（0 到 63）。总共有 0 到 3072 位要压缩。

如果这些序列没有特殊属性并且看起来是随机的，我怀疑是否有任何方法可以实现显着压缩。认为从 32 位种子中匹配任意序列的概率为 2^32.2^(-3072)=7.10^(-916)，即小于无穷小。如果您允许每个值有 10% 的误差，则匹配的概率为 2^32.0.1^512=4.10^(-503)。

以 12.5% 的精度进行压缩的一种简单方法是去掉每个值的三个 LSB，从而节省 50%（1536 位），但我怀疑这就是您要寻找的。

将有助于测量序列http://en.wikipedia.org/wiki/Entropy_(information_theory)的熵和/或值之间可能的相关性。这可以通过绘制所有 (V, Vi+1) 对或 (Vi, Vi+1, Vi+2) 三元组并寻找模式来完成。

于 2014-05-10T10:47:19.703 回答