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

你要找的东西叫提尔

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

你为什么不直接用 SQLite
我认为在你的情况下,没有什么比便携式数据库在速度方面做得更好的了。

Trie是显而易见的答案,而且已经提到了,但是另外 tr13 library 可能就是你看到的。它是垃圾收集器友好的(单个原始字节数组或字节缓冲区),紧凑,并且绝对足够快。键通常是UTF-8字符串,尽管可以是任何字节序列。同样地,尽管也有可变长度int(vint)的替代方法,用于从非常紧凑的字符串到int查找(特别是对于较小的int集)。

RandomAccessFile 和二进制搜索。然后,一旦可能的条目足够小,将该部分加载到内存中,并执行内存内搜索。

看看这个 http://en.wikipedia.org/wiki/Binary_search_algorithm

在已排序的文件中,有一个二进制搜索,最坏情况是O(log(n)) 下一个最好的方法是某种hashmapping,虽然对于部分单词来说这很复杂,并且会产生一个巨大的映射表,但它是O(1)。

每行存储一个字的一个主要问题是,在固定时间内没有对行的随机访问(访问行X包括 从文件的开头添加X个换行符),这样您的二进制搜索将受到影响。

在这种特定(自动完成)情况下,您需要的是 Prefix Tree 或者它的变体(将多个节点组合成一个节点,或者将小于一定大小的子树转换成普通的旧排序单词列表)。

您可以存储前N个字节(可能是4个?)把一个字符串和一个文件偏移到主文件中,在索引中每隔32条左右记录一次,并进行二进制搜索。然后你可以线性搜索多达32个记录后,一个二进制搜索你非常接近。

可以很容易地生成索引文件,然后可以使用简单的文本编辑器管理主文件。

我建议您看看是否可以使用标准库来实现此目的。也许apachelucene可以用在android手机上。如果是这样,您可以构建一个索引(单词前缀->android sqllite中单词的id)。这里是 a discussion about a kind of algorithm lucene is using .

Stringsearch library

我把它用于我的Android应用程序“Wordlist Pro”,它真的很快。

我也可以这样做(下面是一个预处理文件):

aa - line 1
ab - line 17
.
.
zz - line 299819