文本处理，第2部分：OH，倒排索引

这是我的文本处理系列的第二部分。在这篇博客中，我们将研究如何将文本文档存储在可以通过查询轻松检索的表单中。我将使用流行的开源Apache Lucene索引进行说明。

系统中有两个主要的处理流程...

• 文档索引：给定一个文档，将其添加到索引中
• 文档检索：给定查询，从索引中检索最相关的文档。

下图说明了这是如何在Lucene中完成的。

指数结构

文档和查询都以一句话表示。在Apache Lucene中，“文档”是存储和检索的基本单位。“文档”包含多个“字段”（也称为区域）。每个“字段”包含多个“术语”（相当于单词）。为了控制文档在其包含字段中的索引方式，可以用多种方式声明一个字段，以指定是否应该分析它（索引期间的预处理步骤），索引（参与索引）还是存储（如果是它需要在查询结果中返回）。

• 关键字（未分析，索引，存储）
• 未编入索引（未分析，未索引，已存储）
• 未存储（分析，索引，未存储）
• 文本（分析，索引，存储）

倒排索引是存储的核心数据结构。它从术语到文档列表（其中包含该术语）以相反的方式组织。该列表（称为发布列表）按全局排序（通常由文档ID）排序。为了更快地检索，列表不仅仅是一个列表，而是一个跳过列表的层次结构。为了简单起见，我们在随后的讨论中忽略跳过列表。基于Lucene的实现，这个数据结构如下图所示。它以段文件的形式存储在磁盘上，在处理过程中它将被带入内存。

上图仅显示倒排索引。整个指数包含一个额外的正向指数如下。

文档索引

原始格式的文档是从数据适配器中提取的。（这可以使Web API检索某些文本输出，抓取网页或接收HTTP文档上载）。这可以以批处理或在线方式完成。当索引处理开始时，它解析每个原始文档并分析其文本内容。典型的步骤包括...

• 标记文档（分解成文字）
• 小写每个单词（使其不区分大小写，但需要注意名称或缩写）
• 移除停用词（取出“the”，“a”等高频词，但需要小心词组）
• 词干（标准化同一词的不同形式，例如减少“跑”，“跑”，“跑”到“跑”）
• 同义词处理。这可以通过两种方式完成。要么扩大术语以包括它的同义词（即：如果术语是“巨大的”，加上“巨大的”和“大的”），或者将术语缩小到标准化的同义词（即：如果术语是“巨大的”或“巨大的“，将其改为”大“）

此时，文档由多个术语组成。doc = [term1，term2 ...]。可选地，术语可以进一步组合为n-gram。之后，我们计算这个文档的词频。例如，在双向扩展中，文档将变为... doc1 - > {term1：5，term2：8，term3：4，term1_2：3，term2_3：1}我们也可以计算一个“静态分数”基于文档质量的某种度量。之后，我们将文档插入发布列表（如果存在，否则创建一个新的发布列表）为每个条款（所有n元），这将创建倒序列表结构，如上图所示。有一个推动因素可以设置为文档或字段。促进因素有效地增加了有效影响文件或领域重要性的词频。可以通过以下方式之一将文档添加到索引中; 插入，修改和删除。通常情况下，文档将首先添加到内存缓冲区，内存缓冲区组织为RAM中的倒排索引。

• 当这是一个文档插入时，它会通过正常的索引过程（如上所述）来分析文档并在RAM中创建一个反转列表。
• 当这是一个文档删除（客户端请求只包含文档ID）时，它提取正向索引以提取文档内容，然后通过正常索引过程分析文档并构建倒排列表。但在这种情况下，倒排列表中的doc对象被标记为“已删除”。
• 当这是一个文档更新（客户端请求包含修改后的文档）时，它会作为删除操作进行处理，然后进行插入操作，这意味着系统首先从正向索引中获取旧文档，以生成一个标记为“已删除”的节点的倒排列表“，然后从修改后的文档中构建一个新的倒排列表。（例如，如果doc1 =“AB”更新为“AC”，则发布列表将是{A：doc1（删除） - > doc1，B：doc1（删除），C：doc1}。列表将为{A：doc1，B：doc1（已删除），C：doc1}

随着越来越多的文档被插入到内存缓冲区中，它将变满并且将被刷新到磁盘上的段文件。在后台，当M段文件被累积时，Lucene将它们合并成更大的段文件。请注意，每个级别的段文件大小呈指数增长（M，M ^ 2，M ^ 3）。这将每个查询需要搜索的段文件的数量保持在O（logN）复杂度，其中N是索引中文档的数量。Lucene还提供了一个明确的“优化”调用，将所有的段文件合并为一个。

这里我们来详细介绍合并过程，因为发布列表已经按条款垂直排序，并且由doc ID水平排序，合并两个段文件S1，S2基本上如下

• 按照排序的术语顺序从S1和S2一起走过发布列表。对于那些非常见术语（出现在S1或S2中的一个中，但不是两者中的术语），将发布列表写出到新的分段S3。
• 在我们找到一个通用术语T之前，我们合并这两个部分中的相应发布列表。由于这两个列表均按doc ID排序，因此我们只需沿着这两个发布列表将doc对象写入新的发布列表。当两个发布列表具有相同的文档时（文档被更新或删除时就是这种情况），我们根据时间顺序选择最新的文档。
• 最后，将计算每个发布列表（相应术语的）的文档频率。

文件检索

