math - 创建一个有效的函数来拟合数据集

Question

基本上我有一个大的（可以得到多达 100,000-150,000 个值）4 字节输入及其相应的 4 字节输出的数据集。不能保证输入是唯一的（这不是真正的问题，因为我认为我可以生成伪随机数来添加或异或输入，以便它们变得唯一），但不能保证输出也是唯一的（因此两组不同的输入可能具有相同的输出）。

我正在尝试创建一个函数来有效地模拟我的数据集中的值。我不需要它来有效地插值，甚至根本不需要它（我的意思是我永远不会向它提供不包含在这个静态数据集中的输入）。但是，它确实需要尽可能高效。我研究了插值，发现它并不真正适合我正在寻找的东西。例如，大量值意味着样条插值不起作用，因为它会为每个间隔创建一个多项式。

此外，根据我的理解，多项式插值在计算上过于昂贵（n 值意味着多项式可以包含高达 pow(x,n-1) 的项。对于 x= 4 字节数和 n=100,000 它只是不是可行的）。我已经尝试在网上寻找一段时间了，但我的数学不是很强大，而且我一定不知道要搜索的正确术语，因为到目前为止我还没有遇到过类似的东西。

我可以看到这并不完全（委婉地说）一个编程问题，我提前道歉。我不是在寻找确切的解决方案，甚至不是完整的答案。我只需要关于我需要阅读的主题的指针，这样我就可以自己解决这个问题。谢谢！

TL;DR - 我需要一种插值变体，它只需要适合最初给定的数据点，但计算效率很高。

编辑：一些澄清 - 我确实需要输出准确而不是近似值。这是对我目前正在做的一些研究工作的一种优化，我需要在没有输出的实际字节出现在我的程序中的情况下实现这个查找。目前我真的不能说太多，但我会说，就我的工作而言，加密（或压缩或任何其他形式的混淆）不是隐藏表格的选项。我需要一个数学函数，只要它可以访问输入，它就可以重新创建输出。我希望这能把事情弄清楚一点。

Answer 1

由于您没有对函数施加任何限制（连续、平滑等），您可以简单地进行分段常数插值：

或线性插值：

我假设您可以轻松地弄清楚如何构造这样的函数。

编辑：鉴于您的附加要求，即此类功能应“隐藏”数据点...

对于分段常数插值，常数间隔应该是随机的，以便不显示数据点的位置。因此，例如在图片中，间隔以它插值的数据点为中心。相反，您可能想要执行以下操作：

[0 , 0.3) -> 0
[0.3 , 1.9) -> 0.8
[1.9 , 2.1) -> 0.9
[2.1 , 3.5) -> 0.2
etc

当然，这只隐藏了 x 坐标。要同时隐藏 y 坐标，您可以使用线性插值。

只需使其“尖”部分不在数据点所在的位置。选择随机 x 值，使得每个相邻数据点之间都有这些 x 值之一。然后进行插值，使“尖”部分位于这些 x 值处。

Answer 2

这是一个想法。使您的函数成为所有 4 字节整数的线性函数的总和 (mod 2 ³² )，一个分段线性函数，其片段取决于第一位的值，另一个分段线性函数，其片段取决于第一个位的值两位，以此类推。

实际输出值无处出现，您必须将线性项相加才能得到它们。也没有直接记录您拥有哪些输入值。（有人可以对这些输入值得出一些结论，但不能得出它们的实际值。）

您需要的各种系数可以存储在哈希中。您执行的任何未在散列中找到的查找都假定为 0。

如果您在开始相当有效地编码之前向数据集添加一定数量的随机“噪声”，则很难判断您的输入值是什么，甚至在不知道输入的情况下也很难判断输出是什么。

Answer 3

我建议使用一个包含未使用条目的巨大查找表。这是蛮力方法，有一个有序的输出表，按输入的每个可能值排序（不仅是数据集，还有所有其他可能的 4 字节值）。

尽管您的所有数据都在那里，但您可以用随机、任意或随机（在可能复杂的约束条件下随机）数据填充未使用的输入。如果你让它令人信服，那么没有人可以从中挑选出你的真实数据。如果一个“真实”函数插入了您的所有数据，它还将“包含”您的真实数据的所有信息，任何有权访问它的人都可以使用它来生成如上所述的 LUT。

LUT 速度快如闪电，但非常消耗内存。您的案例处于可行性边缘，需要 (2^32)*32= 16 GB 的 RAM，这需要 64 位机器才能运行。这仅适用于数据，而不适用于程序、操作系统或其他数据。最好有 24 个，只是为了确定。如果你能负担得起，他们就是你要走的路。