Coding Morning

GoFound核心源码浅析

作者: nbboy
时间: 2022-07-28
分类: 默认分类
评论

### 1.索引文档的过程

1）词典结构怎么表示 2）文档怎么存储 3）索引列表怎么存储

1）,3）首先对用户的查询进行分词，比如分词结果为S = {w1, w2, w3}，然后对w1进行分片计算Hash槽，分片算法为StringsToInt(w1) % Shard，目前分为10个Hash槽，这样做是为了把所有词典均匀分散开，类似分库的原理，而且这10个“库”的数据文件是分开存储的。根据w1从数据文件中能够获得索引列表，这些索引列表是由文档ID组成。在索引文档的时候，如果该文档ID不在这个索引列表中，就添加进去，值得一提的是ID的查找算法用的是二分查找算法。

![](https://chenxf.org/usr/uploads/2022/07/2175406851.png)

Figure1 倒排索引

2）文档存储也是采用分区存储，也同样存在leveldb中，分区ID计算方法为DocID % Shard。文档存储就以键为分区ID，值为文档内容进行存储，另外为了计算相关性，存储了键为分区ID，值为文档分词序列的正排索引。

![](https://chenxf.org/usr/uploads/2022/07/4240150671.png)

Figure2 文档存储

![](https://chenxf.org/usr/uploads/2022/07/247337852.png)

Figure3 分词存储，用来计算相关性

### 2.检索文档的过程

1）索引列表怎么合并和排序

读取词的倒排列表，合并后计算词的文档频率，并且根据这个值进行倒序，这个实现只考虑了文档频率，并没有考虑词的频率。计算分页的文档后，从库中获取文档内容返回给前端，整个实现过程还是非常简单。

![](https://chenxf.org/usr/uploads/2022/07/1497425236.png)

Figure4 比如检索"伟大人民",首先会对检索语句进行分词,分为“伟大”和“人民”，然后在倒排索引里获取这两个词的倒排列表。接下来第一步倒排列表会先放在一起，再进行排序，第二步会用一个散列表算出每个文档频率，第三步对这个散列表按照文档频率进行排序。

### 3.源码
[gofound](https://github.com/sea-team/gofound "gofound")

让我们一起构建全文搜索引擎(引用)

作者: nbboy
时间: 2022-07-28
分类: 默认分类
评论

> 在搜索资料的时候感觉这篇文章对入门《搜索引擎》还不错，所以翻译了一下，在此保留。

## 让我们一起构建全文搜索引擎

全文搜索引擎我们每天都会使用的一种工具，只不过我们没有意识到它。如果你以前在Google搜索过golang覆盖率报告，或者在购物网站搜索过室内摄像头，你就一定使用过某种类型的全文搜索引擎。

全文搜索引擎是一种在许多文档中搜索文本的技术。一个文档可以是网页，或者新闻文章，邮箱页面，或者任何结构化的信息。今天我们会构建自己的全文搜索引擎。在文末结束的时候，我们能够在少于毫秒的时间内搜索百万级别的文档。从像简单的“返回包含单词猫的所有文档”和扩展搜索引擎支持更加复杂的布尔查询。

### 为什么是全文搜索

在开始写代码之前，你可能会问“我们为什么不用Grep或者用循环检测每个文档是否包含某个词语？”，是的，我们能这样做，然而这个不是一个好主意。

### 本文的文档集

我们将搜索英文Wikipedia的部分文档。最后的转储在[dumps.wikimedia.org](https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-abstract1.xml.gz)，大概到今天，解压缩后大小为913MB,所有的XML文件包含600K文档。

文档例子为：

```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>
```

### 加载文档

首先从转储中加载所有的文档，在Golang中使用encoding/xml包可以很方便做到这点。

```go
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：

```go
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
}
```

在我的笔记本电脑上，搜索需要 103 毫秒 - 还不错。但是如果我们检查搜索的结果，就发现有点问题，比如用该函数可能包含了*caterpillar*和*category*，但是不包含包含大写C的Cat，当然这个不是我们想要的。

所以，在继续之前，我们需要解决两件事：

- 搜索结果对大小写不敏感
- 匹配单词边界而不是子字符串（比如*caterpillar*和*communication*就不能被匹配）

##### 通过正则搜索

能够快速想到解决这个问题的办法就是正则表达式，在这个例子中就是(?i)\bcat\b：

- (?i)可以让大小写不敏感
- \b能够匹配单词的边界

```go
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
}
```

有点惊讶，居然用了两秒才能够搜索完成。如您所见，即使有 600K 文档，事情也开始变得缓慢。虽然该方法挺方便，但它的扩展性并不好。随着数据集越来越大，我们需要扫描越来越多的文档。**该算法的时间复杂度是线性的**，需要扫描的文件数量等于文件总数。如果我们有 600 万个文档而不是 60 万个文档，那么搜索将需要 20 秒。我们需要寻找更加好的方法。

### 倒排索引

为了使搜索查询更快，我们将对文本进行预处理并提前建立索引。全文搜索的核心是一种称为倒排索引的数据结构。倒排索引将文档中的每个单词与包含该单词的文档相关联。

例子:

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

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

![img](https://artem.krylysov.com/images/2020-fts/book-index.png)

### 文本分析

在开始构建索引之前，我们需要将原始文本分解为适合索引和搜索的单词标记。文本分析器由一个分词器和多个过滤器组成。

![img](https://artem.krylysov.com/images/2020-fts/text-analysis.png)

### 分词器

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

```go
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)
    })
}
```

```shell
> tokenize("A donut on a glass plate. Only the donuts.")

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

