算法：倒排表/倒排索引（Inverted index）

蔚落 2023-10-05 19:22 98阅读 0赞

搜索引擎最核心的技术， **倒排索引**技术，倒排索引可能需要分成几篇文章才说得完，我们先会说说倒排索引的技术原理，然后会讲讲怎么用一些数据结构和算法来实现一个倒排索引，然后会说一个 索引器怎么通过 文档来生成一个倒排索引。

什么是倒排索引呢？索引我们都知道，就是为了能更快的找到文档的数据结构，比如给文档编个号，那么通过这个号就可以很快的找到某一篇文档，而倒排索引不是根据文档编号，而是通过文档中的某些个词而找到文档的索引结构。

倒排索引技术简单，高效，简直是为搜索引擎这种东西量身定做的，就是靠这个技术，实现一个搜索引擎才成为可能，我们也才能在海量的文章中通过一个关键词找到我们想要的内容。

我们看个例子，有下面的几个文档：

<table> 
 <thead> 
  <tr> 
   <th>文档编号</th> 
   <th>文档内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>这是一个Go语言实现的引擎</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>PHP是世界上最好的语言</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>Linux是C语言和汇编语言实现的</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>谷歌是一个世界上最好的搜索公司</td> 
  </tr> 
 </tbody> 
</table>

直观的看，我们通过编号1,2,3,4可以很快的找到文档，但是我们需要通过关键词找文档，那么把上面那个表格稍微变化一下，就是倒排索引了

倒排表（倒排索引）【只列出了部分关键词】

<table> 
 <thead> 
  <tr> 
   <th>关键词</th> 
   <th>文档编号</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Go</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>语言</td> 
   <td>1，2，3</td> 
  </tr> 
  <tr> 
   <td>实现</td> 
   <td>1，3</td> 
  </tr> 
  <tr> 
   <td>搜索</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>引擎</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>PHP</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>世界</td> 
   <td>2，4</td> 
  </tr> 
  <tr> 
   <td>最好</td> 
   <td>2，4</td> 
  </tr> 
  <tr> 
   <td>汇编</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>公司</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>这样就非常好理解了吧，实际上倒排索引就是把文档的内容切词以后重新生成了一个表格，通过这个表格，我们可以很快的找到每个关键词对应的文档，好了，没有了，到这里，就是倒排索引的核心原理，也是搜索引擎最基础的基石，不管是谷歌还是某度，最核心的东西就是这两个表格，没这两表格，啥都干不了。</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

看上去很简单吧，好吧，我们现在来模拟搜索引擎进行一次搜索，比如，我们键入关键词：搜索引擎

1.  首先将 “搜索引擎” 这个词进行分词：搜索/引擎；
2.  我们在表格2中查到 “搜索” 这个词出现在第4行， “引擎” 这个词出现在第5行；
3.  找到第4行的第2列、第5行的第2列，把文档编号找出来，是1和4
4.  去第一个表格通过文档编号把每个文档的实际内容找出来
5.  将1和4的结果显示出来
6.  搜索完成

上面就是搜索引擎的最基础的技术了，如果来设计一个数据结构和算法来实现表2就成了搜索引擎技术的关键。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]  
在实现数据结构和算法之前，我们需要知道搜索引擎搜索的是海量的数据，一般的中型电商的数据都是几十上百G的数据了，所以这个数据结构应该是存储在本地磁盘的而不是在内存中的，基于以上的考虑，为了快速搜索，要么自己实现cache来缓存热数据，要么考虑使用操作系统的底层技术MMAP，鉴于我自己实现的cache不见得（基本上是不太可能）比操作系统做得好，所以我使用的是MMAP。

--------------------

参考资料：  
[搜索之倒排索引][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210218101331187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/yanerhao/article/details/77391847