我在随机数据压缩方面的冒险
在过去的3个月里，我一直在设计一种压缩随机数据的算法。继续阅读，了解解决这个问题的极端困难，以及为什么我的工作最终会导致我构建一台小型超级计算机来帮助找到解决方案。
现有的压缩算法基于查找数据中的简单模式或降低消息质量。它们不能处理随机数据。这在实践中意味着为了将更多的内容挤入管道(互联网是一系列管道)，YouTube和Netflix等公司降低了内容的质量以弥补这一点。
您只能多次使用此方法，直到内容开始变得太糟糕，让您的客户无法欣赏。明显的缺点是，这种方法会带来损失。您并不喜欢这条消息最初的样子。它被扭曲了以适应你的连接。
随机数据的压缩器会很有用，因为它可以无损地处理所有类型的数据。基本上产生了两个主要的好处：
或者，您可以将其声明为更有效地使用资源…。潜在地允许高速和低速网络上的新用例。随机数据压缩是真正的圣杯。但就像圣杯一样：目前还没有找到实现这一目标的一般方法。
要开始理解为什么这个问题如此困难，看看短短8个字节可以容纳多少信息是很有用的：
仅在8个字节之后，可以容纳的不同组合的数量就在百万万亿范围内。我很清楚，试图使用暴力完全恢复数据的算法在我们的有生之年是永远不会完成的。
通常情况下，这样的观察足以让我远离像压缩熵这样疯狂的尝试。但是有一个引人注目的数据结构改变了我的想法。它被称为Golomb编码集(GCS)，它的作用非常有趣。
GCS是一种概率数据结构，它可以确定项目是否不在集合中，或者项目是否可能在集合中。“可能”部分暗示集合包含但不存在集合排除的误报。
PROB=1024#假阳性率，2CHUNK_SIZE_BITS的幂=17AVG_BLOOM_PORTIALS=(2**CHUNK_SIZE_BITS)*(1.0/PROB)#128。
Golomb编码集是高度可压缩的，因此输出大小小于输入大小。问题是目前还没有已知的方法从给定的集合中复制输入数据。值得注意的是，GCS已经“感觉”是一个可行的解决方案。如果有一种方法可以重建输入数据…就好了。一系列线索。
假设您有1KB的加密随机数据，您想要使用GCS对其进行压缩。将其全部按原样存储将不起作用，因为对于这么长的位串，有太多的潜在组合。相反，数据应该被分成块，并与其块编号一起存储。接下来，您需要为GCS确定正确的参数。
随着假阳性率的降低，GCS的大小增加，用于存储重建输入数据的线索的剩余空间将会减少。如果您决定将假阳性率设置得太低，则要检查的候选对象的数量将变得令人望而却步，并且算法将永远不会完成。
在选择应该有多大的块时也有类似的问题。如果它们太小，那么您最终会在GCS中存储太多散列，并使集合大小膨胀。但是，如果字长太大，那么每一块的候选字数将太大而无法检查，您将无法在以后减少它们。
我发现效果最好的参数是17位块大小，误报率为1024。最小可压缩数据量也受这些参数的影响。较低的误报率会使过滤器更“有效”(精度较低)，因此您可以压缩较少的数据量。我的参数的最小大小是1024字节。
GCS感觉很神奇，但是它们没有给我们太多关于压缩的东西。
以某种方式，方案需要适合小于318字节的范围，以允许从706字节的GCS重构482个随机17位字的序列。我的方法可能与您预期的不同。
首先：每个单词平均将有128个候选单词，在这些候选单词中，原始单词Brute强制每个单词都有可能的候选单词是可行的，因为单词大小只有17位--当今处理器上的单个核心不会花费超过几分钟的时间来构建一个候选单词列表。
在候选列表中，我们的目标单词将有固定的偏移量。偏移量永远不会改变，因为GCS集永远不会改变。挑战是在482个候选列表中的每个列表中找到正确的偏移量。我尝试了许多不同的方法来做到这一点，但它们都失败了。
位过滤器-不起作用，因为有太多误报，它们会用完所有剩余空间。
我本打算在这里放弃，但后来我开始怀疑是否有任何现有的解决方案可能是可比较的(即使只是打个比方)。问题陈述可以写成有一个可能性列表与一个选择列表，并对选择进行歧视。
有一个著名的程序已经做了这个…。但只有一个号码。比特币。我们可以将工作证明设想为使用一个特殊的随机数来区分一个集合，当该集合与该集合组合时，与其他任何事物一起出现的概率极低。
现在就像是在分销中打赌注，然后锁定你想要的候选人。井…。不管怎么说，大致如此。
为了让无名建筑适合剩余的空间，并且仍然产生盈余，需要为它们的建造选择正确的参数。我将介绍以下定义和值：
如果每个单词的唯一候选列表中都有固定的偏移量，则将此偏移量称为节点。
使用这种方法，可以将每个集合的几十亿个组合减少到小于或等于1。我认为对于一个4字节的鉴别器…来说，这是非常有效的。我们现在只剩下77个字节了。
我用来生成随机数的代码与标准的hashash没有太大不同。主要不同之处在于，我散列了一系列散列，对任何零前缀位的复杂度进行了合计，并根据总体复杂度进行了排序。如果复杂度太低，则现时值不足以区分边缘散列，我会将其丢弃。结尾处的GitHub链接。
注意：我已经在这里给出了过滤集合的计算-它们相当冗长，而且首先还有其他要点需要讨论。
候选名单的长度必须由暴力强迫GCS决定。从那里可以构造每个可能的边缘散列，并将其复杂性与随机数线索进行比较。
CHKSUM_BITS=1AVG_BLOOM_PERIACTIONS=AVG_BLOOM_PERIACTIONS*(1/(2**CHKSUM_BITS))AVG_EDGE_CADERATES=AVG_BLOOM_PERCENTIONS**2#4096AVG_SET_CADERATES=AVG_EDGE_CADERATES**4281474976710656。
尝试每一种可能的边缘散列都有超过1万亿的组合。因为这超过了随机数拼图的整个搜索空间(2**32)，所以它最终会找到比我们的边缘散列集“更好”的候选者，从而使拼图变得毫无意义。
有一些方法可以极大地减少检查的可能性。因为我们要对一个序列进行POW，所以我们知道在某些边缘散列中“好的”随机数所期望的前缀位的数量。这样的信息可以形成基本过滤器的启发式-以少于40分钟(168个核)的总搜索时间从1000+亿个候选中剔除。
您可能注意到的另一件事是，在删除剩余的所有字节之后，我最终添加了一个位过滤器-=(482/8)==60，用于剩余的17个字节。我现在要问的问题是：在将线索过滤器应用于边缘散列候选之后，什么样的启发式组合将使我们能够将设置的偏移量存储在剩余空间中？
现在阻止我回答这个问题的障碍是速度。我的代码需要访问通用CPU计算集群。我把家里的每台笔记本电脑和台式机都连接起来，组成了一个168节点的PySpark集群。这包括谷歌云…上的64个核心节点。我仍然需要几天时间来对所有结果集进行计算。
到目前为止，我已经成功地恢复了一组(在几分钟内分割了1000多亿个组合！)。但我认为，如果不能访问更多的计算资源，我将不会继续这方面的工作。现在，我将发布我当前的代码，并给您留下一些对我当前工作的明显改进。
该算法记录了符合特定标准的最佳谜题。平均而言，这需要尝试大量随机数才能找到解决方案。我发现很容易根据它们的大小来压缩它们，它们都同样大，并且在相同的范围内：
存储1字节字段：4位描述r_b大小，4位描述q_b大小。
我每次可以节省14位，总共节省了106字节。如果调整方案以避免以前使用位串(可能通过在运行时进行权衡)-那么它将额外增加60个字节。或剩余183个字节。假设每个偏移量约15位，这应该足以表示线索过滤阶段中的偏移量。
我认为，有了更多的计算能力(所以我不会等上几天来做我的实验)，我就可以做到这一点。不过，在这件事上我很有可能是错的。现在，以下是我当前的原型代码。它非常混乱，但展示了我的整体概念：