如何在对准确性影响最小的情况下将大型词典放入小型 space 中？
How to fit a large words dictionary in a small space with least effect on accuracy?
我正在尝试使用只允许 30kb 数据的微控制器实现文字游戏。为此，我需要从特定的允许单词词典中查找单词，未压缩时大小接近 4 MB。
我不需要每次都给出正确答案，所以我可以在准确性上做出妥协。有没有一种方法可以在 30kb space 中容纳 4MB 的字典，并且准确性损失最小？
我已经尝试使用优化的'trie'数据结构here, using the compressed trie generator here，这将大小从 4 MB 降低到 740 KB，但我想不出一种方法可以在不丢弃大量单词的情况下缩小它。
'trie' 总能给我正确答案。有没有一种 方法可以通过权衡准确性 来减小大小，并制定出一个在大多数情况下都能给我正确答案的结构？
也许我可以使用机器学习模型或与之相关的东西？
我知道这几乎是不可能的。但是游戏的设计让你不需要准确的答案。即使是 ~25% 的准确率仍然是合理的。
我可能会省略最长的单词，直到字典适合该大小。但在这种情况下，这可能不是最好的方法。
fit a 4MB dictionary in a 30kb space with minimum loss of accuracy?
字典文件应该是一行一个字的格式吧？这是一种非常有效的存储单词列表的方法。
所以我会说，不，4MB 的数据永远、永远都装不进 30kb 的 space。 没有压缩，没有有效存储，现在不是，不是曾经。
想一想：4MB 字面意思是 30kb 限制大小的100 倍。显然，您必须遍历磁盘 上的字典 并可能缓存结果。
不幸的是，我不得不同意这里出现的共识。我已经编写了一些类似的软件（Scrabble 机器人），所以我参考了我的代码并进行了一些计算。我使用 SOWPODS 词典，它实际上比您描述的要小很多 - 267,751 个单词，未压缩占用 2707014 个字节。
使用 trie 数据结构对于实现玩 Scrabble 等游戏的 AI 至关重要，不仅因为它减少了内存中字典的大小，而且因为基本结构大大降低了搜索功能的计算复杂性。当您尝试可能的排列时，您可以在碰到 trie 中的叶子时立即停止。我提出这个问题是因为如果您尝试为此使用 Arduino，您将不可避免地还需要确保代码在速度方面非常高效。
但是为了使用trie来确保合理的性能，这也意味着你需要在节点之间建立链接，而在32位架构上简单实现，这些链接每个将占用4个字节。您可能会实现更高级的逻辑来减少节点以存储每个 2 个字节的偏移量（2^15 指向内存中的偏移量，额外的位表示该节点是否代表一个单词）。但即使那样，这也意味着你需要 trie 有 15K 个节点（实际上更少，因为按理说你也需要一些代码。:)
我试过限制单词的最大大小，看看需要什么才能使节点数量足够少...坏消息，您最多只能存储 4 个字符的单词！这是每个最大大小的节点数：
15: 589315
14: 572754
13: 546969
12: 508959
11: 456252
10: 387321
9: 304186
8: 212237
7: 126700
6: 63605
5: 25776
4: 8208
所以基本上，当您已经充分减小字典的大小时，即使使用更复杂的算法也不再有价值。内存不足，无法运行。
针对使用机器学习模型的想法，我的经验是构建一个可以达到合理精度的功能模型通常需要相当大的内存，而获得合理的性能需要适度强大的硬件，甚至仅执行预测时。 （培训非常昂贵，但您可以离线进行。）
根据所需的效率，即使从磁盘读取数据库也可能是行不通的。缓存只能让你到此为止。
老实说，我认为@TypeKatz 的建议是最合理的。 Arduino 根本不是为此类应用程序设计的，因此最好的办法是将计算量大、内存密集型处理卸载到外部设备。您可以通过串行端口使用连接的设备，或者投资 Wifi 屏蔽并与附近的服务器通信。
无论如何，祝你好运！
我正在尝试使用只允许 30kb 数据的微控制器实现文字游戏。为此，我需要从特定的允许单词词典中查找单词，未压缩时大小接近 4 MB。
我不需要每次都给出正确答案，所以我可以在准确性上做出妥协。有没有一种方法可以在 30kb space 中容纳 4MB 的字典，并且准确性损失最小？
我已经尝试使用优化的'trie'数据结构here, using the compressed trie generator here，这将大小从 4 MB 降低到 740 KB，但我想不出一种方法可以在不丢弃大量单词的情况下缩小它。
'trie' 总能给我正确答案。有没有一种 方法可以通过权衡准确性 来减小大小，并制定出一个在大多数情况下都能给我正确答案的结构？ 也许我可以使用机器学习模型或与之相关的东西？
我知道这几乎是不可能的。但是游戏的设计让你不需要准确的答案。即使是 ~25% 的准确率仍然是合理的。
我可能会省略最长的单词，直到字典适合该大小。但在这种情况下，这可能不是最好的方法。
fit a 4MB dictionary in a 30kb space with minimum loss of accuracy?
字典文件应该是一行一个字的格式吧？这是一种非常有效的存储单词列表的方法。
所以我会说，不，4MB 的数据永远、永远都装不进 30kb 的 space。 没有压缩，没有有效存储，现在不是，不是曾经。
想一想：4MB 字面意思是 30kb 限制大小的100 倍。显然，您必须遍历磁盘 上的字典 并可能缓存结果。
不幸的是，我不得不同意这里出现的共识。我已经编写了一些类似的软件（Scrabble 机器人），所以我参考了我的代码并进行了一些计算。我使用 SOWPODS 词典，它实际上比您描述的要小很多 - 267,751 个单词，未压缩占用 2707014 个字节。
使用 trie 数据结构对于实现玩 Scrabble 等游戏的 AI 至关重要，不仅因为它减少了内存中字典的大小，而且因为基本结构大大降低了搜索功能的计算复杂性。当您尝试可能的排列时，您可以在碰到 trie 中的叶子时立即停止。我提出这个问题是因为如果您尝试为此使用 Arduino，您将不可避免地还需要确保代码在速度方面非常高效。
但是为了使用trie来确保合理的性能，这也意味着你需要在节点之间建立链接，而在32位架构上简单实现，这些链接每个将占用4个字节。您可能会实现更高级的逻辑来减少节点以存储每个 2 个字节的偏移量（2^15 指向内存中的偏移量，额外的位表示该节点是否代表一个单词）。但即使那样，这也意味着你需要 trie 有 15K 个节点（实际上更少，因为按理说你也需要一些代码。:)
我试过限制单词的最大大小，看看需要什么才能使节点数量足够少...坏消息，您最多只能存储 4 个字符的单词！这是每个最大大小的节点数：
15: 589315
14: 572754
13: 546969
12: 508959
11: 456252
10: 387321
9: 304186
8: 212237
7: 126700
6: 63605
5: 25776
4: 8208
所以基本上，当您已经充分减小字典的大小时，即使使用更复杂的算法也不再有价值。内存不足，无法运行。
针对使用机器学习模型的想法，我的经验是构建一个可以达到合理精度的功能模型通常需要相当大的内存，而获得合理的性能需要适度强大的硬件，甚至仅执行预测时。 （培训非常昂贵，但您可以离线进行。）
根据所需的效率，即使从磁盘读取数据库也可能是行不通的。缓存只能让你到此为止。
老实说，我认为@TypeKatz 的建议是最合理的。 Arduino 根本不是为此类应用程序设计的，因此最好的办法是将计算量大、内存密集型处理卸载到外部设备。您可以通过串行端口使用连接的设备，或者投资 Wifi 屏蔽并与附近的服务器通信。
无论如何，祝你好运！