搜索引擎原理解析：从0开始实现一个搜索引擎

政采云技术发表于 1年以前 | 总阅读数：517 次

搜索无处不在，作为信息化时代大多数人获取信息的最重要的路径，说搜索引擎是使用最为广泛和频繁的中间件之一，应该没有人会反驳。在实际的应用场景中，小到个人博客，大到电商平台，你在谷歌上搜索的每一个关键字，在电商网站上搜索的每一件商品，追剧听音乐的时候在搜索栏输入的每一个名字的背后都是搜索引擎的处理和输出。就像是你提问，然后搜索引擎告诉你一个答案，搜索不仅无处不在，无所不知，默默的主宰着网络世界的入口。

一、搜索引擎原理

打开谷歌，输入关键词，谷歌往往可以很精准的返回你所需要的内容，这个是怎么实现的呢？简单的思考一下就能得出一个结论：一定是关键词能极为快速和准确的命中具体的内容及地址，但是搜索引擎的收录页面数量往往是千亿万亿级别的，从这个量级里面检索到你要的数据可以说是大海捞针一点也不夸张。那么搜索引擎是如何让你在数据的汪洋大海里捞到你想要的那根针的那？这就要说到所有的搜索引擎都离不开一个概念：索引。

1. 正排索引

所谓的正排索引其实很很符合人类大脑的搜索逻辑，告诉你一个人的名字，当他/她在你的记忆中命中，就会迅速的浮现出：性格、身高等等信息。数据示例结果如下:

{
  "张三": {
    "sex": "F",
    "height": 175
  },
  "李四": {
    "sex": "M",
    "height": 165
  }
}

通过名字直接定位到具体的数据，从数据结构来看：哈希表的复杂度为 O(1) ，因此可以通过key快速低成本的命中，这种简单的通过一个名字来定位到具体内容的方式就是正排索引的概念。但是如果我们要搜索的条件是属性而非key那？试想一下：在海量的数据中，例如从 14 亿人中检索出符合指定身高的人员数据，要遍历 14 亿的信息来获取需要的数据，成本不言而喻。所以正排索引除非是以 key 为索引进行检索的场景，否则实用价值很低。

2. 倒排索引

其实当下几乎所有的搜索引擎都有着同样的一个核心原理：这个原理就是倒排索引，上面讲到正排索引其实是人类大脑所习惯的搜索方式，所以我们只需要知道一个 key 就能快速的的定位到内容。所以通过 key 来检索的成本很低，那么问题来了，如果我问你：你认识的身高 165 的女性有谁？你会发现你消耗的脑细胞成指数级上升，这还是非常简单的问题，想像一下，从百万千万甚至高达十亿百亿级别的文档中找出内容包含指定关键词的文档，如果用正排索引会有多大的消耗，而倒排索引，正是为了解决这个问题而存在。在百度、谷歌搜索的时候，搜索结果基本上是毫秒级别的，这其实就依赖于倒排索引的实现，其原理例如：假设有一篇文章内容为: “政采云技术团队，持续分享原创干货，欢迎点赞关注！” 文档 ID 为 1 ，还有一篇文档内容为: “政采云是一家优秀的互联网公司，技术氛围十分浓厚”，文档 ID 为 2 。基于倒排索引我们给文章1定义关键词：政采云、原创干货，数据结构为:

{
  "政采云": 1,
  "原创干货": 1
}

这样的一个map中，我们知道map的数据结构是哈希表，所以复杂度用大 O 表示法为 O(1) ，可以很快速的检索到想要的结果，所以倒排索引顾名思义，就是从文章内容 (value) 搜索 key 的索引方式，同样的，文章 2 的倒排索引结构为:

{
  "政采云": 2,
  "技术氛围": 2,
  "互联网公司": 2
}

问题是，两篇文章中有一个同样的关键词：政采云，用户搜索的关键词是政采云的时候，这两篇文章都与政采云有关，应该都搜索出来，所以经过合并，数据结构为：

{
  "政采云": [1, 2],
  "原创干货": [1]
  "技术氛围": [2],
  "互联网公司": [2]
}

这样我们通过以关键词为 key ， value 为文章 ID 的数组这样的方式，就实现了一个倒排索引，是不是很简单那？但是大家有没有发现一个问题，倒排索引的前提是我们要进行关键字词的提取，上文为了简单，人肉提取了关键词，在实际的场景中这个操作肯定不具备实际意义，因此就需要另外一个搜索引擎需要的核心的组件：分词器。

3.分词器

