嗨，用户名！ 每天我们都面临着各种数据的搜索。 现在，几乎每个包含大量信息的网站都可以进行搜索。 搜索可以在家用计算机，手机，各种软件中进行。 当然，如果您向任何开发人员询问技术方面的搜索，elasticsearch，lucene或sphinx都会立即浮现。 今天，我想与您一起进行全文搜索的“内幕”，并使用hh.ru的示例找出其工作原理的第一近似值。
免责声明：本文并不是唯一的真实观点，并且仅作为介绍文本搜索工作以及实现其各个部分的一些选择的入门点。如果您查看搜索的详细信息，那么除了搜索字符串形式中的明显部分之外，您还可以看到更多内容：
- 提示（她建议）
- 搜索结果计数器（counter），
- 各种类型的排序（sort），
- 构面-文档的分组特征，例如空缺所在的地铁，还执行过滤器（过滤器）的功能，
- 同义词
- 分页
- 摘录（snippet）-发行中文档的简短描述，
- 等
而所有这一切都有一个目的-满足用户对尽快找到正确信息的需求。 例如，过滤对于缩小搜索结果的范围很重要，在我们的情况下，它可能是按候选人的经历，位置或职业进行过滤的过滤条件。 构面有助于显示每个薪金范围中的职位空缺。 用同义词补充查询和文档也很重要，这样，在“ java开发人员”的请求下，他们可以找到“ java开发人员”文档。
除了搜索本身之外，总是有很多组件可以使用户的生活变得更轻松：负责纠正错误的监护人，或者与搜索栏交互时会提示更合适查询的最敏感的人。 在某些情况下，重新制定请求很重要。 例如，将请求的一部分移至过滤器：可以从城市中将“莫斯科程序员”请求中的莫斯科取出到过滤器中。
1.基本
现在到了重点。 搜索本身分为两个大阶段：
- 索引（处理文档并根据特殊的索引结构对其进行布局，以便您随后可以快速执行搜索本身），
- 搜索（应用过滤器，布尔搜索，排名等）。
1.1。 索引编制
轻微的抒情偏离。 此外，我将介绍术语的概念-因为习惯上称呼索引和查询的最小单位。 这是将存储在索引字典中的单位。 它可以是简化为正常单词形式或基数，数字，电子邮件，字母n-gram或其他形式的单词。 通常，术语包括对其进行索引或在其中进行搜索的字段。
首先，您需要将输入文档变成一组术语并过滤掉停用词。 它们就像是经常出现的单词-介词，连词，感叹词和其他事物，例如我们不想搜索的特殊字符。 为了使搜索使用不同的单词形式，在索引过程中，我们通常会将所有单词带入某种基本状态。 通常使用以下两种程序之一：词干-隔离单词基础的过程（开发->开发），或词根化-将单词恢复为正常形式的过程（技能->技能）。
1.2索引结构
表示索引的最流行方法是倒排索引。 实际上，这是一种哈希表，其中的键是术语，而值是其中存在该术语的文档列表（通常是称为发帖列表的文档ID列表）。 通常，倒排索引由两部分组成-词典（术语词典）和每个术语的文档列表（发布列表）：
此外，索引可能包含有关文档中术语位置的信息（位置索引），当在一定距离（尤其是短语查询）中搜索术语时，这对术语频率很有用，这将有助于排名和构建查询计划。 但是下面有更多内容。
1.2.1术语词典
该词典存储索引中存在的所有术语，旨在快速查找到文档列表的链接。 有几种存储词典的选项：
- 哈希表，其中术语是关键字，值是指向该术语文档列表的链接。
- 您可以通过二进制搜索进行搜索的有序列表。
- 前缀树（trie）。
最佳方法是最后一个选择，因为 它有几个优点。 首先，在大量术语上，前缀树将占用更少的内存，因为前缀的重复部分将仅存储一次。 其次，我们立即有机会提出前缀请求。 第三，可以通过组合非分支部分来压缩这样的树。
当然，前缀树可能不是唯一的用于在索引中存储术语的结构。 例如，后缀树也可能在附近，这反过来对于具有小丑的查询（形式为po * sql的查询）将更为最佳。
1.2.2发布清单
文档列表是文档标识符的有序列表，允许对其进行一些优化。 通常，它不仅自身存储该词出现的文档列表，而且还存储该词出现的位置（张贴）。 这可以立即解决多个问题：我们立即知道一个单词在文档中出现了多少次，我们可以在术语之间以一定距离进行短语和查询，一次越过多个文档列表并查看术语的位置。
例如，在该列表中，
标题为第6个文档中的术语
scala ，该单词出现4次，分别位于位置2、15、18和25。
1.2.3具有多个字段的文档
大多数文档至少由文档名称及其主体组成，由多个字段组成。 这在搜索文档的各个部分时以及排序时该术语显着时（例如，可以将标题中出现的术语视为更重要）会有所帮助。
另外，在索引中，通常不仅可以存储文本字段，还可以存储文档的符号，一些数值等，索引中的存储通常采用{field-term}的形式。
例如，如果您有空缺，那么它将同时具有多个字段：名称，描述，公司，薪资，城市和必要的经验。 这是必要的，以便用户不仅可以方便地按公司的名称和文字进行搜索，还可以按薪水和工作经验进行过滤，查看所在城市和邻近城市有多少空缺职位，甚至可以搜索特定公司的空缺职位。
1.3索引压缩与优化
工作速度对于搜索很重要，因此，大多数索引搜索操作通常在RAM中执行。 为此，对索引进行多种优化非常重要，这将使其适合有限的内存大小。 除此之外，通常还会应用许多优化，这些优化使您可以在搜索时以更高的速度移动索引，从而跳过不必要的部分。
1.3.1增量压缩
由于我们记得按术语排列的文档列表（也称为发布列表）是有序的，因此如何压缩它的第一个想法是制作一个ID偏移量的列表，而不是相对于先前文档具有ID的列表。 在6个标识符的特定列表上，它看起来像这样：
因此，在列表中移动时，我们将始终根据先前获得的值来计算当前标识符。 例如，对于第二个偏移量3，我们将第一个值2加到ID 5，将第三个值4加5，得到9依此类推。 对于大量文档，此方法非常有效，特别是与另一种压缩方法（记录可变格式数字）结合使用时。
1.3.2 VarByte和VarInt
这是一种将每个单独的列表项存储在内存中的方法，以便占用最少的空间。 例如，如果前三个偏移量仅适合1个字节，则无需占用更多空间。 考虑到我们的列表不包含id文档，而是delta，压缩将非常有效。 在此数字表示中，每个字节的第一位是标志，指示当前数字的表示是否在此字节上结束。
如果字节0的第一位是数字的最后一个字节，如果1不是。
1.3.3跳转列表/跳转表
跳过列表是一种用于快速浏览特定术语的文档列表，跳过列表中不必要部分的结构之一。 这个想法是在列表本身的前面在磁盘上存储到列表中远方元素的链接，因为压缩后我们无法说出100或200文档的确切位置。 例如，当查询两个词时，这很方便，其中一个词经常出现，而第二个词则很少，相反，文件列表仅以第200个文件ID开头。 然后，如果在第一个列表中有一个带有通行证的列表，我们可以节省移动时间并立即跳过不必要的标识符块。
1.4要求
1.4.0词条查询
最简单的请求类型，我们只需要查找适当的文档列表并按排名排序即可发布文档。
例如，通过这种方式，我们找到了
java的职位列表：
1.4.1布尔查询（与非）
在我们到处可见的信息检索中，布尔搜索是最重要的部分之一。 整个布尔搜索基于AND，OR和NOT的组合。 例如，当我们用两个词搜索查询：
java android时 ，实际上，通过简单的搜索，它将转换为
java AND android 。 这意味着我们要查找包含两个单词的所有文档。
值得一提的是您如何在文档列表中移动。 由于每个术语的文档列表都是经过排序的，因此通常有两种方法可以遍历列表：依次遍历文档，逐个传递文档或直接移至特定文档，跳过不需要的文档（例如，当第一个列表小得多时） ，我们不需要浏览第二个列表中的大量文档）。 在这种情况下，我们首先使用第二个列表的跳过指针中的指针，使其尽可能靠近所需的文档ID，然后线性移动。
在搜索时，会发生以下情况：在java和android术语的索引中是文档列表，然后在它们上进行交集-也就是说，我们找到包含这两个术语的文档。 通过此搜索，可以使用两种遍历列表的方法来更快地穿越。
对于形式为Java OR scala的OR查询，我们需要查找包含至少一个术语的所有文档，情况就有所不同-在这里，我们不需要将该术语一次出现在所有文档列表中。 但是有些查询带有多个OR运算符，那么可能会出现最小匹配数的条件，例如，可能存在一个Java OR scala OR cotlin OR clojure查询，其中至少有两个匹配项，然后我们应该显示所有包含至少两个查询词的文档。
在这种情况下，堆的工作效率最高。 我们可以在其中存储指向每个列表的迭代器的链接，并获取恒定时间的最小元素。 取最小元素之后，我们从堆中删除迭代器，向前迈出一步，然后将其再次添加到堆中。 您可以分别存储要添加到结果和计数器中的当前候选者，他满足的次数以及当候选者与堆中的最小元素不同的那一刻，看看是否在操作中忽略了最小匹配项。 然后将其添加到结果的最终列表中，或者丢弃该文档。
1.4.2前缀/小丑
有时我们想查找所有包含以特定前缀开头的单词的文档。 在这种情况下，前缀请求将为我们提供帮助，其外观类似于
jav * 。 当在前缀树上实现字典时，前缀请求非常有效，然后我们进入前缀的嵌套并接受下面的所有术语。
1.4.3短语查询和接近查询
有时候，您需要查找整个短语，例如“ java developer”，或者找到两个单词之间的单词，例如“ java”和“ developer”，而两个单词之间的单词不超过两个，以便您可以找到包含java android kotlin开发人员的文档。 为此，另外使用每个文档中的单词位置列表。
跨越文档列表时，所有操作都与AND操作相同。 但是，在两个列表中都找到该文档之后，还要进行另一次检查-根据位置（位置）的差异，这些术语彼此之间的距离正确。
1.4.4请求计划
通常，在执行请求本身之前，先构建其计划。 发生这种情况是为了优化请求的执行并进行优化，例如省略文档列表的列表起作用。
优化查询的最简单方法是按照文件大小的增加顺序遍历文档列表。 因此，我们不会浪费大量文档，而不是浪费在较小列表中。
例如，让我们解析
android AND java AND sql query 。 假设android列表中有10个文档，在sql-20和java-100中。在这种情况下，最好先越过最小的列表，并且优化后的查询将看起来像
（android AND sql）AND java 。
对于OR，最简单的方法是将相交处的文档数计算为两个可能相交的列表的总和。
1.4.5查询扩展-同义词
除了用户在搜索栏中输入的内容外，通常搜索还会尝试扩展查询本身以查找更多相关文档。 可以使用很多来扩展搜索：用户的查询历史记录，有关他的一些个性化数据等等。 但是除此之外，还有一种扩展请求的通用方法-同义词。
在这种情况下，将文档写入索引时，该术语在同义词词典中被替换为“链接”：
转换请求时也会发生同样的事情。 例如，当我们请求
销售经理时 ，请求实际上看起来像：
因此，在回复中，我们不仅会收到包含销售经理的文档，还会收到包含销售代理和销售的文档。
1.5过滤
1.5.1快速范围滤波器
有时我们希望通过一系列值来过滤某些内容，例如，根据多年的经验。 假设我们想找到所有需要3到11年经验的职位空缺。 第一个决定是使用范围内的所有选项发出请求，并通过OR进行组合。 但是问题在于可能有太多的值。 解决此问题的一种方法是一次以多种精度记录值：
在这种情况下，我们将存储5个精度值：一年（我们将其视为初始值），两个，四个，八个和十六个。
然后，在记录时将发生以下情况：例如，当记录需要6年经验的文档时，我们会立即以所有准确性记录该值：
当过滤“从3年到11年”时，会发生以下情况：我们仅选择所需精度的值，而只得到3个值而不是8个值，并得到查询
（实际值== 3）OR（精度4 == 4）OR（精度4 == 8）
1.5.2位掩码
位掩码是索引的组成部分。 最重要的用途是过滤已删除的文档。 当您从索引中删除文档时，不会立即发生物理删除。 索引旁边写有一个特殊的结构，其中每个位都表示索引中文档的ID，删除后，该位将升高一个位，并且在搜索时，这些文档将被过滤且不会落入输出。
您还可以使用位掩码为每个用户设置某些文档的权限，并缓存各个常用的过滤器。 然后，通常将位掩码与索引分开存储。
例如，我们有流行的过滤条件：莫斯科市，只有部分时间，没有工作经验。 然后，在请求之前，我们可以为这些文档获取已保存的位掩码，添加它们，并获得最终的位掩码-哪些文档经过所有这三个过滤器，从而节省了过滤时间。
2.排名
我们记得，搜索的主要任务是在最短的时间内获得最相关的信息。 在此之后，通过文本查询过滤文档并应用了必要的过滤器和权限后，我们将获得文档排名的帮助。
最简单，最便宜的排名方法是按日期对文档进行排序。 在某些系统中，这是以前进行的，例如在新闻或房地产公告中，因此首先向用户显示了最新文档。
有时，可以使用基于文档中找到的单词数的排名模型，例如，在文档数量不多的情况下，并且我们希望查找其中至少找到一个查询单词的所有文档。 在这种情况下，那些找到查询中所有单词或更多单词的文档将更加相关。
当然，目前，这些方法已经无关紧要，它们很可能归因于问题的历史。
2.1 TF-IDF
TF-IDF（术语频率-文档反向频率）是最基本和最常用的排名公式之一。 公式的本质是减少在各处使用的术语（例如介词和插入词），并制作更有意义的稀有术语，从而从查询中显示带有稀有和有意义的术语的第一份文档。 现在让我们将公式分成几部分：
TF（术语频率）是文档中出现的术语的频率。 它的计算很简单：
TF术语“ java” =文档中术语“ java”的数量/文档中所有术语的数量
IDF（反文档频率） -单词在文档集合中出现的频率的倒数。 帮助减轻常用单词的权重。
IDF（`java`）=日志（集合中的文档数/出现Java术语的文档数）此外，要获得术语java的TF-IDF，我们只需要将获得的TF和IDF值相乘即可。 , , . , , developer , , java developer .
2.2
, , . , , , .
2.3 BM25 BM*
BM25 (Okapi best match 25) TF-IDF . BM25F, ( ).
2.4
, :
- DFR (divergence from randomness),
- IBS (information-based models),
- LM Dirichlet,
- Jelinek-Mercer.
2.5
, , . ,
.
2.6 Top k
, . , , .
, .
top k .
— . k, k
* . heap. n*log(n) k.
. , , , 10 12, score 10 score . , n — (n*page size) .
3.
3.1
— . , .
, : , , . , . . ( , ). (merge).
, , :
. , , , - .
3.2 (megre)
— . «» — . , , ( ).
, , , . :
4.
, , . , - (, . .). , , , .
4.1
(, hh , ), . .
, , . -, , . -, , , .
4.2
, . , .
, hh,
, , - :
5. …
, , , . , : , , , , , (highlight), . , , , top k .
:
就是这样，谢谢大家的关注，很高兴听到您的评论和问题。聚苯乙烯
我要感谢gdanschin帮助我写这篇文章。