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

Question

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

我完全没有实现搜索索引的经验，因此任何关于如何构建索引，存储哪些信息，如何实现高级搜索(例如“整个短语”，结果排名等)的一般信息。

我不害怕自己构建它，尽管我很乐意重用现有的组件(或使用一个组件来开始使用原型(prototype))。我正在寻找一种可从C++访问的解决方案，最好在运行时不需要其他安装。内容是静态的(因此汇总搜索信息很有意义)，但是搜索可能必须累积来自多个此类存储库的结果。

不过，我可以做出一些有根据的猜测:为所有(相关)单词创建一个映射word ==> pages，可以通过突出程度(h1> h2> ...> <p>)并靠近顶部来为映射分配一个等级。可以在此基础上进行高级搜索:搜索短语"homo sapiens"可以列出包含"homo"和"sapiens"的所有页面，然后扫描所有返回的页面以查找它们一起出现的位置。但是，存在许多有问题的场景和 Unresolved 问题，因此我正在寻找对应该以某种方式逃避我的Google-fu的大量现有工作的引用。

[赏金编辑]
到目前为止，我发现的最好的资源is this和那里的链接。
我确实有一个实验系统的实现路线图，但是，我仍在寻找:

有关索引创建和各个步骤的引用资料

各个步骤的可用实现

可重用的实现(具有上述环境限制)

Answer 1

此过程通常称为information retrieval。您可能会发现this online book很有帮助。

现有图书馆

这里有两个现有解决方案，它们可以完全集成到应用程序中，而无需单独的过程(我相信两者都可以使用VC++进行编译)。

Xapian很成熟，可以完成从索引到排名检索的所有所需工作。需要单独的HTML解析，因为AFAIK不会解析html(它有一个伴随程序Omega，它是索引网站的前端)。

Lucene是Java中的索引/搜索Apache库，带有正式的预发行C版本lucy和非官方的C++版本CLucene。

实现信息检索

如果由于某些原因上述选项不可行，则以下是有关构建和使用索引的各个步骤的信息。定制解决方案可以从简单到非常复杂，具体取决于您对应用程序的需求。我将过程分为5个步骤

HTML处理

文本处理

索引

检索

排名

HTML处理

这里有两种方法

剥离您所引用的页面讨论了一种通常称为剥离的技术，该技术涉及删除所有不会显示的html元素，并将其他html元素转换为它们的显示形式。就个人而言，我将使用perl进行预处理并为生成的文本文件建立索引。但是对于集成解决方案，尤其是您要记录重要性标签(例如

，

)的集成解决方案，您可能想扮演自己的角色。您可以从中构建的C++剥离例程的Here is a partial implementation(出现在《 C++中的思想》，这是书here的最终版本)中。

解析 html解析使剥离的复杂性提高了一点，这将有助于您记录重要性标签。但是，一个好的C++ HTML解析器是hard to find。一些选项可能是htmlcxx(从未使用过，但是活跃并且看起来很有希望)或hubbub(C库，它是NetSurf的一部分，但声称是可移植的)。

如果您正在使用XHTML或愿意使用HTML到XML转换器，则可以使用许多可用的XML解析器之一。但是同样，很难找到HTML到XML的转换器，我唯一知道的就是HTML Tidy。除了转换为XHTML之外，它的主要目的是修复丢失/损坏的标记以及has an API，该标记可能用于将其集成到应用程序中。给定XHTML文档，有很多不错的XML解析器，例如Xerces-C++和tinyXML。

文字处理

至少对于英语而言，将文本转换为单词非常简单。但是，涉及搜索时会带来一些麻烦。

停用词是已知词，不会在集合中的文档(例如文章和命题)之间提供有用的区分。通常，这些词不会从查询流中索引和过滤。网络上有很多停用词列表，例如one。

词干涉及预处理文档和查询，以识别每个单词的词根，以更好地概括搜索。例如。搜索“foobarred”应产生“foobarred”，“foobarring”和“foobar”。可以仅在根目录上建立和搜索索引。阻止词干的两种通用方法是基于字典的(从单词==>根查找)和基于算法的。波特算法非常普遍，并且有几种实现方式，例如C++ here或C here。 Snowball C library中的词干支持多种语言。

