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

Question

从字典数据库中搜索单词的最有效方法是什么.我搜索了答案,人们建议使用trie数据结构.但是为大量单词创建树的策略是加载主存储器.我正在尝试制作一个Android应用程序,它涉及我的数据结构项目的这个实现.所以有人能告诉我这本词典是如何运作的.

即使我在手机中使用t9字典,单词的建议也会很快显示在屏幕上.很想知道算法及其背后的设计.

Answer 1

您可以使用最有用的Trie来搜索大词典.因为太多的单词正在使用类似的启动,所以在常量因子搜索周围的trie brgins也可以使用到位,对物理内存的访问次数有限.您可以在网上找到许多实现.

如果有人不熟悉特里,我认为这个网站很好,我只是在这里引用他们的样本:

trie(来自检索)是一种多路树结构,可用于在字母表上存储字符串.它已被用于在拼写检查程序和自然语言"理解"程序中存储大型英语(例如)单词词典.鉴于数据:

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

相应的trie将是:

这是java中实用的Trie实现:http: //code.google.com/p/google-collections/issues/detail？id = 5