### 过滤器

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

##### 小写

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

```go
func lowercaseFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = strings.ToLower(token)
    }
    return r
}
```

```shell
> lowercaseFilter([]string{"A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"})

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

##### 删除常用词

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

没有“官方”停用词列表。当然我们能够添加更多：

```go
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
}
```

```shell
> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

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

##### 词干过滤

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

实现一个词干分析器是一个非常重要的任务，这篇文章没有涉及,而是直接使用了一个模块:

```go
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
}
```

```shell
> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

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

##### 将分析器放在一起

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

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

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

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

标记已准备好进行索引。

##### 构建索引

回到倒排索引。它将文档中的每个单词映射到文档 ID。内置映射是存储这种映射的一个很好的方法。映射中的键是一个单词，值是一个文档 ID 列表:

```go
type index map[string][]int
```

构建索引包括分析文档并将其 ID 添加到映射中:

```go
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)
}
```

OK! 映射中的每个标记都引用了包含该标记的文档的 ID:

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

##### 查询

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

```go
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
}
```

```shell
> idx.search("Small wild cat")

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

最后，我们可以找到所有提到Cat的文件。搜索 600K 文档只需不到一毫秒 (18µs)！使用倒排索引，搜索查询的时间复杂度与搜索标记的数量成线性关系。在上面的示例查询中，除了分析输入文本之外，搜索只需要执行三个map查找。

##### 布尔查询

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

![img](https://artem.krylysov.com/images/2020-fts/venn.png)

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

```go
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 列表之间的集合交集

```go
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 的文档：

```shell
> 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，这是其中之一：

![By Karen Stout - originally posted to Flickr as Asian Golden cat, CC BY-SA 2.0, https://commons.wikimedia.org/w/index.php?curid=11413240](https://artem.krylysov.com/images/2020-fts/asian-golden-cat-s.jpg)

### 总结

我们刚刚构建了一个全文搜索引擎。尽管它很简单，但它可以为更高级的项目奠定坚实的基础。我没有涉及很多可以显着提高性能并使引擎更加友好的内容。以下是一些进一步改进的想法：

- 扩展布尔查询以支持 OR 和 NOT。
- 将索引存储在磁盘上：
  - 在每次应用程序重新启动时重建索引可能需要一段时间。
  - 大量索引放在内存里也不合适
- 尝试使用内存和 CPU 高效的数据格式来存储文档 ID 集。看看[Roaring Bitmaps](https://roaringbitmap.org/)。
- 支持索引多个文档字段。
- 按相关性对结果进行排序。

结构之美碎碎念

GoFound核心源码浅析

让我们一起构建全文搜索引擎(引用)

图片处理解决方案Gimg发布了

基础知识

最新文章

最近回复

分类

归档

其它