世界上有各种语言，每种语言的语义、语法各不相同，分词器的意义就在于可以从各种语言中提取字词，而通过倒排索引中讲述的内容我们可以知道这些字词对应的就是倒排索引的查询条件。帮助我们把一大段文本分割成一个个的字词的工具就叫做分词器。分词器主要用在两个方面：创建索引的时候从整篇文档中提取字词来创建索引，搜索的时候把用户的搜索条件分词去命中索引。例如我的搜索条件为：我好想去政采云有限公司工作，那么通过分词器可以获取到的结果如下：

我好想去政采云有限公司  => ["我", "好", 想去", 政采", "云", "有限公司", "工作"]

可以发现其实依靠分词器配合倒排索引，我们已经可以实现一个基本的搜索引擎了，但是存在一个问题，中文博大精深，例如这一句话就会成功让分词器傻眼：

来到杨过曾经生活过的地方，小龙女动情地说：我也想过过过儿过过的生活。

这当然是一个极端的情况，实际场景中比较少的遇到，但是：搜索计算机，出现的结果应该是电脑还是计算器，搜索网点，应该是营业网点还是网络点位。就需要集合其他的条件来进行判断了。例如用户在搜索网点关键词之前搜索了网络设备。所以搜索的准确性一定是会存在一定局限性的。可以越来越贴近用户想要的结果，却难以获得一个定性的结果，需要持续的维护来优化准确性。而针对一些具有特定背景的词汇，则需要自定义词库的方式进行处理，例如一个特定词汇：云原生，会被分词器分割成：云和原生这两个词，这将会直接影响搜索的结果，导致搜索出来的内容跟实际需求可能南辕北辙，针对这种问题，自定义词库将云原生等专有的名词定义成一个专有词库即可。然后另外一个问题是：无论是什么语言文档中总会存在大量的对于文档内容毫无意义的功能词，例如：英文中的：'the'、'is'、'at'、'which'、'on', 中文中的：在、的、你、我、他等等。对于内容搜索来说这些词其实毫无意义，数量又很多，占用资源的同时又影响搜索效率和结果，而针对这些词语的过滤就是搜索引擎中停用词的概念。

4. 停用词

停用词是会在文本处理过程中如果遇到它们，就立即停止处理，并将其忽略，通常配合分词器来进行处理。一些语气助词、副词、介词、连接词等，通常自身并无明确的意义。所以需要做一次过滤。停用词的作用通常是过滤优化分词结果。

5. 近义词

以上的逻辑中搜索引擎的效果越来越好，但是却无法满足这样的一些场景：用户输入 k8s 的时候，命中不了 kubernetes 的索引，用户输入”开发“却命中不了”研发“，然而语言的复杂度很高，在实际的场景中用户提交的内容不可控，想要匹配更为精确的内容我们还需要按照分词的结果进行近义词的匹配。以分词结果 + 近义词进行命中查询才能更加的符合用户的需要。而近义词从人的理解上比较简单，然而实际逻辑化却十分复杂，需要依赖于 NLP 和 AI 来进行处理，所以复杂度较高。比较简单的做法是可以将常用的词语建立词库去做匹配关联，但是往往精准程度很大程度上受到词库完善程度的影响，实际上也会发现这样实现的近义词库的方式带来的搜索效益比较有限，但是在内部文档搜索场景中并不要求太多的匹配度，而且也可以灵活的指定行业关键词，例如搜索消息队列，近义词库就可以指定：kafka 、 rocketmq 、 nsq 等。

6. 文档排序算法

搜索完成之后，搜索的结果往往不止一条，那么那些是用户最想要看到的，那些是次要的，主要的靠前排序让用户最先看到，从人的理解力来说当然很简单，但是要让搜索引擎理解这个就需要依赖于算法。例如比较简单的匹配程度算法，用户关键词通常能够代表他所理解的文档内容的核心关键词，通常如果是文档的核心词，那么这个关键词在目标文档中出现的次数通常就会比较多，所以一个简单的算法是，统计关键词在各个文档中的命中数，以命中次数做排序。然而单单一个简单的算法，实际搜索的结果往往不符合预期，所以正常情况下，为了使搜索的结果更贴近用户的实际诉求，应该是结合多种算法综合进行排序计算。例如，通常文档的标题对文档内容具备更高优先级的代表意义，所以用户输入的查询条件和文档的标题匹配应该有更高的权重，另外，文档内容可能有时效性，随着时间的推移可能失效，因此，创建、修改时间靠前的文档也应该有较高的权重。在实际的场景中，文档的排序，实际就是由这些算法的匹配度综合计算最终得出分值来完成的。此外目前一些场景中通过机器学习，或者推荐算法来进行文档优先级计算的实际效果会更好。

7. 联想搜索 NLP

