2011-11-02 270 views
4

背景:
我的CSS360组正尝试创建一个包含自动完成搜索功能的Android应用程序。我们要搜索的数据包含大约7000个条目,并且将存储在手机本身的SQLite数据库中。最明显的方法是在用户输入每个字符后对数据库进行线性搜索,然后返回可能是用户查询字母扩展名的建议列表。但是,这看起来效率很低,我们一直在寻找更好的替代方案。在今天的另一个课程中,我的导师简要地讨论了trie数据结构,并提到它经常用于存储整个字典。可以在对数时间内(与常规旧数组的线性时间相反)检索条目,因此这对我们来说似乎是一个很好的工具!不幸的是,我们已经对这个项目感到厌倦了,而且我们没有人真正知道如何做到这一点。我们所有人都编码到目前为止是基本的控制台应用程序,教我们编程基础知识。我们都试图通过观看YouTube视频来学习Android平台,并将数据库内容与我们团队中具有任何SQL体验的人员区分开来。我们可以认真使用一些指针!预先填充的Trie

问题:

  • 当创建一个线索,是有可能对整个结构预先填充? IE:为每个使用的节点生成一行代码,以便在程序启动时整个结构已经存在于内存中?我的想法是,这将节省我们每次程序启动时必须从数据库重新生成整个特里结构的开销。如果是这样,是否有一种简单的方法将这几千行代码加入到我们的程序中? IE:某种脚本可以将数据库文件转换为可以复制并粘贴到Eclipse的java命令的巨大文本文件?
  • 如果我们直接搜索数据库而不是使用某种内部列表或数据结构,是否会有相当多的开销?我们是否应该从数据库中复制名称并在程序中搜索它们以实现自动完成功能?
  • 如果这对我们来说在技术上证明过于困难,而且我们不得不求助于常规线性搜索,那么性能是否会受到明显影响?
  • 我们目前的计划是每次用户输入一个字符时运行自动完成功能,然后等待该功能返回,然后再继续输入。迄今为止我们中唯一编写的程序是同步运行的。我们需要知道什么才能使这个函数异步?考虑到我们的新手能力以及我们已经必须满足的要求,这对我们来说技术上太具有挑战性了吗?

回答

0

sqlite应该能够很好地提供这种自动完成功能。我建议使用他们的内部索引重新执行轮子。如果你需要做后者,那么在完成这些工作之后,sqlite可能不会帮助你。

如果你想要子串搜索,那么full text search可能是你最好的选择。

如果你只想完成单词的开头,那么只使用他们的香草indexes应该是绰绰有余。如果性能出现问题,那就等到他们在查询之前输入三个字符。设置您的结果的限制,以获得快速响应。