Soundex encoding 一种使搜索对拼写错误更强大的方法是使用语音编码对单词进行编码。然后，当查询出现语音错误时，它们仍将直接映射到索引的单词。 here's one周围有很多实现。

索引编制

映射词==>页面数据结构称为 inverted index。之所以倒转，是因为它通常是从页面==>单词的前向索引生成的。倒排索引通常有两种形式:倒排文件索引(将单词映射到它们所在的每个文档)和完整倒排索引(将单词映射到它们所在的每个文档的每个位置)。

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

SQLite或Berkly DB-两者都是具有C++ API的数据库引擎，这些引擎已集成到项目中，而无需单独的服务器进程。永久数据库本质上是文件，因此只需更改关联文件即可搜索多个索引集。将DBMS用作后端可以简化索引的创建，更新和搜索。

在内存数据结构中-如果您使用的反向文件索引不是很大(内存消耗和加载时间)，则可以将其实现为std::map<std::string,word_data_class>，并使用boost::serialization进行持久化。

在磁盘数据结构上-我听说过使用内存映射文件处理类似YMMV这样的结果非常快。具有反向文件索引将涉及具有两个索引文件，一个索引文件表示带有struct {char word[n]; unsigned int offset; unsigned int count; };之类的单词，第二个索引文件表示仅带有unsigned int s(文件偏移量中隐含的单词)的元组。 offset是第二个文件中单词的第一个文档ID的文件偏移量，count是与该单词相关联的文档ID的数量(要从第二个文件读取的ID的数量)。然后，搜索将减少为使用指针进入内存映射文件的第一个文件进行二进制搜索。缺点是需要填充/截断单词以获得恒定的记录大小。

建立索引的过程取决于您使用的后端。生成反向文件索引( detailed here)的经典算法始于阅读每个文档并扩展(页面ID，单词)元组列表，而忽略每个文档中的重复单词。处理完所有文档后，按单词对列表进行排序，然后折叠为(word，(页面ID1，页面ID2，...)。

mifluz gnu库实现带存储的倒排索引，但是没有文档或查询解析。 GPL可能不是一个可行的选择，但是会让您了解支持大量文档的反向索引所涉及的复杂性。

恢复

bool 检索是一种非常常见的方法，它只是为分别用或/和连接的每个查询词索引的文档的并集/交集。如果将文档ID按术语的排序顺序存储，则这些操作非常有效，因此可以直接应用 std::set_union或 std::set_intersection之类的算法。

检索方面有很多变化， wikipedia进行了概述，但是标准 bool 值对许多应用程序都适用。

排行

有许多方法可以对 bool 检索返回的文档进行排名。常用的方法是基于单词袋模型，这意味着单词的相对位置被忽略。通用方法是对每个检索到的文档相对于查询进行评分，并根据它们的计算得分对文档进行排名。计分方法很多，但是术语“频率反文档频率”是一个很好的起点。

该公式背后的思想是，如果一个查询词在文档中频繁出现，则该文档的得分应更高，但是在许多文档中出现的单词的信息性较差，因此应降低该单词的权重。根据查询条件，公式为i = 1..N和文档j

分数[j] = sum_over_i(word_freq [i，j] * inv_doc_freq [i])

其中word_freq [i，j]是单词j在文档j中的出现次数，以及

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

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

通常，通过反复试验进行调整，可以获得特定域的有效排名。通过标题/段落上下文调整排名的起始位置可以是基于标题/段落上下文的单词膨胀word_freq，例如1代表段落，10代表顶层标题。对于其他一些想法，您可能会发现 this paper很有趣，其中作者调整了BM25排名以进行位置评分(这种想法是，靠近文档开头的单词比指向末尾的单词更相关)。

等级表现的客观量化是通过精确召回曲线或平均平均精确度 here获得的。评估需要一组理想的查询，并与该组中的所有相关文档配对。