我们在搜索框中输入一个条件，我们发现搜索引擎会自动联想出可能是你想要的搜索条件，其实在你输入的过程中搜索引擎会不断的通过你键入的词汇进行"联想"，这个具体实现十分复杂，例如根据历史信息、你的位置信息、语言信息、结合地域文化特征等等条件综合的去猜测出你需要的结果。复杂度非常的高，因此即便是几个当下的搜索引擎的大厂，条件联想仍然会有不小的出错几率。

8. 大模型与搜索引擎

NLP从基于规则和模式的匹配到利用知识方法再到统计方法，再到今天各种大模型不断的涌现，人类已不满足于仅仅通过关键词来搜索想要的结果，今天，计算机已经有了更深层次的自然语言理解和生成的能力，机器越来越”人“化，能够更好更精准的理解用户更复杂的需要，让找到答案变的更加简单便捷。看起来大模型颠覆了搜索引擎，但是实际上，搜索引擎仍然具备大模型所不具备的优势。其一是实时性和成本，大模型训练一次无论是时间还是资源的成本都是海量的，高昂的学习成本（大模型的训练成本远远高于搜索引擎的成本，二者不在一个数量级上）导致了必然的信息滞后（想象一下电商场景，新上架一个商品要很久以后才能被搜索到），而搜索引擎就可以很轻易的实现数据的实时性。其二是数据的可信度，搜索引擎通过相关性匹配索引先获知相关的内容，不存在对原文的任何加工处理，而大模型本质上是给出一个大模型算法认为的答案，很多信息甚至于是大模型”编造"的，因此给出的答案不一定正确，更缺少权威，甚至于存在胡编乱造的情况，可信度较低，在严谨的需求场合中，这个问题是很致命的。因此，搜索引擎的不可替代性依然存在，仍然具备顽强的生命力。

二、实现一个搜索引擎

搜索引擎最基本的两个功能：创建索引、提供搜索。如果不考虑索引的持久化，可以将索引创建在内存中，在这种实现下，表面上看我们所实现的搜索引擎性能上秒杀 Elasticsearch ，但是这其实是主要归功于内存的速度， Elasticsearch 的强大在于分布式的特性和生产环境中久经考验的可靠性实践。Elasticsearch 解决了非常复杂的问题，仍然是生产环境的最佳解决方案。从本文视角只是从原理上进行简单的阐述和实现。

1. 数据类型设计

一个doc的数据类型：我们设计包含了标题、类型（标识文章、用户、应用、代码等）、来源（标识各种来源系统）、请求地址、摘要、创建和更新时间。

2. 文档数据类型

type Doc struct {
  Title       string    `json:"title,omitempty"`
  Type      string   `json:"type,omitempty"`
  Source      string    `json:"source,omitempty"`
  Url         string    `json:"url,omitempty"`
  Description string    `json:"description,omitempty"`
  CreatedAt   time.Time `json:"createdAt,omitempty"`
  UpdatedAt   time.Time `json:"updatedAt,omitempty"`
}

3. 接口设计

索引数据接口，主要用来存放索引

type Index interface {
  Set(docId, index string) error
  Get(index string) ([]string, bool)
  List() ([]string, error)
  Del(key string) error
  Exist(key string) bool
}

元数据接口：用来存放文档的基本元数据信息。索引和元数据都可以存放在其他中间件中，例入数据库和缓存服务器中。

type Metadata interface {
  Set(key string, doc *Doc) error
  Get(docId string) (*Doc, bool)
  Del(docId string) error
}

命中统计接口，用于统计关键词在对应文档的命中率，用于排序。

type Count interface {
  Set(docId, index string)
  Get(docId string) (map[string]int64, bool)
  Del(docId string) error
}

任何后端数据存储例如 redis 、 mysql 、 sqlite 等等只要实现这三个接口，都可以对接进来，本文以内存存储为例。

4. Set类型

我们基于上文提到的利用map的哈希表特性实现的倒排索引， value 中的值要保持唯一，Set是一个很适合的数据结构。虽然原生 golang 是没有 set 这个类型的，但是实现也很简单，我们用 map 实现一个 set 并通过 sync.RWMutex 来保证并发安全：

// golang中的空结构体不占用内存
type Empty struct{}

type Set struct {
  sync.RWMutex
 Store map[string]Empty
}

func NewSet() *Set {
 return &Set{Store: make(map[string]Empty)}
}

func (s Set) List() []string {
  s.RLock()
  var result []string
  for k := range s.Store {
    result = append(result, k)
 }
  s.RUnlock()
 return result
}

func (s Set) Set(key string) {
  s.Lock()
 s.Store[key] = Empty{}
  s.Unlock()
}

