Clever Geek Handbook

在Go中编写全文搜索引擎

全文搜索是我们几乎每天都在Internet上搜索某些信息时使用的那些工具之一。全文搜索（FTS）是一种在文档集合中搜索文本的方法。该文档可以链接到网页，报纸文章，电子邮件或任何结构化文本。



今天，我们将要编写自己的FTS引擎。到本文结尾，他将能够在一毫秒内搜索数百万个文档。我们将从简单的搜索查询开始，例如“用cat返回所有文档”，然后扩展引擎以支持更复杂的逻辑查询。



注意：最著名的全文搜索引擎是Lucene（还有Elasticsearch 和Solr建立在其顶部）。



为什么需要FTS



在编写任何代码之前，您可能会问：“难道您不只是使用grep还是一个循环来检查每个文档中的搜索词吗？” 是的你可以。但这并不总是最好的主意。



住房



我们将从英语维基百科中搜索注释的片段。最新的转储位于dumps.wikimedia.org。截至今天，解压缩后的文件大小为913 MB。XML文件包含60万多个文档。



样本文件： 



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


上载文件



首先，您需要使用非常方便的内置包从转储中加载所有文档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： 



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单词感到满意，但对Cat却没有大写字母C表示满意。这并非我们所要的。



在继续之前，有两件事需要解决：



  • 使搜索不区分大小写（以便输出也包括Cat）。

  • 考虑单词边界，而不是子字符串（这样，在输出中就不会出现像毛毛虫和交流这样的单词）。


使用正则表达式搜索



解决这两个问题的一个显而易见的解决方案是正则表达式。



在这种情况下，我们需要(?i)\bcat\b：



  • (?i) 表示正则表达式不区分大小写

  • \b 表示与单词边界相对应（一侧有字符但另一侧没有字符的地方）


但是现在搜索花费了超过两秒钟的时间。如您所见，即使只有60万份文档，系统也开始变慢。尽管此方法易于实现，但伸缩性却不太理想。随着数据集的增长，需要扫描越来越多的文档。此算法的时间复杂度是线性的，也就是说，要扫描的文档数等于文档总数。如果我们有600万个文档而不是60万个文档，则搜索将花费20秒。我们必须提出更好的建议。



倒排索引



为了加快搜索查询速度，我们将预处理文本并建立索引。



FTS的核心是称为倒排索引的数据结构。它将每个单词链接到包含该单词的文档。



例： 



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形式。稍后，当引用索引时，我们还将搜索查询规范化为小写，以便搜索查询cAt找到单词Cat。



删除常用词



几乎所有的英语文本都包含常用词，例如a，I，The或be。它们被称为停用词，几乎存在于所有文档中，因此应将其删除。



没有“官方”停用词列表。让我们消除OEC列表中的前十名。随时补充： 



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"]


抽干



由于语法规则，文档中的单词形式不同。阻止将它们简化为基本形式。例如，捕鱼，捕鱼和渔民都归结为主要的鱼类形式。



实现词干并不是一件容易的事，本文也不会涉及。让我们采用现有模块之一： 



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"]


注意：词根提取器并不总是能正常工作。例如，有些人可能会缩短航线，以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"]


令牌已准备好建立索引。



建立索引



让我们回到倒排索引。它将每个单词与文档ID匹配。内置数据类型非常适合存储地图（显示）map。密钥将是令牌（字符串），值将是文档ID的列表： 



type index map[string][]int


在建立索引的过程中，将分析文档并将其标识符添加到地图： 



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


一切正常！显示中的每个令牌都引用包含该令牌的文档的ID： 



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万个文档花费的时间不到一毫秒（18μs）！



对于倒排索引，搜索查询的时间复杂度与搜索令牌的数量呈线性关系。在上述查询示例中，除了分析输入文本外，仅执行三个地图搜索。



逻辑查询



上一个请求为每个令牌返回了一个未链接的文档列表。但是我们通常希望搜索小型野猫会返回包含small，wild和cat的结果列表。下一步是计算列表之间的交集。这样，我们将获得与所有令牌相对应的文档列表。







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



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
}


更新后的代码search解析给定的查询文本，查找令牌并计算ID列表之间的给定交集： 



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： 



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


搜索按预期工作！



顺便说一句，我首先了解了catopum，这是其中之一：







结论



因此，我们制作了全文搜索引擎。尽管它很简单，但可以为更高级的项目提供坚实的基础。



我没有提到许多可以显着提高性能并使搜索更加方便的方面。以下是一些进一步改进的想法：



  • 添加逻辑运算符OR和NOT。

  • 在磁盘上存储索引：

    • 每次重新启动应用程序时，都需要一些时间来还原索引。

    • 大索引可能无法容纳在内存中。
  • 试用内存和CPU优​​化的数据格式来存储ID集。看看咆哮的位图。

  • 索引文档的多个字段。

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


所有源代码都在GitHub上发布。


More articles:


All Articles