java - 如何在大型单词列表(词汇表)中查找具有下降内存消耗和查找时间的单词？

Question

问题

[下面是应用程序在受限条件下的操作说明]

我想要一个数据结构来搜索25万个单词列表中是否存在string，同时仅使用相当数量的ram并保持将数据结构加载到ram中所需的时间很小(比如说0到8秒) 。查找单词所需的时间也应该很快(比如说0到0.5秒)，但是ram的使用更为重要。还可以创建多个游戏(在标题“使用”中更多有关该游戏的内容)，而无需占用大量内存。

知道哪些单词以string开头也非常有值(value)，但不足以牺牲很多秒的加载时间。

采用

适用于Android离线游戏。有限的内存可用。 The maximum amount of ram an Application can use according to this post is between 16-32mb ram depending on the device.我的空Android应用程序已经使用了大约17mb(使用Android Studio中的Memory Monitor)。我的android设备将ram的使用上限限制为26mb，而整个Activity则为我留出了大约8mb的可用空间。

我尝试过的选项

他们似乎都以不同的方式注定了失败。

哈希图-将所有单词读入哈希图对象。

1.1 初始化速度:慢，需要23秒才能将每个单词读入哈希表。

1.2 ram用法:使用了大量的ram，尽管我忘记了多少。

1.3 搜索速度:当然，快速查找列表中是否存在单词。

1.4 缩小可能的单词范围(可选):较慢，需要遍历整个哈希图并逐一删除它们。另外，由于它使用的是删除功能，因此无法使用哈希图的相同实例来玩多个游戏。添加更多游戏时会占用太多内存，从而无法缩小可能的单词数。

Trie - Implement a RadixTree＆
You can see my implementation here.

2.1 初始化速度:慢，需要47秒才能将每个单词读入RadixTree。

2.2 ram用法:使用大量的ram，以至于Android多次挂起线程。

2.3 搜索速度:快速查找列表中是否存在单词。

2.4 缩小可能单词的范围(可选):超快速，因为只需要引用树中的一个节点即可找到所有可能的单词作为其子代。您可以通过缩小可能的单词来玩很多游戏，因为额外的游戏只需要引用树中的一个节点即可!

扫描仪-按顺序浏览单词文件

3.1 初始化速度:无。

3.2 ram用法:无。

3.3 搜索速度:大约20秒。

3.4 缩小可能的单词的范围(可选):无法现实地完成。

简单的代码:

String word;
String wordToFind = "example";
boolean foundWord = false;

while (wordFile.hasNextLine()) {
    word = wordFile.nextLine();
    if(word.equals(wordToFind)) {
        foundWord = true;
        break;
    }
}

test.close();

我想到的选项:

Long-binary-search-tree: Converting the word-list to a list of long s then reading these in and doing a binary search on them.

1.1 的初始化速度:可能与哈希图相同或略微，大约需要20秒。但是我希望调用Array.sort()不会花费太多时间，到目前为止还不知道。

1.2 ram用法:如果仅使用12个字母单词或更低的字母和26个字母的字母，则需要5位(2 ^ 5 = 32)来编码字符串。那么一个long数组将需要250,000 * 8位=大约2mb。哪个不算太多。

1.3 搜索速度: Arrays.binarySearch()

1.4 缩小可能的单词(可选):缩小可能的单词是可能的，但我不确定如何缩小。 According to a comment on this post。

带有存储的哈希图-创建一个将单词映射到单词列表文件的索引号的哈希函数。然后在此特定位置访问文件，并从此处查找是否存在单词。您可以利用字母的顺序来确定是否仍然可以找到该单词，因为单词列表是自然排列的。

2.1 初始化速度:不需要(因为我需要事先将每个单词放在正确的索引处。)

2.2 ram用法:无。

2.3 搜索速度:很快。

2.4 缩小可能的单词范围(可选):不可能。

我有具体问题

我在“我想到的选项”部分中考虑过的选项是否可行，或者是否还有我错过的事情而无法实现？

是否有我没有想到过的选项在性能上更好/相等？

结束语

我已经在这个问题上停留了大约一个星期。因此，任何新想法都将受到欢迎。如果以上任何假设不正确，我也很高兴听到有关它们的信息。

我以这种方式发布了这篇文章，以便其他人也可以从他们那里学习，无论是看到我的错误还是看到答案中有什么用。

Answer 1

这听起来像是bloom filter的理想用法。如果您愿意冒被误认为某个单词的风险，则可以将单词表压缩为您愿意制作的大小一样大的内存。