algorithm - 类似于反向随机数生成器的东西

Question

我真的不知道这个问题的名称是什么，但它是有损压缩之类的东西，我的英语不好，但我会尽量描述它。

假设我有来自未知来源的未排序唯一数字列表，长度通常在 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
  

这个问题有名字吗？是否有算法可以完成我刚才描述的事情？
它是否与 Monte Carlo 方法 相同，因为据我了解它不是。

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

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

Answer 1

这确实是有损压缩。

您没有告诉我们列表中值的范围。从您提供的样本中，我们可以推断出它们每个至少计数 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) 三元组并寻找模式来完成。