扣丁书屋

如何从零开始实现全文搜索引擎?

我们要从零开始构建一个 FTS 搜索引擎。当你看完这篇博文,你将会了解如何在 1 毫秒延时的情况下搜索百万级的文档。“给我搜索出所有包含 cat 单词的文档”,我们会从以上一个简单的搜索词开始逐步去扩展我们的搜索引擎,甚至去支持更为复杂的布尔查询功能。

原文地址:https://artem.krylysov.com/blog/2020/07/28/lets-build-a-full-text-search-engine/

全文搜索(Full-Text Search)是一个大家每天都会使用的工具,但是只有少部分人真正理解其背后的原理。如果你曾经使用 Google 搜索过,类似“Golang 覆盖率报告”或者在某些电子商务网站搜索“室内无线摄像头”,意味着你都使用过全文搜索。

全文搜索(英文简写 FTS)是一项在一系列文档中搜索文本的技术。文档可以是网页、报刊文章、Email 邮件或者任何结构化的文本。

今天我们要从零开始构建一个 FTS 搜索引擎。当你看完这篇博文,你将会了解如何在 1 毫秒延时的情况下搜索百万级的文档。“给我搜索出所有包含 cat 单词的文档”,我们会从以上一个简单的搜索词开始逐步去扩展我们的搜索引擎,甚至去支持更为复杂的布尔查询功能。

提示:众所周知的全文搜索引擎是 Lucene,而比较知名的工具 Elasticsearch 和 Solr 都是在 Lucene 基础上构建的。

为什么是全文搜索?

在我们开始写代码之前,你肯定会问为什么不直接使用 grep 工具,或者通过顺序的方式逐步去对每个文档进行遍历?我们当然可以这样干,但是这并不是一个好的解决方案。

搜索语料

我们使用的搜索语料文档是英文 Wikipedia 的部分文档,可以通过网站 dumps.wikimedia.org 下载。目前解压后的文档大小是 913MB,里面包含了超过 60 万的 XML 文件。示例如下:

<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>

加载文档

首先我们需要将所有的文档进行加载,而 Go 内建的 encoding/xml 包就非常的好用,以下是代码实现:

import (
   "encoding/xml"
   "os"
)

type document struct {
   Title string `xml:"title"`
   URL   string `xml:"url"`
   Text  string `xml:"abstract"`
   ID    int
}

func loadDocuments(path string) ([]document, error) {
   f, err := os.Open(path)
   if err != nil {
       return nil, err
  }
   defer f.Close()

   dec := xml.NewDecoder(f)
   dump := struct {
       Documents []document `xml:"doc"`
  }{}
   if err := dec.Decode(&dump); err != nil {
       return nil, err
  }

   docs := dump.Documents
   for i := range docs {
       docs[i].ID = i
  }
   return docs, nil
}

每一个加载后的文档都会分配一个唯一的 ID 标识。为了保持简单,第一个被加载的文档分配的 ID=0,第二个 ID=1,以此类推。

第一次尝试

搜索内容

现在我们已经将所有的文档加载到内存,那就可以开始尝试用最简单的方法去搜索包含 cat 的文档了。我们通过一个循环判断每一篇文档是否包含 cat:

func search(docs []document, term string) []document {
   var r []document
   for _, doc := range docs {
       if strings.Contains(doc.Text, term) {
           r = append(r, doc)
      }
  }
   return r
}

在我的笔记本电脑上,搜索耗时是 103ms,不算太差。如果你稍微仔细看一下搜索出来的结果的话,你会发现结构里面包含了一些 caterpillarcategory 等匹配,而且并没有搜索到包含大写 Cat 的文档。以上并不是我想要的搜索行为。

接下来我们将修复以上的两个问题:

  • 使得搜索引擎能够感知字母大小写
  • 匹配完整的单词,而不是某个单词的一部分

使用正则表达式搜索

一种快速解决上述问题的解决方案是使用正则表达式。

比如搜索 cat 的正则表达式是 (?i)\bcat\b

  • (?i) 意思是使得搜索对大小写不敏感
  • \b 匹配单次的边界(边界意思是单词的前后是非字母)
