最近，一款5个字母的文字游戏非常流行。浏览一下源代码，就可以看到实现允许猜测字典和答案列表的一个有趣的选择。
秘密单词的列表就在代码中，这个单词是根据用户的本地日期选择的。
第一点很聪明。这意味着他们不需要每天更新后端（或者后端有逻辑），它会在午夜为每个用户自动切换，而不是根据服务器的午夜随机切换。
另外两个让我吃惊。我希望至少有一些简单的特定领域的压缩。此外，我希望答案列表只是字典中的指针，而不是单独的列表（每次提交单词时都需要验证代码检查两个列表）。
我想我将如何实现这一点，并从那里开始思考如何优化它。一篇关于将字典压缩到适合一个游戏机的帖子，然后火上浇油，最终我崩溃了。我花了一天的时间尝试不同的事情，以下是我的发现。支持这项研究的所有代码都是开源的，可以在这里查看。
注意：对于这个分析，我使用的是原始单词的档案。随着时间的推移，字典和答案都发生了变化。我认为任何改变都不会对这一分析产生太大影响。对于所有的通用压缩，我使用的是zstd，因为它是一个非常高质量的压缩机。
我的要求很简单。我将假设一个浏览器目标，我将看看如何最好地在那里获取数据。我将假设我可以发送二进制数据，并且我还将估计解码器的大小，以确保我不只是将数据移动到解码器中。然而，在实践中，这不是我的任何解决方案的问题。
由于WASM开销和Rust错误处理开销，测量代码大小非常困难。为了对此进行规范化，我将采用最小实现的代码大小（位图为1347） B） 并减去在没有恐慌可能性的情况下实施时的大小差异（234 B） 。这意味着本文中看到的代码大小将比实际压缩大小小1113b。这应该大致说明基础设施的开销。我认为这是有意义的，因为除非您在WASM中只实现这一个函数，否则您将不得不支付这一成本，而且这并没有存储任何特定于域的数据。我也不想用“不安全”来实现每一个，以避免切片边界检查带来的恐慌。这不是很科学，主要是确保没有实现会导致巨大的代码量。
我还想确保编码对于交互使用是可行的。我的目标是50 女士在100号房间里留了很多空间 ms是其他工作的门槛。实际上，对于我的任何解决方案来说，这都不是一个数量级的问题。本文中的所有时间都是通过计算平均时间，在AMD5950X上以随机顺序检查所有可能的有效或无效单词。这并不特别科学，因为分支预测器将很快学会总是说是或否，并且计时只运行了一次，但由于我目前还没有达到时间要求，这似乎并不重要。
首先，让我们看看最简单的选项是如何工作的。这场比赛有12场 字典里有972个单词，2315个答案，10个单词 657个可猜单词。在游戏中，这些是JSON编码在两个单独的列表中。让我们看看这些有多大。对于“两者”，我采用了最好的情况，即简单地将它们连接起来，而不是在它们之间换行。
说实话。不到25 如今，应用程序数据的KiB已经不多了。但让我们看看我们能做得多好。
首先，让我们试着把单词放在一个列表中。这应该允许更好的压缩，因为所有单词都是按顺序排列的，而不是答案的随机顺序。（请注意，答案仅限于⅓ 而完整的字典压缩到几乎⅕. 我认为这其中很大一部分是不可预测的顺序。）然而，与此同时，我也放弃了JSON编码。我只是把所有5个字母的单词连在一起。这为我节省了三个字符（"；，"；）在每一个属于⅜ 节省（尽管这些字符可能压缩得很好）。
至于查找，我正在进行二进制搜索。没有必要达到我的性能目标，但可以显著加快我的全面测试。另外，增加的代码大小很小。
虽然我们的尺寸因删除JSON而显著下降，但压缩效果变差，最终节省了不到2%。如果每个答案增加2个字节以重新获得答案列表，则基本上是收支平衡。
注意：一个有趣的优化是限制答案的选择，这样你就不用2个字节来选择任意答案，只需要1个字节（甚至更少）。设计一个人类无法轻易利用的方案来偏向他们的选择，尽管它会使一些答案变得不可能，这应该是相当容易的。
第一件显而易见的事情是，所有的单词都只使用a-z范围内的字母。我们不需要每个字符花费一个完整字节。我们只需要log_2（26）=每个字符4.7位，或每个字23.5位。我将忽略半位，使用24位，或每个字3字节。
逻辑很简单。不存储单词本身，而是将单词索引存储在可能的单词列表中。例如aaaaa是0，zzzzz是26^5-1。代码如下：
fn索引（单词：[u8；5]）->；u32{let mut i:u32=0；对于单词{debug#u assert！（b'；a'；.=b'；z'；）中的c。包含（&；c））；i*=26；i+=（c-b'；a'；）如u32；}i}
我们得到了⅗ 我们期待的尺寸差异，但是zstd完全没有找到任何图案！压缩的大小实际上比以前大，在默认的zstd设置下，它根本不压缩。这是令人惊讶的，因为通常每个单词的开头都有3个字节的重复，但我猜zstd没有注意到这一点。gzip也在挣扎，但佐夫利确实设法将其压缩到34.314 基布。仍然比让压缩器直接看到ASCII码要大得多。
我们可以使用索引中的前2个字符，并将剩余的3个字符压缩成2个字节，而不是将每个单词存储在3个字节中。这样每个字可以节省1字节，但会占用索引空间。
幸运的是，最常见的两个字母前缀“co”只有220个单词，这意味着我们在索引中每个前缀只需要一个字节，或者26^2=676字节。
这比以前小得多，加上压缩似乎找到了更多的模式，但速度明显较慢。有两个主要原因。
我们把索引中的值加起来。这对空间有利，但对速度不利。这可以通过一个预处理过程来解决，以便在进行查找之前解析报价。
我没有费心对这些值进行二进制搜索。我不认为这对最多220个条目有帮助，但也许会有帮助。
如果不是存储索引，而是为每个可能的单词存储一位呢。如果是允许的单词，则为1，否则为0。这将需要26^5位，并应提供非常快速的查找。
我们可以使用相同的逻辑将单词转换为索引，然后只需检查表中的该位。
这种方法速度非常快，如果你在服务器上托管数据，这是一个很好的选择。通用压缩也做了一个伟大的工作，使这个选项相当小的电线。
另一种选择是，我们不存储单词，只存储前一个单词的更改。这样做的好处是，在排序列表中，第一个字符几乎总是相同的，第二个字符通常是相同的，依此类推。我决定这样做的方式是将差异存储在索引中。这很有效，因为我们可以列举可能的单词。其他选项包括计数不匹配的字符数，然后是替换字符。
不幸的是，单词之间的距离差异很大。从“charr”、“chars”和“chart”等相邻单词到“xerus”和“xoana”等164个遥远的单词 068个可能的单词！这意味着我们需要17.4位来存储距离。然而，由于大多数间隙较小，因此使用可变长度编码最有意义。
在本例中，我使用了一种简单的变量编码，其中顶部的位集意味着要添加更多字节。在这个系统中，3个字节为我们提供了21个可用位，足以填补我们最大的空白。
这个解决方案很慢，因为它会顺序扫描所有单词，直到找到匹配项。这是因为我们无法在可变长度编码中搜索，需要将所有以前的值相加才能找到当前索引。然而，10岁时 µs仍在我们的目标时间内。这也可以通过在客户机上构建2个甚至3个字符的前缀索引来轻松改进，或者客户机可以只构建一个位图。
回想起来，这个想法没有多大意义。这基本上与之前的想法相同，只是我在前面插入了第一个字母的跳转表。这会加快查找速度，因为您不需要扫描之前的每个单词。然而，我认为它也会更小，因为我不必在列表中包含第一个字母，但是因为我在进行增量编码，所以没有什么区别。工具和工具之间的距离与aken和工具之间的距离相同。
注意：这与Alexander Pruss在Game Boy实现中使用的方法基本相同。在游戏机上，提前建立索引而不是使用有价值的RAM可能是有益的。
速度显著加快，大约快20倍。这很有意义，因为你不需要平均扫描一半的单词，只需要扫描一半首字母相同的单词。我假设这不完全是26倍，因为字母分布不均。
这就是我开始这个项目的原因。我以为我可以用布卢姆过滤器来解决这个问题。然而，计算结果表明这不太可能。我还是做了实验，证实了我的怀疑。为了避免误报，我需要使用¼MiB过滤器。通过调整一些常数来过度拟合数据，这可能会稍微降低，但似乎很难找到足够小的过滤器来有效地解决这一问题。
过滤器的一个固有缺点是无法迭代条目。这意味着您不能将答案作为16位索引发送到有效的单词列表中，您需要使用完整的24位可能的单词索引。然而，即使你想存储一年的答案，这也是一个小的额外成本（只有365个额外字节）。
我仍然认为这个想法有价值，即使它不符合我的目标，即在合理的范围内没有误报。如果你能在需求上做出妥协，这可能是一个不错的选择。16岁 KiB过滤器，你可以得到1:127的假阳性率，8 KiB你可以得到1:11。如果目标是防止因拼写错误而意外提交，避免人们仅仅猜测“aeiou”是他们的第一个单词，那么这些可能是合理的权衡。不管怎么说，单词表上都充满了像“abcee”这样的奇怪单词，所以我认为没有人会注意到一些误报。
它非常快（我本可以使用更快的散列），但如果你不想出现误报，这种方法并不好。
最好的方法是在15岁时进行增量编码 压缩后的KiB。与25岁时的简单方法相比，这是一个显著的降低 基布。当然，与在JavaScript中嵌入列表和使用字典检查成员身份的简单性相比，很容易认为这不是一个值得优化的方法。包括（猜测（））| |答案。包括（猜测）。