创建和使用HTML全文搜索索引(C++)

Question

我需要为HTML页面集合创建搜索索引.

我根本没有实现搜索索引的经验,所以任何一般信息如何构建一个,存储什么信息,如何实现高级搜索,如"整个短语",结果排名等.

我并不害怕自己构建它,虽然我很乐意重用现有的组件(或者使用一个开始使用原型).我正在寻找一个可以从C++访问的解决方案,最好不需要在运行时进行额外的安装.内容是静态的(因此聚合搜索信息是有意义的),但搜索可能必须累积来自多个此类存储库的结果.

---

不过,我可以做一些有根据的猜测:word ==> pages为所有(相关的)单词创建一个地图,可以通过promincence(h1> h2> ...> <p>)和接近顶部来为映射分配排名.高级搜索可以建立在最重要的是:搜索词组"homo sapiens"可以列出包含所有页面"homo"和"sapiens",然后扫描所有的网页返回,他们一起出现的位置.然而,有很多有问题的场景和未解决的问题,所以我正在寻找对应该是大量现有工作的参考,这些工作以某种方式逃脱了我的谷歌.

---

[编辑赏金]
我发现的最好的资源是这个以及那里的链接.我确实有一个实验系统的实施路线图,但是,我仍然在寻找:

• 有关索引创建和各个步骤的参考资料
• 各个步骤的可用实现
• 可重用的实现(具有上述环境限制)

Answer 1

该过程通常称为信息检索.您可能会发现这本在线书籍很有帮助.

现有图书馆

以下是两个现有的解决方案,可以完全集成到应用程序中,而无需单独的流程(我相信它们都将使用VC++进行编译).

Xapian已经成熟,可以完成您所需的大部分工作,从索引到排名检索.需要单独的HTML解析,因为,AFAIK,它不解析html(它有一个配套程序Omega,它是索引网站的前端).

Lucene是Java中的索引/搜索Apache库,具有官方预发行版C版本lucy和非官方C++版本CLucene.

实施信息检索

如果由于某种原因上述选项不可行,这里有一些关于构建和使用索引的各个步骤的信息.根据您的应用需求,定制解决方案可以从简单到非常复杂.我把这个过程分成了5个步骤

1. HTML处理
2. 文字处理
3. 索引
4. 恢复
5. 排行

HTML处理

这里有两种方法

• 剥离 您引用的页面讨论了一种通常称为剥离的技术,它涉及删除所有不显示的html元素并将其他元素转换为其显示形式.就个人而言,我使用perl进行预处理并索引生成的文本文件.但对于集成解决方案,尤其是您想要记录重要性标记的解决方案(例如<h1>,<h2>),您可能想要自己的角色. 下面是部分实现一个C++剥离例行的(出现在C++中思考,本书的最终版本在这里),你可以打造而成.

• 从解析中解析复杂程度是html解析,这有助于记录重要性标记.但是,很难找到一个好的C++ HTML解析器.一些选项可能是htmlcxx(从未使用它,但是活跃且看起来很有前途)或hubbub(C库,NetSurf的一部分,但声称是可移植的).

  如果您正在处理XHTML或愿意使用HTML-to-XML转换器,则可以使用许多可用的XML解析器之一.但同样,HTML-to-XML转换器很难找到,我所知道的唯一一个是HTML Tidy.除了转换为XHTML之外,它的主要目的是修复丢失/损坏的标签,并且它有一个可能用于将其集成到应用程序中的API.鉴于XHTML文档,有许多优秀的XML解析器,例如Xerces-C++和tinyXML.

文字处理

至少对于英语而言,将文本处理为单词非常简单.但是,在涉及搜索时会出现一些复杂情况.

• 停用词是先验已知的词,不能在集合中的文档之间提供有用的区分,例如文章和命题.通常,这些单词不会从查询流中编入索引和过滤.有许多在网络上可用的停用词列表,比如这一个.

• 词干包括预处理文档和查询以识别每个单词的根,以更好地概括搜索.例如,搜索"foobarred"应该产生"foobarred","foobarring"和"foobar".可以仅在根上构建和搜索索引.阻塞的两种通用方法是基于字典(从word ==> root查找)和基于算法.波特算法是很常见的几个实现,这些实现,例如C++这里还是这儿用.Snowball C库中的词干支持多种语言.

