现有库
以下是两个现有的解决方案,它们可以完全集成到应用程序中,而无需单独的过程(我相信这两个解决方案都将使用VC++进行编译)。
Xapian
是成熟的,可以做很多你需要的,从索引到排名检索。需要单独的HTML解析,因为afaik不解析HTML(它有一个伴生程序
Omega
,这是索引网站的前端)。
Lucene
是爪哇中的索引/搜索Apache库,具有正式的预发布C版本
lucy
和一个非官方C++版本
CLucene
.
实施信息检索
如果上述选项由于某种原因不可行,下面是关于构建和使用索引的各个步骤的一些信息。定制解决方案可以从简单到非常复杂,这取决于您的应用程序需要什么。我把这个过程分成了5个步骤
HTML处理
文本处理
标引
检索
排名
HTML处理
这里有两种方法
汽提
您提到的页面讨论了一种通常称为剥离(stripping)的技术,该技术涉及删除所有不显示的HTML元素,并将其他元素转换为其显示表单。就我个人而言,我会使用Perl进行预处理,并为生成的文本文件编制索引。但是对于一个集成的解决方案,特别是您希望在其中记录重要性标记(例如
、
)的解决方案,您可能希望扮演自己的角色。
Here is a partial implementation
一个C++解析器例程(出现在
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”、“foobaring”和“foobar”。索引可以单独在根上构建和搜索。词干的两种一般方法是基于词典(从word=>根目录查找)和基于算法。波特算法非常常见,有几种实现,例如
C++ here
或
C here
. 堵塞在
Snowball C library
支持多种语言。
here's one
.
标引
映射字=>页数据结构称为
inverted index
. 它的反转是因为它通常是由page==>单词的前向索引生成的。反向索引通常有两种类型:
反向文件索引
将单词映射到它们出现的每个文档,以及
完全反向索引
将单词映射到它们出现在的每个文档中的每个位置。
重要的决定是使用什么后端进行索引,为了便于实现,有些可能性是:
SQLite
或
Berkly DB
这两种都是带有C++ API的数据库引擎,它们集成到一个项目中,而不需要单独的服务器进程。持久数据库本质上是文件,因此只需更改相关文件就可以搜索多个索引集。使用DBMS作为后端简化了索引创建、更新和搜索。
内存中的数据结构-如果您使用的是不太大的反向文件索引(内存消耗和加载时间),则可以将其实现为
std::map<:string>
使用
boost::serialization
为了坚持。
在磁盘数据结构上——我听说过使用内存映射文件来处理这类事情的快速结果,YMMV。有一个反向的文件索引需要有两个索引文件,一个代表单词
struct {char word[n]; unsigned int offset; unsigned int count; };
,第二个表示(word,document)元组,
unsigned int
s(文件偏移中隐含的字)。这个
offset
是第二个文件中单词的第一个文档ID的文件偏移量,
count
是与该字关联的文档ID数(从第二个文件读取的ID数)。然后,通过将指针指向内存映射文件的第一个文件,搜索将简化为二进制搜索。下面是需要填充/截断单词以获得恒定的记录大小。
索引过程取决于您使用的后端。生成反向文件索引的经典算法(
detailed here
)从阅读每个文档开始,扩展(页面ID、Word)元组列表,忽略每个文档中的重复单词。处理完所有文档后,按单词对列表排序,然后折叠为(word,(page id1,page id2,…)。
这个
mifluz
GNU库实现带存储的反向索引,但不进行文档或查询解析。GPL,所以可能不是一个可行的选择,但它会让您了解支持大量文档的反向索引所涉及的复杂性。
检索
一种非常常见的方法是布尔检索,它只是为分别与或/和联接的每个查询词编制索引的文档的联合/交集。如果文档ID按每个术语的排序顺序存储,那么这些操作是有效的,因此算法
std::set_union
或
std::set_intersection
可以直接应用。
检索上有变化,
wikipedia
有一个概述,但标准布尔值对许多/大多数应用程序都很好。
排名
有许多方法可以对布尔检索返回的文档进行排序。常用的方法都是建立在词袋模型的基础上,即忽略词的相对位置。一般的方法是对每个检索到的文档进行相对于查询的评分,并根据计算出的评分对文档进行排名。有很多得分方法,但一个好的起点是
术语频率反相文件频率
公式。
这个公式背后的思想是,如果一个查询词经常出现在一个文档中,那么该文档的得分应该更高,但是在许多文档中出现的一个词的信息性却较低,因此该词应该被降权。公式是,查询条件i=1..n和文档j
score[j]=对i的求和(单词_freq[i,j]*inv_doc_freq[i])
其中,单词_freq[i,j]是文档j中出现单词i的次数,以及
inv_-doc_-freq[i]=日志(m/doc_-freq[i])
其中m是文档数,doc_freq[i]是包含单词i的文档数。请注意,所有文档中出现的单词不会影响分数。一个更复杂的评分模型被广泛使用
BM25
包括在Lucene和Xapian中。
通常,对特定领域的有效排序是通过试错法来调整的。根据标题/段落上下文调整排名的起始位置可能是根据标题/段落上下文增加单词频率,例如段落为1,顶级标题为10。对于其他一些想法,你可能会发现
this paper
有趣的是,作者根据位置评分调整了BM25排名(这个想法是,靠近文档开头的单词比靠近结尾的单词更相关)。
排名绩效的客观量化是通过精确的回忆曲线或平均精度来获得的,详细的
here
. 评估需要与集合中所有相关文档配对的一组理想查询。
