除此之外,还有其他比这更快速的搜索方式吗?您能从实现的角度详细说明吗?(假设我需要实现它)
为了让人们更容易理解,让我以这种方式表述:
假设我想构建一个搜索应用程序,其搜索操作类似于我们在Windows中使用的搜索操作。
我的问题是,构建这样一个应用程序可能有哪些可行的选项/方法/方式? (哪些比现有的更快。)
(是否可以使用二叉搜索树这种技术?)
在大型语料库上进行全文搜索的基本技术有两种:posting lists和suffix arrays。
Posting lists是(term, document_id)对的列表,可以选择包含文档中的位置信息。如果按term排序或哈希,就可以创建一个高效可搜索的全文索引。
有多种技术可以使posting lists更小,访问更快,更新更快,更加灵活,但有可能会降低准确性。Lucene可能是当今最好的现成posting list文本索引器,与你之前的评论相反,它可以索引PDF、Microsoft Word等文件中的文本。由Thomas Maierhofer链接的Lucene.net项目看起来是一个相当不错的移植,不过你始终会落后于Java版本的最新进展。
对于远超内存大小的语料库,你必须把posting list存储在磁盘上。这就要求使用简单的二叉搜索树来访问它已经不可行了:如果你有十万个文档每个文档都有一万个单词,那么你有十亿个posting,这意味着你的二叉搜索树至少有30层。问题是从根到叶子的路径上的30个节点通常位于磁盘的不同部分,因此磁盘需要查找30次才能找到一个term的posting!这大约需要2.5秒,速度太慢了。
然而,有一种修改过的二叉树数据结构称为“B树”,可以使用。Lucene使用一个类似于B树的简单数据结构,但更容易支持大规模的更新。我在自己的dumbfts项目中编写了一个非常简单的版本,它实现了一个用几页Python编写的全文搜索引擎来搜索我的电子邮件。我每天都在使用它,它是免费软件,并且对我所用的目的来说运行得相当不错,但它并不像Lucene那样是一个世界级的搜索系统。
作为缩小Posting列表以换取精度的例子,《Managing Gigabytes》书(和mg4j项目)有一个名为“签名最小完美哈希表”的数据结构,它实际上并不存储被索引的术语,而只存储它们的哈希值。因此,存在误判的可能性 —— 您必须检索包含该术语的文档,以确认它们确实存在。
后缀数组是一种更紧凑但运行速度略慢的基数树(也称为trie)实现,GLIMPSE 和其他一些程序使用了这种数据结构,但如今它们基本上已经不再使用。 它们具有一些发布列表数据结构中不存在的灵活性 - 例如,它们允许正则表达式搜索和带有拼写错误的搜索,但它们并不像其他技术那样快速。 最近还进行了一些基于后缀数组的 Burrows-Wheeler 变换工作,提供了一种压缩算法,在这种算法中,压缩文件 就是 全文索引! 这种方法最好记录在名为FM 索引 的版本中,虽然我听说可能还有早期版本的技术未经发表。 不过,与上述其他技术不同,我认为当文档是 PDF 文件或类似格式时,该技术实际上并不起作用 - 您仍然可以使用相同的方法提取每个页面的文本版本并对其进行索引,但无法获得压缩原始文档的好处。看看 Lucene。它是一个用于文本(文件)的超快速搜索库。还有可用的Lucene.NET。如果你喜欢自己实现,它是一个很好的起点和基准。
正如你所知,有许多方法可以处理搜索,每种方法都涉及许多不同类型的数据结构。如果你想让我详细阐述某个特定领域,我可以为你做到。
网络上有很多关于全文搜索的研究论文,也有很多源代码。如果你看一下它们,你会发现在现代硬件上使用二叉搜索树不会提供好的结果。二叉搜索树是一种非常特定的数据结构,在具有多级缓存的现代cpu上并不尽可能快。快速的数据结构比2更高的扇出。
此外,这个问题更适合使用(基数)trie。请参见维基百科。
你可以使用Knuth-Morris-Pratt或Boyer-Moore搜索算法,它们非常快速,而且不需要索引。