java - 在排序文件中使用二进制搜索超快速自动完成(300000 行)

Question

在我的 Android 应用程序中，我想要一个具有自动完成功能的输入字段。项目数量约为 300000。最好的解决方案似乎是将项目放入文件中(在 sdcard 上)，每行一个项目，每行将具有相同数量的字符，以便我可以查找特定的行号.如果用户在文本字段中输入内容，我将二进制搜索(通过 RandomAccessFile)文件并显示建议。

我希望自动完成超快(最好在 100 毫秒以下，但我想这是不可能的)，我可以做哪些优化？

更新 1:我会将用户输入转换为带空格的小写英文字符 (a-z)。所以 'A/b' 将被转换为 'a b' 然后进行搜索。

Uodate 2:我现在意识到我需要额外的东西 - 搜索以单词开头的子字符串。

Answer 1

你要找的是 TRIE

http://forums.sun.com/thread.jspa?threadID=5295936

在计算机科学中，trie 或前缀树是一种有序的树数据结构，用于存储关联数组，其中键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的键；相反，它在树中的位置显示了它关联的键。一个节点的所有后代都有一个与该节点关联的字符串的公共(public)前缀，并且根与空字符串关联。值通常不与每个节点相关联，仅与叶子和一些与感兴趣的键对应的内部节点相关联。