shan

制作一个全文搜索引擎

2020-09-20

原文地址：Let’s build a Full-Text Search engine

本文是一片关于搜索引擎文章的翻译，仅供个人学习使用。

全文搜索是人们每天都会使用但却没有意识到的工具之一。如果你用谷歌搜索 “golang coverage report” 或者想在电子商务网站找到 “indoor wireless camera” ，你就会用到某种全文搜索引擎。

全文搜索（Full-Text Search，FTS）是一个在一系列文档进行搜索特定内容的技术。这个文档可能是一个网页，报纸上的一篇文章，一个邮件信息，或者其他类型的内容。

这里我们会去构建一个我们自己的全文搜索引擎。在文章的最后，我们能够在数百万的文档中耗费1毫秒以内搜索到所需的内容。我们会以一个简单的搜索案例开始，例如：在所有文档中搜索带有cat的文档，然后我们会去扩展这个引擎去支持更加复杂的布尔查询。

注：最著名的FTS引擎叫Lucene（如Elasticsearch和solr就是建立在它之上的）。

Why FTS

在我们开始编写代码之前，你可能会问：我们能不能只用grep或者用循环进行检查每个文档，从而找到包含我们寻找内容的文档？答案是可以，但是这不是最好的方法。

Corpus

我们将搜索英语维基百科摘要的一部分。最新的dump位于dumps.wikimedia.org。截至今天，解压缩后的文件大小为913 MB。 XML文件包含超过60万个文档。

文档示例：

1
2
3
<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>

Loading documents

首先，我们需要从dump中中加载所有的文档，内置库encoding/xml处理起来非常方便：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 = 0，第二个ID = 1，依此类推。

First attempt

Searching the content

现在我们把所有的文档都加载到内存里了，我们可以尝试在当中找到有关与cat的文档。最开始，尝试循环所有文档并检查它们中间是否包含cat：

Now that we have all documents loaded into memory, we can try to find the ones about cats. At first, let’s loop through all documents and check if they contain the substring cat:

1
2
3
4
5
6
7
8
9
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，不算太差。如果从输出中检查部分文档，你可能会注意到该函数匹配到了 caterpillar 和 category ，但与 Cat 的大写字母 C 不匹配，那不是我想要的。

我们需要在更进一步之前修复两个问题：

  • 让搜索大小写不敏感（这样就能搜索到Cat了）；
  • 匹配一个单词，而不是子字符串（这样 caterpillar 和communication就不会被匹配到了）。

Searching with regular expressions

很快想到的并且易实现的一个解决方法是使用正则表达式： (?i)\bcat\b，

  • (?i)让表达式大小写不敏感；
  • \b匹配一个单词边界；
1
2
3
4
5
6
7
8
9
10
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万个文档，查找也开始变慢。尽管该方法易于实施，但伸缩性不好。随着数据集变得越来越大，我们需要扫描越来越多的文档。该算法的时间复杂度是线性的，需要扫描的文档数等于文档总数。如果我们有600万个文档而不是60万个文档，则搜索将花费20秒。因此，我们需要更好的方法。

Inverted Index

为了让查找更快，我们将对文本进行预处理并预先建立索引。

FTS的核心是一个称为倒排索引的数据结构。倒排索引将文档中的每个单词与包含该单词的文档相关联。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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],
}

Below is a real-world example of the Inverted Index. An index in a book where a term references a page number:

以下是倒排索引的真实示例。一本书的索引及其中术语引用页码：

img

Text analysis

在我们开始建索引之前，我们需要将源文档拆分成一系列的单词（词项，token），从而适合索引和搜索。文本分析器（text analyzer）由一个标记器（tokenizer）和多个过滤器（filter）组成。

img

Tokenizer

文本分析的第一步是标记。它的工作是将文本转化为一系列token。我们的实现是在单词边界上分割文本并删除标点符号：