• Soundex编码 一种使搜索对拼写错误更具鲁棒性的方法是使用语音编码对单词进行编码.然后,当查询出现语音错误时,它们仍会直接映射到索引字.有很多实现,这是一个.

索引

地图字==>页面数据结构称为倒排索引.它倒置是因为它经常从页面的正向索引生成==>单词.反向索引通常有两种形式:反向文件索引,它将单词映射到它们出现的每个文档,以及完整的反向索引,它将单词映射到它们出现的每个文档中的每个位置.

重要的决定是用于索引的后端,一些可能性是,为了易于实现:

1. SQLite或Berkly DB - 这两者都是带有C++ API的数据库引擎,它们集成到项目中而无需单独的服务器进程.持久性数据库本质上是文件,因此只需更改关联文件即可搜索多个索引集.使用DBMS作为后端简化了索引创建,更新和搜索.
2. 在内存数据结构中 - 如果你使用的反向文件索引不是非常大(内存消耗和加载时间),这可以实现为std::map<std::string,word_data_class>,使用boost :: serialization进行持久化.
3. 在磁盘数据结构上 - 我听说过使用内存映射文件这种事情的极快结果,YMMV.具有反向文件索引将涉及具有两个索引文件,一个表示具有类似内容的单词struct {char word[n]; unsigned int offset; unsigned int count; };,并且第二个表示(单词,文档)元组仅具有unsigned ints(文件偏移中隐含的单词).的offset是该文件用于第一文档ID用于在所述第二文件中的字偏移量,count是文件ID的数量关联与字(从第二文件中读取的ID号码).然后,搜索将通过第一个文件减少到二进制搜索,并使用指向内存映射文件的指针.缺点是需要填充/截断单词以获得恒定的记录大小.

索引的过程取决于您使用的后端.生成反向文件索引的经典算法(在此详述)首先阅读每个文档并扩展(页面ID,单词)元组列表,忽略每个文档中的重复单词.处理完所有文档后,按字词对列表进行排序,然后折叠为(word,(page id1,page id2,...)).

该mifluz GNU库实现倒排索引W /存储,但没有文件或查询解析.GPL,因此可能不是一个可行的选项,但会让您了解支持大量文档的倒排索引所涉及的复杂性.

恢复

一种非常常见的方法是布尔检索,它只是为每个与或者和/或连接的查询词索引的文档的并集/交集.这些操作是有效的,如果该文档ID存储在排序的顺序为每个术语,以便像算法std::set_union或std::set_intersection可以直接应用.

检索有变化,维基百科有一个概述,但标准布尔值适用于许多/大多数应用程序.

排行

有许多方法可以对布尔检索返回的文档进行排名.常用的方法是基于单词包模型,这意味着单词的相对位置被忽略.一般方法是相对于查询对每个检索到的文档进行评分,并基于其计算得分对文档进行排名.有许多评分方法,但一个好的起点是术语频率 - 逆文档频率公式.

这个公式背后的想法是,如果一个查询词在文档中经常出现,那么该文档应该得分更高,但是在许多文档中出现的词的信息量较少,所以这个词应该加权.公式是,在查询项i = 1..N和文档j上

得分[j] = sum_over_i(word_freq [i,j]*inv_doc_freq [i])

其中word_freq [i,j]是文档j中单词i的出现次数,并且

inv_doc_freq [i] = log(M/doc_freq [i])

其中M是文档数,doc_freq [i]是包含单词i的文档数.请注意,所有文档中出现的单词都不会对分数产生影响.更广泛使用的更复杂的评分模型是BM25,它包含在Lucene和Xapian中.

通常,通过反复试验来获得特定域的有效排名.通过标题/段落上下文调整排名的起点可以是基于标题/段落上下文为单词膨胀word_freq,例如1表示段落,10表示顶级标题.对于一些其他的想法,你可能会发现本文有趣,在这里笔者调整BM25排名位置得分(的想法是,话更接近文档的开头比向着终点的话更相关).

排序性能的客观量化是通过精确回忆曲线或平均精度得到的,在此详述.评估需要一组理想的查询,并与集合中的所有相关文档配对.