发布时间：2022-4-10 分类： 行业资讯
指数在日常生活中非常普遍。例如，图书目录是一种索引结构，旨在让人们更快地找到相关的章节内容。例如，像hao123这样的导航代购源码网站本质上是因特网页面中的索引结构。目的是类似的，以便用户可以尽快找到有价值的分类代购源码网站。
在计算机科学领域，索引也是一种非常常见的数据结构。其基本目的是加快特定应用程序的搜索速度。例如，在数据库中，在许多有效的数据结构中，使用大量索引来提高系统效率。
具体到搜索引擎，索引是最重要的核心技术之一。面对庞大的网页内容，如何快速查找包含用户查询字词的所有网页？倒排索引在其中起着关键作用。本文重点介绍与倒排索引相关的技术。
本文通过介绍简单的示例介绍了与搜索引擎相关的一些基本概念。理解这些基本概念对于理解未来索引的工作机制非常重要。
文字矩阵
单词 - 文档矩阵是一种表达两者之间包含关系的概念模型。图1显示了它的含义。图1中的每一列代表一个文档，每行代表一个单词，tick的位置代表包含关系。
图1：Word-Document Matrix
从肖像，文档的角度来看，每列表示文档中包括哪些单词，例如文档1包含词汇表1和词汇表4，并且不包含其他单词。从水平到字维，每行代表哪些文档包含单词。例如，对于词汇1，词汇1出现在文档1和文档4中，而其他文档不包含词汇1，并且还可以解释矩阵中的其他等级。
搜索引擎的索引实际上是单词 - 文档矩阵的特定数据结构。实现上述概念模型的方法有多种，例如倒排索引，签名文件，后缀树等。然而，实验数据表明，倒排索引是实现单词到文档映射关系的最佳方式，因此本文主要介绍倒排索引的技术细节。
倒排索引的基本概念
以下是反向索引中常用的一些常用术语
文档：通用搜索引擎处理Internet页面，文档的概念更通用，表示以文本形式存在的存储对象。与网页相比，可以将更多形式（如Word，PDF，XML等）称为文档。例如，电子邮件，文本消息或微博也可以称为文档。
文档集合：多个文档的集合称为文档集合。例如，大量互联网页面或大量电子邮件是文档集合的特定示例。
文档编号：在搜索引擎中，文档集合中的每个文档都有一个唯一的内部编号，用作文档的唯一标识符，便于内部处理。每个文档的内部编号称为文档编号。
字数：与文档编号类似，搜索引擎在内部识别具有唯一编号的单词，该单词可用作单词的唯一表示。
反向索引：反向索引是用于实现单词 - 文档矩阵的特定存储形式。通过反转索引，您可以快速获取包含基于单词的单词的文档列表。倒排索引主要由两部分组成：单词字典和倒置文件。
单词词典：搜索引擎的索引单位是一个单词。单词词典是由文档集合中出现的所有单词组成的字符串集合。单词词典中的每个索引项记录单词本身的一些信息和指向反转列表的指针。 。
倒置列表：倒置列表记录了出现单词的所有文档的文档列表以及单词出现在文档中的位置信息。每条记录称为倒置项。根据反转列表，您可以查看哪些文档包含单词。
反转文件：所有单词的反转列表通常按顺序存储在磁盘上的文件中。此文件称为反向文件，反向文件是存储反向索引的物理文件。
这些概念之间的关系可以在图2中清楚地看到。
图2：倒排索引的基本概念示意图
反向索引简单示例
从逻辑结构和基本思想来看，倒排索引非常简单。下面我们通过具体的例子来解释，这样每个人都可以有一个宏观和直接感觉的倒排索引。
假设文档集合包含5个文档，每个文档包含如下图所示的内容。在图3的最左列中是与每个文档相对应的文档编号。我们的任务是为此文档集创建一个倒排索引。
图3：文档集合
中文和英文是不同的语言，单词之间没有明确的分隔符。因此，分词系统首先用于自动将文档剪切成单词序列，从而将每个文档转换为由单词序列组成的数据流。为了便于系统的后续处理，必须为每个不同的单词分配唯一的单词编号，并记录包含该单词的文档。处理完成后，我们可以得到最简单的倒排索引（参见图4）。在图4中，“字ID”列记录对应于每个字的数字，第二列是对应的字，第三列是对应于每个字的反转列表。例如，单词“Google”，其中单词编号为1，反转列表为{1,2,3,4,5}，表示文档集合中的每个文档都包含单词。
图4的反向索引最简单的原因是索引系统只记录哪些文档包含某个单词，实际上，索引系统除此之外还可以记录更多信息。图。图5是相对复杂的倒排索引。与图1所示的基本指标系统相比较。 4，不仅文件号而且字频信息都记录在对应于该词的倒排列表中，也就是说，该词是在某个文件中出现的次数，这个信息记录的原因是因为在计算搜索结果时，词频信息是一个非常重要的计算因子，因此为方便起见，它被记录在反转列表中。在随后的排序期间执行分数计算。在图5所示的例子中，单词“founder”的单词编号为7，相应的反向列表有（3; 1），其中3表示文档编号为3的文档，包含单词，编号1 It表示单词频率信息，即单词在3号文档中仅出现一次，而与其他单词对应的反向列表表示相同的含义。
图4：最简单的倒排索引
图5：带有字频信息的倒置索引
实用的倒排索引也可以记录更多信息。除了记录文档号和字频信息之外，图1所示的索引系统还包括：图6另外记录两种类型的信息，即，对应于每个单词的文档频率信息（图6）。第3列）和文件出现的单词的信息。
图6：带有字频，文档频率和位置信息的倒排索引
文档频率信息表示文档集合中包含特定单词的文档数量。记录该信息的原因与词频信息相同。此信息是搜索结果排名计算中非常重要的因素。关于文档中单词的位置的信息不一定由索引系统记录。它可以包含在实际索引系统中，也可以选择不包含此信息。这是因为搜索系统不需要此信息。位置信息只有在支持短语查询时才会派上用场。
以单词“Ras”为例，单词数为8，文档频率为2，表示整个文档集合中有两个文档包含单词，相应的反向列表为{（3; 1; < 4>;），（5; 1;< 4>）}，这意味着该单词已出现在文档3和文档5中，单词频率为1，并且单词“ldquo; ras”出现在这两个文件中的位置是4，即文件中的第四个单词是“las”。
图6中所示的倒排索引已经是一个非常完整的索引系统。实际搜索引擎的索引结构基本相同。差别只不过是实现上述逻辑结构的具体数据结构。
利用该索引系统，搜索引擎可以容易地响应用户查询，例如用户输入查询词“Facebook”，搜索系统找到倒排索引，从中可以读出包含该词的文档，以及文档提供给用户。搜索结果，并使用词频信息，文档频率信息对这些候选搜索结果进行排序，计算文档与查询之间的相似度，根据相似度得分从高到低对输出进行排序，这是搜索系统的一部分。处理。
起源于短篇小说：辛苦工作后的80后
