java - 如何从庞大的数据库中搜索给定的单词？

Question

从字典数据库中搜索单词的最有效方法是什么。我搜索了答案，人们建议使用 trie 数据结构。但是为大量单词创建树的策略是加载主内存。我正在尝试为我的数据结构项目制作一个涉及此实现的 android 应用程序。谁能告诉我字典是如何工作的。

即使我在手机中使用 t9 词典，单词建议也会很快出现在屏幕上。很想知道它背后的算法和设计。

Answer 1

您可以使用对搜索大字典最有用的Trie 。因为太多的词都在使用类似的启动，所以围绕常数因子搜索的尝试也可以在适当的位置使用，访问物理内存的次数有限。你可以在网上找到很多实现。

如果有人不熟悉 trie，我认为这个网站很好，我只是在这里引用他们的示例：

Trie（来自检索）是一种多路树结构，可用于在字母表上存储字符串。它已被用于在拼写检查程序和自然语言“理解”程序中存储大型英语（比如）单词词典。给定数据：

an, ant, all, allot, alloy, aloe, are, ate, be 

相应的尝试将是：

这是 Java 中很好的实用 Trie 实现： http ://code.google.com/p/google-collections/issues/detail?id=5

Answer 2

有很多方法可以做到这一点。我前段时间使用的一个（如果您不更改字典特别好）是创建一个前缀索引。

也就是说，您对条目进行词汇排序。然后，为不同的首字母保存范围的（结束）位置。也就是说，如果您的条目具有从 1 到 1000 的索引，并且单词“aardvark -- azerbaijan”的范围从 1 到 200，那么您在单独的表“a | 200”中创建一个条目，然后您首先执行相同的操作和第二个字母。然后，如果您需要查找某个特定的词，则大大缩小了搜索范围。就我而言，前两个字母的索引就足够了。

同样，此方法要求您使用数据库，如 SQLite，我认为它存在于 Android 上。

Answer 3

使用 trie 确实有空间意识，当我在加载 150,000 个单词后检查我的 RAM 使用情况时才意识到，使用量是 150 MB（Trie 是用 C++ 实现的）。内存消耗很大程度上是由于指针。我最终得到了三元尝试，它的内存浪费非常少，大约为 30 MB（与 150 MB 相比），但时间复杂度有所增加。另一种选择是使用“左孩子右兄弟”，其中内存浪费非常少，但时间复杂度高于三元特里树。