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

Question

问题

[ 以下是应用程序在哪些约束条件下应该做的描述 ]

我想要一个数据结构,搜索string一个250,000字列表中是否存在,同时只使用相当数量的ram并保持将这个数据结构加载到ram small所需的时间(比如说0-8秒).找到一个单词所需的时间也应该很快(比方说0到0.5秒),但ram的使用更为重要.它也应该可以创建多个游戏(更多关于这个游戏的标题是"使用"),而不需要更多的内存.

知道哪些单词以a开头string,但不足以牺牲加载时间达数秒也是非常有价值的.

---

使用

它适用于Android离线游戏.有限的ram可用.应用程序根据此帖子可以使用的最大ram数量在16-32mb ram之间,具体取决于设备.我的空Android应用程序已经使用了大约17mb(在Android Studio中使用Memory Monitor).我的android设备将ram的使用量限制在26mb,让我的整个空间大约为8mb Activity.

---

我试过的选项

他们似乎都注定了不同的方式.

1. Hashmap - 将所有单词读入哈希映射对象.

   1.1 初始化速度:用23秒慢速将每个单词读入哈希映射.

   1.2 ram用法:使用大量的ram,虽然我忘记了多少.

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

   1.4 缩小可能的单词(可选):慢,需要经过整个哈希映射并逐个删除它们.此外,由于它使用删除,因此无法使用相同的哈希映射实例来播放多个游戏.添加更多游戏时会占用太多内存,因此无法缩小可能的单词.

2. 特里 -实现一个RadixTree& 你可以在这里看到我的实现.

   2.1 初始化速度:用47秒慢速读取每个单词进入RadixTree.

   2.2 ram使用:使用大量的ram,以至于Android几次挂起线程.

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

   2.4 缩小可能的单词(可选):超快,因为只需要对树中的节点进行引用,然后找到所有可能的单词作为其子节点.您可以通过缩小可能的单词来玩很多游戏,因为额外的游戏只需要参考树中的节点!

3. 扫描仪 - 按顺序浏览文字文件

   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();

---

我想到的选项:

1. 长二进制搜索树:将单词列表转换为longs 列表然后读取它们并对它们进行二进制搜索.

   1.1 初始化速度:可能与哈希映射相同或少于约20秒.但是我希望调用Array.sort()不会占用太多时间,因此还不知道.

   1.2 ram用法:如果你只用12个字母的单词或26个字母的字母表,你需要5位(2 ^ 5 = 32)来编码一个字符串.一长串需要250,000*8位=大约2mb.哪个不是太多.

   1.3 搜索速度: Arrays.binarySearch()

   1.4 缩小可能的单词(可选):缩小可能的单词是可能的,但我不知道如何.根据这篇文章的评论.

2. 带存储的Hashmap - 创建将单词映射到单词列表文件的索引号的散列函数.然后访问此特定位置的文件,并从此处查看是否存在单词.您可以利用字母表的顺序来确定您是否仍然可以找到该单词,因为单词列表是按自然顺序排列的.

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

   2.2 ram用法:无.

   2.3 搜索速度:快.

   2.4 缩小可能的单词(可选):不可能.

---

我有具体问题

1. 我在"我想到的选项"部分中可以选择的选项是可行的选项,还是我想念的东西会使它们无法实现？
2. 我有没有想过哪些选项在性能方面更好/相同？

结束语

我已经坚持了一个星期了.所以任何新的想法都非常受欢迎.如果我上面的任何一个假设不正确,我也很高兴听到他们.

我以这种方式发表了这篇文章,所以其他人也可以通过看到我的错误或看到答案中有用的东西来向他们学习.

Answer 1

这听起来像是布隆过滤器的理想用途。如果您愿意承受某些内容被错误地视为单词的风险，您可以将单词列表压缩为您愿意的大小的内存量。