在我的 Android 应用程序中，我想要一个带有自动完成功能的输入字段。项目数约为 300000。最好的解决方案似乎是将项目放入一个文件（在 sdcard 上），每行一个项目，每行具有相同数量的字符，以便我可以寻找特定的行号. 如果用户在文本字段中输入内容，我将二进制搜索（通过 RandomAccessFile）文件并显示建议。
我希望自动完成速度非常快（最好在 100 毫秒以下，但我想这是不可能的），我可以做哪些优化？
更新 1： 我会将用户输入转换为带空格的小写英文字符 (az)。所以 'A/b' 会被转换成 'a b' 然后被搜索。
Uodate 2： 我现在意识到我需要额外的东西 - 搜索以单词开头的子字符串。
您要查找的内容称为 TRIE
http://forums.sun.com/thread.jspa?threadID=5295936
在计算机科学中，trie 或前缀树是一种有序树数据结构，用于存储关联数组，其中键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的键；相反，它在树中的位置显示了它与哪个键相关联。一个节点的所有后代都具有与该节点相关联的字符串的公共前缀，而根与空字符串相关联。值通常不与每个节点相关联，仅与叶和一些与感兴趣的键对应的内部节点相关联。
为什么不直接使用SQLite DB 而不是文本文件？
在您的情况下，我认为您在速度方面没有比便携式数据库更好的方法了。
Trie 是显而易见的答案，并且已经提到过，但另外tr13 库可能是您正在查看的内容。它是垃圾收集器友好的（单个原始字节数组或字节缓冲区），紧凑，并且对于您的情况绝对足够快。键通常是 UTF-8 字符串，尽管可以是任何字节序列。同样的值，虽然也有可变长度整数（vints）的替代方法，用于获得非常紧凑的字符串到整数的查找（尤其是对于较小的整数集）。
一种策略可能是使用RandomAccessFile和 Binary Search 来缩小结果范围。然后，一旦可能的条目足够小，将该部分加载到内存中，并进行内存搜索。
这将提高性能，因为当人们键入时，您可以快速搜索已加载到内存中的文件的同一部分。
旧线程，但这是您需要的： Stringsearch 库
我将它用于我的 Android 应用程序“Wordlist Pro”，它真的很快。
100 毫秒是足够的时间。我认为最大的担忧是显示更新。
如果您想避免使用实际的数据库，除了主文件之外，还可以使用简单的索引文件来轻松完成。
您可以将字符串的前 N 个字节（可能是 4 个？）和文件偏移量存储到主文件中的索引中，每 32 条左右的记录，并在其中进行二进制搜索。然后，在二进制搜索让您非常接近之后，您可以线性搜索多达 32 条记录。
考虑到平均字符串长度和媒体上单次读取的大小，您可以将索引频率从 32 条记录调整为任何有意义的值。如果您有 512 字节的文件系统读取和 8 字节的平均字符串，那么您将每 64 条记录执行一次索引，等等。每个最小磁盘读取大小有多个索引记录没有多大意义。
可以轻松生成索引文件，然后您可以使用简单的文本编辑器管理主文件。
看看这个http://en.wikipedia.org/wiki/Binary_search_algorithm
在一个排序的文件中，你有一个 O(log(n)) 的二进制搜索最坏的情况，下一个最好的事情是某种哈希映射，它是 O(1)，尽管这对于部分单词来说很复杂，并且会产生一个巨大的映射表。
我建议看看您是否可以为此目的使用标准库。也许 apache lucene 可以在安卓手机中使用。如果是这样，您可以建立一个索引（单词前缀-> android sql lite 中单词的 id）。这是关于 lucene 正在使用的一种算法的讨论。
每行一个字存储的一个主要问题是在恒定时间内没有随机访问行（访问行 X 包括从文件开头计算X 个换行符），因此您的二进制搜索会受到影响。
在这种特定（自动完成）情况下，您需要的是前缀树或其变体（将几个节点组合成一个，或者将小于特定大小的子树变成普通的旧排序单词列表）。
提前将您的可能性预处理到搜索树中，而不是在运行时进行。
我也可以做这样的事情（下面是一个预处理文件）：
aa - line 1
ab - line 17
.
.
zz - line 299819
如果用户输入以 aa 开头的内容，我会阅读第 1 - 17 行并按顺序在其中搜索