1
2
3
4
5
6
7
8
9
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"]

Filters

在大多数情况下，仅将文本转换为token列表是不够的。为了使文本更易于索引和搜索，我们需要进行其他标准化。

Lowercase

为了使搜索不区分大小写，小写过滤器将标记转换为小写。 cAt，Cat 和 caT 被标准化为 cat。稍后，当我们查询索引时，我们也将小写搜索词。这将使搜索词cAt 与文本 Cat 相匹配。

1
2
3
4
5
6
7
8
9
10
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"]

Dropping common words

几乎所有英文文本都包含常用单词，例如a，I，the或be。这些单词称为停用词。我们将删除它们，因为几乎所有文档都将与停用词匹配。

没有停用词的“官方”列表。让我们按OEC排名排除前十名。随时添加更多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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"]

Stemming

由于语法规则，文档可能包含同一单词的不同形式。词干将单词还原为基本形式。例如，fishing，fished和fisher可以简化为基本形式（词干）fish。

实施词干分析器是一项艰巨的任务，本文不做介绍。我们将采用已有的模块之一：

1
2
3
4
5
6
7
8
9
10
11
12
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。

Putting the analyzer together

1
2
3
4
5
6
7
func analyze(text string) []string {
    tokens := tokenize(text)
    tokens = lowercaseFilter(tokens)
    tokens = stopwordFilter(tokens)
    tokens = stemmerFilter(tokens)
    return tokens
}

标记器和过滤器将句子转换为token列表：

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

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

tokens 已准备好建立索引。

Building the index

Back to the inverted index. It maps every word in documents to document IDs. The built-in map is a good candidate for storing the mapping. The key in the map is a token (string) and the value is a list of document IDs:

回到倒排索引，它将文档中的每个单词映射到文档ID。内置map是存储映射的理想选择。映射中的键是token（字符串），值是文档ID的列表：

1
type index map[string][]int

构建索引包括分析文档并将其ID添加到map：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)
}

映射中的每个token都引用包含token的文档的ID：

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

Querying

要查询索引，我们将应用与索引相同的标记器和过滤器：

1
2
3
4
5
6
7
8
9
10
11
12
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, ...]]

最后，我们可以找到所有提及cat的文件。搜索60万文档不到一毫秒（18µs）！

使用倒排索引，搜索查询的时间复杂度与搜索token的数量呈线性关系。在上面的示例查询中，除了分析输入文本外，搜索仅需要执行三次map查找。

Boolean queries

上一节中的查询为每个token返回了一份文档列表。我们通常希望在搜索框中输入small wild cat时找到的结果列表是同时包含small，wild和cat的结果。下一步是计算列表之间的交集。这样，我们将获得与所有标记匹配的文档列表。

img

幸运的是，倒排索引中的ID按升序插入。由于ID已排序，因此可以在线性时间内计算两个列表之间的交集。相交函数同时迭代两个列表，并收集两个列表中都存在的ID：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}

更新后的搜索将分析给定的查询文本，查找令牌并计算ID列表之间的交集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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转储仅包含两个同时匹配small，wild和cat的文档：

1
2
3
4
> 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.

Conclusions

我们刚刚构建了全文搜索引擎。尽管它很简单，但它可以为更高级的项目打下坚实的基础。

我没有涉及很多可以显着提高性能并使引擎更友好的东西。以下是一些进一步改进的想法：

  • 扩展布尔查询以支持OR和NOT。

  • 将索引存储在磁盘上：

    • 每次重新启动应用程序时重建索引可能需要一段时间。
    • 大索引可能无法容纳在内存中。

  • 试用内存和CPU效率高的数据格式来存储文档ID集。Roaring Bitmaps。

  • 支持索引多个文档字段。

  • 按相关性对结果进行排序。

完整的源代码可在GitHub上找到。

Tags: FTS golang
← Python中的异步IO ovs利用流表连接不同网段的子网 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章