如何在具有下降内存消耗和look-up时间的大型单词列表（词汇表）中找到单词？
How to find a word in large word list (vocabulary) with descent memory consumption and look-up time?
问题
[下面是对应用在哪些约束条件下应该做什么的描述]
我想要一个 data-structure 来搜索 string 是否存在于 250,000 word-list 中，同时仅使用相当数量的 ram 并保持加载此 [= =174=] 进入 ram small（比方说 0-8 秒）。查找单词所需的时间也应该很快（假设为 0 到 0.5 秒），但 ram 的使用更为重要。还应该可以创建多个游戏（更多关于这个游戏的内容在标题 "use"）而不需要更多的内存。
知道哪些单词以 string 开头也很有价值，但还不足以牺牲 load-time 很多秒。
使用
它用于 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 中使用内存监视器）。我的 android 设备将 ram 使用量限制在 26mb，让我的整个 Activity.
有大约 8mb 的免费空间 space
我试过的选项
他们似乎都注定要以不同的方式。
Hashmap - 将所有单词读入 hash-map object.
1.1 初始化速度：每个字读入Hash-map慢23秒
1.2 ram 使用情况： 使用了大量的 ram，虽然我忘了具体是多少。
1.3 搜索速度： 查找单词是否存在于列表中当然很快。
1.4 缩小可能的单词范围（可选）： 慢，需要遍历整个hash-map 并一一删除。也因为它正在使用删除，多个游戏将无法使用 hash-map 的相同实例进行播放。添加更多游戏时会占用太多内存，从而无法缩小可能的单词范围。
&
You can see my implementation here.
2.1 初始化速度： 将每个单词读入 RadixTree 需要 47 秒。
2.2 ram 使用： 使用大量 ram，以至于 Android 挂起线程几次。
2.3 搜索速度： 快速查找列表中是否存在单词。
2.4 缩小可能的词范围（可选）： 非常快，因为只需要引用树中的一个节点，然后找到所有可能的词作为其 children.您可以通过缩小可能的单词范围来玩很多游戏，因为额外的游戏只需要引用树中的一个节点！
扫描仪 - 按顺序word-file
3.1 初始化速度： none.
3.2 内存使用： none.
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 longs then reading these in and doing a binary search on them.
1.1 初始化速度： 可能与 hash-map 相同或稍短，大约 20 秒。但是我希望调用 Array.sort() 不会花费太多时间，目前还不知道。
1.2 ram 用法： 如果您只用 26 个字母的字母表计算 12 个字母或更少的单词，则需要 5 位 (2^5= 32) 来编码一个字符串。一个多头数组需要 250,000*8 位 = 大约 2mb。这不是太多。
1.3 搜索速度： Arrays.binarySearch()
1.4 缩小可能的词范围（可选）：缩小可能的词范围是可能的，但我不确定如何。 According to a comment on this post.
Hashmap with storage - 创建一个哈希函数，将单词映射到 word-list 文件的索引号。然后访问这个特定位置的文件并从这里查看是否存在单词。由于 word-list 是自然顺序，因此您可以使用字母表的顺序来确定您是否仍然可以找到该词。
2.1 初始化速度： 不需要（因为我需要事先将每个单词放在正确的索引处。）
2.2 内存使用： none.
2.3 搜索速度：快。
2.4 缩小可能的词范围（可选）： 不可能。
我有具体问题
- 我在 "Options I have thought of" 部分中想到的选项是否可行，或者是否有我遗漏的东西导致它们无法实施？
- 是否有我没有想到的选项better/equal？
结束语
我已经坚持了大约一个星期了。所以任何新想法都非常受欢迎。如果我上面的任何假设是不正确的，我会d 也很高兴听到他们的消息。
我这样做 post 是为了让其他人也能从中吸取教训，无论是看到我的错误还是看到答案中的有效内容。
这听起来像是 bloom filter 的理想用途。如果您愿意冒某些东西被错误地认为是一个词的风险，您可以将您的词表压缩到您愿意的大小内存中。
我遇到了同样的问题，最后使用了 "on-disk" 特里树。也就是说，我使用字节偏移量而不是指针将数据结构编码到单个文件中（以相反的顺序打包节点，"root" 节点是最后写入的）。
只需将文件读入字节数组即可快速加载，trie 遍历使用与指针相同的偏移值。
我的 200K 字集适合 1.7 MB（未压缩），每个字终止节点中有一个 4 字节值。
问题
[下面是对应用在哪些约束条件下应该做什么的描述]
我想要一个 data-structure 来搜索 string 是否存在于 250,000 word-list 中，同时仅使用相当数量的 ram 并保持加载此 [= =174=] 进入 ram small（比方说 0-8 秒）。查找单词所需的时间也应该很快（假设为 0 到 0.5 秒），但 ram 的使用更为重要。还应该可以创建多个游戏（更多关于这个游戏的内容在标题 "use"）而不需要更多的内存。
知道哪些单词以 string 开头也很有价值，但还不足以牺牲 load-time 很多秒。
使用
它用于 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 中使用内存监视器）。我的 android 设备将 ram 使用量限制在 26mb，让我的整个 Activity.
我试过的选项
他们似乎都注定要以不同的方式。
Hashmap - 将所有单词读入 hash-map object.
1.1 初始化速度：每个字读入Hash-map慢23秒
1.2 ram 使用情况： 使用了大量的 ram，虽然我忘了具体是多少。
1.3 搜索速度： 查找单词是否存在于列表中当然很快。
1.4 缩小可能的单词范围（可选）： 慢，需要遍历整个hash-map 并一一删除。也因为它正在使用删除，多个游戏将无法使用 hash-map 的相同实例进行播放。添加更多游戏时会占用太多内存，从而无法缩小可能的单词范围。
2.1 初始化速度： 将每个单词读入 RadixTree 需要 47 秒。
2.2 ram 使用： 使用大量 ram，以至于 Android 挂起线程几次。
2.3 搜索速度： 快速查找列表中是否存在单词。
2.4 缩小可能的词范围（可选）： 非常快，因为只需要引用树中的一个节点，然后找到所有可能的词作为其 children.您可以通过缩小可能的单词范围来玩很多游戏，因为额外的游戏只需要引用树中的一个节点！
扫描仪 - 按顺序word-file
3.1 初始化速度： none.
3.2 内存使用： none.
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
longs then reading these in and doing a binary search on them.1.1 初始化速度： 可能与 hash-map 相同或稍短，大约 20 秒。但是我希望调用 Array.sort() 不会花费太多时间，目前还不知道。
1.2 ram 用法： 如果您只用 26 个字母的字母表计算 12 个字母或更少的单词，则需要 5 位 (2^5= 32) 来编码一个字符串。一个多头数组需要 250,000*8 位 = 大约 2mb。这不是太多。
1.3 搜索速度： Arrays.binarySearch()
1.4 缩小可能的词范围（可选）：缩小可能的词范围是可能的，但我不确定如何。 According to a comment on this post.
Hashmap with storage - 创建一个哈希函数，将单词映射到 word-list 文件的索引号。然后访问这个特定位置的文件并从这里查看是否存在单词。由于 word-list 是自然顺序，因此您可以使用字母表的顺序来确定您是否仍然可以找到该词。
2.1 初始化速度： 不需要（因为我需要事先将每个单词放在正确的索引处。）
2.2 内存使用： none.
2.3 搜索速度：快。
2.4 缩小可能的词范围（可选）： 不可能。
我有具体问题
- 我在 "Options I have thought of" 部分中想到的选项是否可行，或者是否有我遗漏的东西导致它们无法实施？
- 是否有我没有想到的选项better/equal？
结束语
我已经坚持了大约一个星期了。所以任何新想法都非常受欢迎。如果我上面的任何假设是不正确的，我会d 也很高兴听到他们的消息。
我这样做 post 是为了让其他人也能从中吸取教训，无论是看到我的错误还是看到答案中的有效内容。
这听起来像是 bloom filter 的理想用途。如果您愿意冒某些东西被错误地认为是一个词的风险，您可以将您的词表压缩到您愿意的大小内存中。
我遇到了同样的问题，最后使用了 "on-disk" 特里树。也就是说，我使用字节偏移量而不是指针将数据结构编码到单个文件中（以相反的顺序打包节点，"root" 节点是最后写入的）。
只需将文件读入字节数组即可快速加载，trie 遍历使用与指针相同的偏移值。
我的 200K 字集适合 1.7 MB（未压缩），每个字终止节点中有一个 4 字节值。