我正在尝试使用一个仅允许30kb数据的微控制器来实现一个文字游戏。为此，我需要从一个未压缩时大小接近4MB的特定词典中查找单词。

我不需要每次都给出正确的答案，所以我可以牺牲一些准确性。有什么方法可以将4MB的词典压缩到30kb的空间内，同时尽量减少准确性的损失吗？

我已经尝试使用优化后的’trie’数据结构，如此处建议的那样，并使用此处的压缩trie生成器，将大小从4MB减少到740KB，但我想不出如何在不丢弃大量单词的情况下进一步缩小它。

‘trie’总是能给我正确的答案。有没有通过牺牲准确性来减少大小的方法，构建一个结构，大多数时候都能给我正确的答案？也许我可以使用机器学习模型或与之相关的东西？

我明白这几乎是不可能的。但这个游戏设计得并不需要准确的答案。即使是大约25%的准确率仍然是可以接受的。

我可以省略最长的单词，直到词典适合那个大小。但在这种情况下，这可能不是最佳方法。

回答：

不幸的是，我不得不同意这里出现的共识。我写过一些类似的软件（一个拼字游戏机器人），所以我参考了我的代码并进行了一些计算。我使用的是SOWPODS词典，实际上比你描述的要小得多 – 267,751个单词，未压缩时占用2707014字节。

使用trie数据结构对于实现像拼字游戏这样的游戏的AI至关重要，不仅仅因为它减少了内存中词典的大小，而是因为基本结构显著降低了搜索功能的计算复杂度。当你尝试可能的排列组合时，你可以立即在到达trie的叶子节点时停止。我提到这一点是因为如果你试图使用Arduino来做这件事，你不可避免地也需要确保代码在速度上非常高效。

但是，为了使用trie来确保合理的性能，这也意味着你需要在节点之间建立链接，并且在32位架构上的简单实现中，这些链接将各占4字节。你可能会实现更复杂的逻辑，将节点减少到每个存储偏移量的2字节（2^15指向内存中的偏移量，额外的一位作为该节点是否代表一个单词的指示）。但即便如此，这意味着你需要trie有15K个节点（实际上更少，因为合理来说你还需要一些代码在里面。:）

我尝试限制单词的最大长度，看看需要什么来将节点数量降低到足够低……坏消息是，你只能存储长度不超过4个字符的单词！这是每个最大长度的节点数量：

15: 58931514: 57275413: 54696912: 50895911: 45625210: 3873219: 3041868: 2122377: 1267006: 636055: 257764: 8208

所以，基本上，当你将词典的大小减少到足够小时，使用更复杂的算法已经不再有价值。内存不足以让它工作。

关于使用机器学习模型的想法，我的经验是，构建一个能够达到哪怕是某种合理准确性的功能模型通常需要大量的内存，而获得合理的性能需要中等强度的硬件，即使只是进行预测。（训练非常昂贵，但你可以在线下进行。）

即使是从磁盘读取数据库也可能不是一个可行的解决方案，这取决于所需的效率。缓存只能帮你到一定程度。

坦白说，我认为@TypeKatz的建议是最合理的。Arduino根本不是为这种应用设计的，所以最好的做法是将计算密集、内存密集的处理卸载到外部设备。你可以使用通过串行端口连接的设备，或者投资一个Wifi屏蔽并与附近的服务器通信。

无论如何，祝你好运！