func search(docs []document, term string) []document {
   re := regexp.MustCompile(`(?i)\b` + term + `\b`) // Don't do this in production, it's a security risk. term needs to be sanitized.
   var r []document
   for _, doc := range docs {
       if re.MatchString(doc.Text) {
           r = append(r, doc)
      }
  }
   return r
}

糟糕的是,以上搜索耗时超过了 2 秒。正如你所看到的,在超过 60 万文档的情况下,搜索变得越来越慢,而简单的实现方案并不能拥有好的扩展性。随着数据集的不断扩大,我们将搜索越来越多的文档,而上述我们实现的算法的时间复杂度是 O(n) 的,意味着时间是和文档数成正比的。如果我们有 600 万文档要搜索的话,耗时会超过 20 秒,肯定是无法忍受的。

倒排索引

为了使搜索变得更快,我们需要提前做一些预处理并建立相应的索引加速搜索。

而这正是全文搜索(FTS)的核心数据机构,我们称之为倒排索引(Inverted Index,也有叫反向索引的)。默认我们知道一篇文档包含了哪些词,而倒排索引将建立词和文档的对应关系。示例如下:

documents = {
   1: "a donut on a glass plate",
   2: "only the donut",
   3: "listen to the drum machine",
}

index = {
   "a": [1],
   "donut": [1, 2],
   "on": [1],
   "glass": [1],
   "plate": [1],
   "only": [2],
   "the": [2, 3],
   "listen": [3],
   "to": [3],
   "drum": [3],
   "machine": [3],
}

以下是一个真实世界的倒排索引,一本书的附录包含了词出现的所有页码。

文本分析

在我们开始建立索引之前,我们需要将文档中的词进行切分,方便后续的索引和查询。

一个文本分析器包含了一个分词器和多个过滤器。

分词器

分词器是文本分析的第一步,它的任务是将文档切分为一系列的词。我们的实现是简单的将文本通过单词边界进行切分,同时移除相应的标点。

func tokenize(text string) []string {
   return strings.FieldsFunc(text, func(r rune) bool {
       // Split on any character that is not a letter or a number.
       return !unicode.IsLetter(r) && !unicode.IsNumber(r)
  })
}
> tokenize("A donut on a glass plate. Only the donuts.")

["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]

过滤器

在很多场景下,只是将文本进行切分并不够。为了使得后续的索引和查询更容易,我们需要做额外的标准化。

将单词统一小写

为了使得搜索对字母大小写不敏感,我们将所有词统一转化为小写。比如 cAt、Cat、caT 将统一转化为小写的 cat。当我们搜索的时候,我们也会把搜索词转化为小写的。

func lowercaseFilter(tokens []string) []string {
   r := make([]string, len(tokens))
   for i, token := range tokens {
       r[i] = strings.ToLower(token)
  }
   return r
}
> lowercaseFilter([]string{"A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"})

["a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"]

去除通用词

任何英文文档中都包含了一些通用的词,比如 a、I、the、be。而这些词另外一个称呼是停用词。我们会将这些词删除不进行索引,因为任何的文档中都包含这些词,搜索这些词并没有任何意义。

但是并没有一个官方的停用词列表,我们将移除 OEC Rank 中排序前十的停用词,当然你也可以增加更多。

var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
   "a": {}, "and": {}, "be": {}, "have": {}, "i": {},
   "in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}

func stopwordFilter(tokens []string) []string {
   r := make([]string, 0, len(tokens))
   for _, token := range tokens {
       if _, ok := stopwords[token]; !ok {
           r = append(r, token)
      }
  }
   return r
}
> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

["donut", "on", "glass", "plate", "only", "donuts"]

词干提取

因为英语中语法的不同,文档中可能包含同一个词的不同表现形式,而词干提取就是为了将这些词转化为词干。比如fishingfishedfisher 都会转化为基础词干 fish。

实现一个词干提取器并没有那么容易,而这并不是本文的重点,所以我们使用了一个现成的开源模块。

import snowballeng "github.com/kljensen/snowball/english"

func stemmerFilter(tokens []string) []string {
   r := make([]string, len(tokens))
   for i, token := range tokens {
       r[i] = snowballeng.Stem(token, false)
  }
   return r
}
> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

["donut", "on", "glass", "plate", "only", "donut"]

提示:词干有时候并不是一个有效的词,比如 airline 会转化成 airlin。

将所有的文本分析器进行集成

func analyze(text string) []string {
   tokens := tokenize(text)
   tokens = lowercaseFilter(tokens)
   tokens = stopwordFilter(tokens)
   tokens = stemmerFilter(tokens)
   return tokens
}

分词器和过滤器将文档转化为词的列表。

> analyze("A donut on a glass plate. Only the donuts.")

["donut", "on", "glass", "plate", "only", "donut"]

现在以上词就可以开始索引了。

构建索引

回到倒排索引,它将词与其出现的文档列表进行关联。而 Go 内建的 map 就是一个很好的候选数据结构,键值 key 存储词,值 value 储存文档 ID 列表。

type index map[string][]int

构建索引的步骤就是逐步的分析文档,并将文档 ID 增加到 map 映射中。

func (idx index) add(docs []document) {
   for _, doc := range docs {
       for _, token := range analyze(doc.Text) {
           ids := idx[token]
           if ids != nil && ids[len(ids)-1] == doc.ID {
               // Don't add same ID twice.
               continue
          }
           idx[token] = append(ids, doc.ID)
      }
  }
}

func main() {
   idx := make(index)
   idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
   idx.add([]document{{ID: 2, Text: "donut is a donut"}})
   fmt.Println(idx)
}

我们成功了,以上代码将词和文档列表进行了关联。

map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]