func (s Set) Del(key string) {
  if _, exist := s.Store[key];exist {
    s.Lock()
    delete(s.Store, key)
    s.Unlock()
  }
}

5. 工厂函数

type Store struct {
  // 索引
  Index    Index
  // 统计
  Count    Count
  //  分词器
  Seg      *gojieba.Jieba
}

func NewStore() *pkg.Store {
  return &pkg.Store{
    Seg:      gojieba.NewJieba(),
    Index:    newIndex(),
    Count:    newCount()
  }
}

6. 创建索引

// 去重
func removeDuplicate(items []string) []string {
 result := make([]string, 0, len(items))
 temp := map[string]struct{}{}
 for _, item := range items {
  if _, ok := temp[item]; !ok {
   temp[item] = struct{}{}
   result = append(result, item)
  }
 }
 return result
}

func (s Store) CreateIndex(text, docId string, doc *Doc) {
  seg := removeDuplicate(s.Seg.Cut(text, true))
  for _, v := range seg {
    // 这里将所有索引中的英文小写，解决大小写匹配的问题
    word := utils.ToLower(v)
    s.Index.Set(docId, word)
    s.Count.Set(docId, word)
  }
  if err := s.Metadata.Set(docId, doc); err != nil {
    log.Println("[ERROR] Update metadata failed:", err.Error())
  }
}

7. 搜索

func (s Store) Search(text string) []string {
  var result []string
  seg := s.Seg.Cut(text, true)
  for _, v := range seg {
    var key = utils.ToLower(v)
    doc, exist := s.Index.Get(key)
    if !exist {
      continue
    }
    result = append(result, doc...)
  }
  return result
}

func (s Store) SortSearch(text string) []string {
  var result []string
  var hit = make(map[string]int64)
  docs := s.Search(text)
  for _, v := range docs {
    count, exist := s.Count.Get(v)
    if !exist {
      hit[v] = 0
    }
    for _, i := range count {
      hit[v] += i
    }
  }
  for _, d := range utils.SortDoc(hit) {
    result = append(result, d.Key)
  }
  return result
}

8. 文档排序

排序规则中，可以通过文章的创建时间，关键字匹配数量、匹配程度等分别计算权重，基于总权重进行排序。

type Map struct {
  Key   string
  Value int64
}

type DocList []Map

func (p DocList) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p DocList) Len() int           { return len(p) }
func (p DocList) Less(i, j int) bool { return p[i].Value < p[j].Value }

func SortDoc(m map[string]int64) DocList {
  p := make(DocList, len(m))
  i := 0
  for k, v := range m {
    p[i] = Map{k, v}
    i++
  }
  sort.Sort(p)
  return p
}

三、测试

如下所示，三次搜索总耗时 81.848 纳秒, 不到 0.1 毫秒这当然是因为所有的数据都缓存在内存中的结果，我们可以将元数据以及索引数据存放在持久化的中间件中，虽然性能会下降但是可以保障数据的安全性。

func main() {
  s := store.NewStoreByMEM()
  s.CreateIndex("政采云技术团队， 是一个富有活力、创造力的团队，持续保持稳定的原创更新， 欢迎点赞关注！", "111111", &pkg.Doc{
    Title: "政采云技术团队",
    Description: "政采云技术团队， 是一个富有活力、创造力的团队",
    Url: "https://juejin.cn/user/703323667190104",
    Source: "原创文章",
  })
  now := time.Now()
  fmt.Println("关键词: 政采云 目标文档:", s.Search("政采云"))
  fmt.Println("关键词: 原创 目标文档:", s.Search("原创"))
  fmt.Println("关键词: 创造力 目标文档:", s.Search("创造力"))
  fmt.Println(fmt.Sprintf("搜索耗时：%s", time.Since(now)))
}
//  output
➜  LiteSearch git:(main) ✗ go run main.go
关键词: 政采云 目标文档: [111111]
关键词: 原创 目标文档: [111111]
关键词: 创造力 目标文档: [111111]
搜索耗时：81.848µs

以上就是一个，没有分布式能力，不考虑数据可靠的单机搜索引擎的简单实现，用十分简洁(Low)的排序解决方案提供了索引、查询及排序能力。

四、总结

虽然看起来搜索引擎的原理非常简单，但是抛开流量谈性能就是耍流氓，搜索引擎实际上是个非常之复杂的系统工程。分布式的海量数据存储，超高并发的读写，搜索的速度和精确度要求等等，每一项都面临着对应技术领域天花板级别的挑战。本文只是尝试以一个简单的原理阐述开始最终实现一个搜索引擎来了解搜索引擎基本原理、工作流程、运行机制。