存储内存占用少的大字典+快速查找的方法(在Android上)

Question

我正在开发一个需要大量(~25万字词典)的安卓文字游戏应用程序.我需要:

• 合理快速查找例如恒定时间更好,需要每秒执行200次查找以解决单词拼图,并且可能更频繁地在0.2秒内进行20次查找以检查用户刚刚拼写的单词.

编辑:查询通常会问"在字典中吗？".我想在这个单词中支持最多两个通配符,但这很容易,只需生成通配符可能存在的所有可能的字母并检查生成的单词(即26*26查找带有两个通配符的单词) .

• 因为它是一个移动应用程序,使用尽可能少的内存并且只需要少量初始下载字典数据是首要任务.

我的第一次天真尝试使用了Java的HashMap类,这导致了内存不足异常.我已经研究过使用android上可用的SQL lite数据库,但这看起来有些过分.

做我需要的好方法是什么？

Answer 1

你可以用更低级的方法实现你的目标......如果它是一个文字游戏,那么我怀疑你正在处理27个字母字母.因此,假设一个不超过32个字母的字母表,即每个字母5位.您可以使用5位/字母的简单编码将12个字母(12 x 5 = 60位)填充到单个Java long中.

这意味着实际上如果你没有超过12个字母/单词的单词,你可以将你的字典表示为一组Java long.如果你有250,000个单词,这个集合的一个简单的表示作为单个,排序的longs数组应该采用250,000字x 8字节/字= 2,000,000~2MB内存.然后通过二分搜索进行查找,考虑到数据集的小尺寸,这应该非常快(少于20次比较,因为2 ^ 20会使您超过一百万).

如果你有超过12个字母的单词,那么我会将> 12个字母单词存储在另一个数组中,其中1个单词将由2个连接的Java long以明显的方式表示.

注意:这个工作原因并且可能比trie更节省空间并且至少非常简单地实现的原因是字典是常量的...如果你需要修改数据集,搜索树是好的,但是如果数据set是常量,你可以经常使用简单的二进制搜索方式.

Answer 2

你会想要某种trie。我认为也许三元搜索树会很好。它们的查找速度非常快，内存使用量也很低。本文提供了有关 TST 的更多信息。它还讨论了排序，因此并非所有内容都适用。这篇文章可能更适用一些。正如文章所说，TST

将数字尝试的时间效率与二叉搜索树的空间效率结合起来。

如此表所示，查找时间与使用哈希表非常相似。