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

问题

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

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

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


使用

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


我试过的选项

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

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

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

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

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

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

  2. Trie – 实现RadixTree并且 您可以在此处查看我的实现。

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

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

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

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

  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. long-binary-search-tree:将word-list转换为long s列表,然后读取这些列表并对它们进行二进制搜索。

    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 – 创建将单词映射到单词列表文件的索引号的散列函数 。 然后访问此特定位置的文件,并从此处查看是否存在单词。 您可以使用字母表的顺序来确定您是否仍然可以find该单词,因为单词列表是按自然顺序排列的。

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

    2.2 ram用法:无。

    2.3 搜索速度:快。

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


我有具体问题

  1. 我在“我想到的选项”部分中可以选择的选项是可行的选项,还是我错过的东西会使它们无法实现?
  2. 我有没有想过哪些选项在性能上更好/相等?

结束语

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

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

    这听起来像是布隆filter的理想用途。 如果您愿意允许将某些内容误认为某个词的风险,您可以将您的词汇表缩减为您愿意制作的内存量。

    我遇到了同样的问题,并最终选择了“盘上”特里。 也就是说,我使用字节偏移而不是指针将数据结构编码为单个文件(以相反的顺序打包节点,其中“根”节点是最后写入的节点)。

    通过简单地将文件读入字节数组来快速加载,使用与指针相同的方式使用偏移值进行遍历。

    我的200K字集合适合1.7 MB(未压缩),每个字终止节点具有4字节值。