实现一个简单的全文检索引擎

发表于 分类于 不明生物：

全文检索是人们每天都在使用的工具之一。如果你曾经在google上搜索过“golang使用情况”或试图在电子商务网站上找到“室内无线摄像头”，你都会使用某种全文检索。

全文检索（FTS）是一种在文档集合中搜索文本的技术。文档可以引用网页、报纸文章、电子邮件或其他任何结构文本。

今天我们要建造我们自己的FTS引擎。在这篇文章的最后，我们将能够在不到一毫秒的时间内搜索数百万个文档。我们将从简单的搜索查询开始，比如“给我包含单词cat的所有文档”，然后扩展引擎以支持更复杂的布尔查询。

注：最著名的FTS引擎是Lucene（以及在此基础上构建的 Elasticsearch 和 Solr ）。

为什么选择FTS

在我们开始编写代码之前，您可能会问：“我们不能只使用grep，或者使用一个循环来检查每个文档是否包含我要查找的单词？” 是的，我们可以，但这并不是最好的方式。

语料库

点击下载 dumps.wikimedia.org 语料。

语料的格式如下：

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>

加载文档

首先，我们需要加载上一步下载的文档。

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，依此类推。

常规搜索测试

关键词搜索

现在我们已经将所有文档加载到内存中，我们可以尝试找到关于猫的文档。首先，让我们遍历所有文档并检查它们是否包含子字符串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也匹配）。

  • 匹配单词边界而不是子字符串（因此caterpiller和communication不匹配）。

正则表达式搜索

一个快速想到并允许实现这两个需求的解决方案是正则表达式。

例如：(?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秒。所以我们还需要优化。

反向索引

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

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],
}

下面是一个倒排索引的真实例子。书名索引书中一个术语引用页码的索引：

Book Index

文本分析

在开始构建索引之前，我们需要将原始文本分解为一个适合索引和搜索的单词（标记）列表。

文本分析器由一个分词器器和多个过滤器组成。

分词器

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

1
2
3
4
5
6
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)
    })
}
1
2
3
> tokenize("A donut on a glass plate. Only the donuts.")

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

过滤器

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

大小写过滤

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

1
2
3
4
5
6
7
func lowercaseFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = strings.ToLower(token)
    }
    return r
}
1
2
3
> 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前10名排除在外。请根据需要添加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}
1
2
3
> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

["donut", "on", "glass", "plate", "only", "donuts"]
去除多形词

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

实现词干分析器是一项非常重要的任务，这篇文章不讨论它。我们将使用现有的模块之一

1
2
3
4
5
6
7
8
9
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
}
1
2
3
> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

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

注: 词干并不总是一个有效的词。例如，airline 和 airlin。

合并
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
}

分词器和过滤器将句子转换成一个标记列表：

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

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

创建索引

回到反向索引, 它将文档中的每个单词映射到文档id。map是存储映射的一个很好选择。map中的键是一个令牌（字符串），值是一个文档ID列表：

1
type index map[string][]int

建立索引包括分析文档并将其ID添加到映射关系中：

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)
}
1
map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]

索引检索

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

1
2
3
4
5
6
7
8
9
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
}
1
2
3
> idx.search("Small wild cat")

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

最后，我们可以找到所有提到猫的文件。搜索60万个文档所用时间不到1毫秒（18微秒）！

使用反向索引时，搜索查询的时间复杂度与搜索词的数量成线性关系。在上面的示例查询中，除了分析输入文本外，search只需执行三次map查找。

Boolean检索

上一节中的查询为每个令牌返回一个分离的文档列表。当我们在搜索框中输入small wild cat时，我们通常期望找到的是同时包含small、wild和cat的结果列表。下一步是计算列表之间的集合交集。这样我们将得到一个匹配所有令牌的文档列表。

幸运的是，反向索引中的id是按升序插入的。由于ID是排序的，所以可以在线性时间内计算两个列表之间的交集。intersection函数同时迭代两个列表，并收集两个列表中存在的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 dump 同时包含匹配 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.

搜索顺利完成。

总结

我们刚刚建立了一个全文搜索引擎。尽管它简单，它可以为更先进的项目奠定坚实的基础。

文中没有提到很多可以显著提高性能和使搜索引擎更人性化的东西。以下是一些进一步改进的想法：

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

  • 在磁盘上存储索引：

    • 每次重新启动应用程序时重建索引可能需要一段时间;

    • 大索引可能无法放入内存;

  • 尝试使用内存和CPU高效的数据格式来存储文档ID集;

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

  • 按相关性对结果排序;

参考

lets-build-a-full-text-search-engine - krylysov

关注作者公众号,获取更多资源!
赏作者一杯咖啡~