查询

要利用上述构建的倒排索引,我们需要对查询词也进行一致的文本分析(分词器和过滤器)。

func (idx index) search(text string) [][]int {
   var r [][]int
   for _, token := range analyze(text) {
       if ids, ok := idx[token]; ok {
           r = append(r, ids)
      }
  }
   return r
}
> idx.search("Small wild cat")

[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]

最后,我们可以从 60 万文档中搜索所有出现 cat 的文档,而耗时少于 1 毫秒(18 微妙)。

当我们利用倒排索引,搜索算法的时间复杂度是和搜索词的数量相当,这意味着算法时间复杂度是 O(1),并不会随着文档数量的增加而增加。

布尔查询

在前一部分我们的介绍中搜索的返回是每一个词的文档列表,并没有做相关的聚合。而我们期望的是能够搜索到同时包含 smallwildcat 的文档。下一步我们将会对以上文档列表进行聚合归并,这样就能得到包含所有词的文档列表。

幸运的是,我们的倒排索引的文档列表是升序的。这样我们去计算两个列表的相同元素的算法时间复杂度是线性的。

func intersection(a []int, b []int) []int {
   maxLen := len(a)
   if len(b) > maxLen {
       maxLen = len(b)
  }
   r := make([]int, 0, maxLen)
   var i, j int
   for i < len(a) && j < len(b) {
       if a[i] < b[j] {
           i++
      } else if a[i] > b[j] {
           j++
      } else {
           r = append(r, a[i])
           i++
           j++
      }
  }
   return r
}

我们再将搜索结果聚合代码与之前的进行整合。

func (idx index) search(text string) []int {
   var r []int
   for _, token := range analyze(text) {
       if ids, ok := idx[token]; ok {
           if r == nil {
               r = ids
          } else {
               r = intersection(r, ids)
          }
      } else {
           // Token doesn't exist.
           return nil
      }
  }
   return r
}

Wikipedia 的文档中最后只有两篇文档同时包含了 smallwild 和 cat。

> idx.search("Small wild cat")

130764 The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692 Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.

搜索结果是我们所期望的。同时,通过搜索结果我们也是第一次听说 catopuma(金猫), 以下图片就是。

总结

我们仅仅是实现了一个简单的全文搜索引擎,尽管它很简单,但是你依然可以基于此建立更多复杂的项目。

同时我们也没有过多的去介绍如何提高性能,以及使搜索引擎对用户使用更加的友好。以下是一些后续优化的方向仅供参考:

  • 扩展布尔查询支持 OR 和 NOT
  • 将倒排索引存储在磁盘
  • 每次都重建索引会耗费一些时间
  • 大的索引可能不能在内存全部存储

以上所有代码都可以从 GitHub 上获取到:https://github.com/akrylysov/simplefts


https://mp.weixin.qq.com/s/zWYiAZJUYXfjxoWM2xpjoA


手机扫码阅读