考虑一个文档是一个向量（每个词作为分离的维度，相应的值是tf-idf值），查询也是一个向量。文档检索问题可以定义为查找与查询匹配的top-k最相似的文档，其中相似性定义为文档向量与查询向量之间的点积或余弦距离。tf-idf是一个归一化频率。TF（术语频率）表示术语在文档中出现多少次（通常是应用平方根或对数等压缩函数）。IDF是文档频率的倒数，如果该词出现在许多其他文档中，则用它来折扣重要性。TF-IDF有许多变种，但通常它反映了文档（或查询）与每个词的关联强度。给定包含术语[t1，t2]的查询Q，这里是我们如何获取相应的文档。一种常用的方法是“我们一次性的文件方法”，我们在这里同时遍历t1，t2的发布列表（而不是我们在开始发布列表之前遍历整个发布列表t1的“一次一词”方法的t2）。遍历过程如下所述...

• 对于查询中的每个术语t1，t2，我们标识所有相应的发布列表。
• 我们同时走每个发布列表以返回一系列文档（按doc ID排序）。请注意，每个退货凭证至少包含一个字词，但也可以包含多个字词。
• 我们计算查询到文档向量的点积的动态分数。请注意，我们通常不涉及查询的TF / IDF（这很简短，我们不关心每个术语的频率）。因此，我们可以在划分IDF分数（在每个发布列表的头部）之后，计算具有匹配项的发布列表的所有TF分数的总和。Lucene还支持查询级别提升，其中一个提升因子可以附加到查询条件。升压因子将相应地乘以项频率。
• 我们还查找纯粹基于文档（而不是查询）的静态分数。总分是静态和动态分数的线性组合。
• 虽然我们在上面的计算中使用的分数是基于计算查询和文档之间的余弦距离，但我们并不仅限于此。我们可以插入任何对域有意义的相似函数。（例如，我们可以使用机器学习来训练模型来评分查询和文档之间的相似度）。
• 在计算总分后，我们将文档插入到保存topK得分文档的堆数据结构中。

这里将整个发布列表遍历。如果发布列表很长，响应时间延迟将会很长。有没有办法让我们不必遍历整个列表，仍然能够找到大概的顶级K文件？我们可以考虑一些策略。

1. 静态分数发布顺序：请注意，发布列表是基于全局顺序排序的，这种全局排序在遍历期间提供了单调递增的文档ID，这对于支持“一次一个文档”遍历很重要，因为不可能访问同样的文件。但是，这种全局排序可能是非常随意的，并不一定是文档ID。因此，我们可以根据全球性的静态评分（例如文档质量指标）来选择订单。我们的想法是，我们遍历静态分数减少幅度的发布列表，所以我们更有可能访问总分（静态+动态分数）较高的文档。
2. 削减频繁的条款：我们不遍历其术语IDF值较低的发布列表（即：该词出现在许多文档中，因此发布列表往往很长）。这样我们可以避免遍历长的发布列表。
3. TopR列表：对于每个发布列表，我们创建一个额外发布列表，其中包含原始列表中具有最高TF（词频）的前R个文档。当我们执行搜索时，我们在此topR列表中执行搜索，而不是原始发布列表。

由于我们有多个倒排索引（在内存缓冲区以及不同级别的段文件中），我们需要结合它们的结果。如果termX出现在segmentA和segmentB中，则会选取更新的版本。新鲜版本的确定如下：具有较低等级（较小尺寸）的部分将被视为更新鲜。如果两个分段文件处于同一级别，则数字较高的那个文件更新。另一方面，IDF值将是段文件中每个发布列表的相应IDF的总和（如果同一文档已更新，则该值稍微偏离，但这种差异可忽略不计）。但是，合并多个段文件的处理会导致文档检索中的处理开销。Lucene提供了一个明确的“优化”

分布式索引

对于大型语料库（如Web文档），索引通常分布在多台机器上。有两种分配模式：术语分区和文档分区。

在文档分区中，文档随机分布在构建索引的不同分区中。在术语分区中，术语分布在不同的分区上。我们将讨论文档分区，因为它更常用。分布式索引是由Lucene构建的其他技术提供的，例如ElasticSearch。典型设置如下...在此设置中，机器按列和行组织。每列表示文档的分区，而每行表示整个语料库的副本。

在文档索引期间，首先随机选择一排机器并分配用于构建索引。当一个新文档被抓取时，随机挑选一个来自所选行的列机器来承载文档。该文档将被发送到构建索引的这台机器。更新后的索引稍后将传播到其他行副本。在文件检索过程中，首先选择一排副本机器。然后客户端查询将被广播到选定行的每一列机器。每台机器将在其本地索引中执行搜索，并将TopM元素返回给查询处理器，该查询处理器将在返回给客户端之前合并结果。请注意，K / P <M <K，其中K是客户期望的TopK文档，P是机器的列数。注意M是一个需要调整的参数。这个分布式索引的一个注意事项是，由于发布列表横跨分区横向分割，所以我们丢失了IDF值的全局视图，否则机器无法计算TF-IDF分数。有两种方法可以减轻...

1. 不做更改：在这里我们假设文档均匀分布在不同的分区上，所以本地IDF代表了实际IDF的一个很好的比例。
2. 额外的：在第一轮中，查询被广播到返回其本地IDF的每一列。查询处理器将收集所有IDF响应并计算IDF的总和。在第二轮中，它将查询连同IDF总和一起广播给每一台机器，这将根据IDF总和计算本地分数。