Pal*_*Dot 8 .net filesystems search full-text-search data-structures
我不知道他们在普通的Windows搜索中使用了什么.但是有一种技术可以让你立刻使用文件索引,然后再使用索引来加快搜索速度.(例如Windows搜索4.0)
除此之外还有其他方法可以加快搜索速度吗？你能从实施的角度详细说明吗？(假设我可能需要实现它)
为了简化理解,让我这样说:
假设我想构建一个搜索应用程序,它执行类似于我们在windows中使用的搜索操作.
我的问题是,有哪些可用的选项/方法/方法可用于构建此类应用程序？(并且比现有的更快.)
(可以使用二叉搜索树类技术吗？)
Kra*_*ker 22
基本上有两种技术用于对大型语料库进行全文搜索:发布列表和后缀数组.
发布列表是(term,document_id)对的列表,可选地具有文档中的位置.如果您按术语对其进行排序或散列,则可以使用高效可搜索的全文索引.
有各种技术可以使发布列表更小,访问更快,更新更快,更灵活,有些以牺牲准确性为代价.Lucene可能是目前最好的现成的基于发布列表的文本索引器,并且(与之前的评论相反)它可以索引PDF,Microsoft Word等文件中的文本.由Thomas Maierhofer链接的Lucene.net项目看起来是一个非常合理的端口,当然,你总是会落后于Java版本的前沿.
对于比内存大得多的语料库,您几乎必须将发布列表存储在磁盘上.这有碍于使用一个简单的二叉搜索树来访问它:如果你有每万个字十万的文档,你有十亿的贴子,这意味着你的二叉搜索树有30最小深度与麻烦的是从树的根到叶子的路径上的30个节点通常位于磁盘的不同部分 - 因此磁盘必须寻找30次才能找到一个术语的发布!这大概是2½秒,这非常慢.
但是,存在称为"B树"的二叉树数据结构的修改版本,其可以工作.Lucene使用的简单数据结构很像B树,但更容易支持大量更新.我在自己的dumbfts项目中编写了一个非常简单的相同数据结构版本,它在几页Python中为我的电子邮件实现了一个全文搜索引擎.我每天都使用它,它是免费软件,它对我使用它的效果非常好,但它并不是像Lucene这样的世界级搜索系统.
作为使置入列表的准确性成本较小的一个例子,管理千兆字节书(和MG4J项目)有一个数据结构称为"签署最小完美哈希表",这实际上并没有被存储索引的术语-只是他们的哈希.因此,假阳性的可能性很小 - 您必须检索据称包含该术语的文档,以确认它们确实存在.
后缀数组是一个更紧凑和稍慢版本的基数树(又名尝试),由GLIMPSE和其他一些程序实现,但它们现在基本上已经不再使用了.它们具有发布列表数据结构中不存在的一些灵活性 - 例如,它们允许使用拼写错误进行正则表达式搜索和搜索,但它们并不是那么快.最近有一些Burrows-Wheeler变换工作,它基于后缀数组,提供压缩算法,其中压缩文件是全文索引!最好的文档版本被称为FM索引,虽然我听说有该技术的旧版本,可能未发表.不同于上述的其它技术,不过,我觉得这个时候的文件是PDF文件或类似的东西不实际工作-你仍然可以使用提取的每一页和索引该文本版本的相同的方法,但你不没有压缩原始文档的好处.
我的熟人蒂姆在2003年写了一篇关于搜索的非常好的系列博客文章,这些文章仍然非常棒.他们更深入地介绍了这些东西(除了最近的发展).
拉维:这是你要找的那种信息吗？
编辑:谢谢你修改我的格式,马丁!
Tho*_*fer 14
看看Lucene吧.它是文本(文件)的超快速搜索库.还有Lucene.NET可用.如果您想自己实现它,那么它是您实现的良好起点和基准.