索引算法来开发像谷歌桌面搜索这样的应用程序？

Question

我想开发类似谷歌桌面搜索的应用程序，我想知道我应该使用哪些索引技术/算法，这样我就可以获得非常快的数据检索。

Answer 1

用于在bzip2中压缩数据的Burrows-Wheeler变换可用于使文本的子串搜索成为一个恒定的时间函数。

http://en.wikipedia.org/wiki/Burrows-Wheeler_transform

我还没有在网上看到简单的介绍，但这里有很多细节：

http://www.ddj.com/architect/184405504

Answer 2

通常，您需要的是一个Inverted Index。您可以自己建立索引，但这需要做大量的工作--您需要处理stemming、stop words、扩展发布列表以包括文档中的职位，以便您可以处理多个单词查询，等等。然后，您需要存储索引，可能存储在磁盘上的B-Tree中-或者您可以使用现有的数据库作为磁盘存储，例如BDB，使您的工作变得更容易。您还需要编写一个查询规划器来解释用户查询、执行query expansion并将其转换为一系列索引扫描。维基百科上关于Search Engine Indexing的文章也很好地概述了所有的挑战。

或者，您可以利用现有的工作并使用现成的全文索引解决方案，如Apache Lucene和Compass (构建于Lucene之上)。这些工具几乎可以处理上面详细介绍的所有内容(甚至更多)，这使得您可以编写工具来构建和更新索引(通过将所有文档提供给Lucene )，以及允许用户搜索索引的UI。