本文來源于Artem Krylysov的博客。
全文搜索是我們每天都在使用卻沒察覺的常用工具之一。如果您曾經(jīng)在谷歌上搜索過“Golang覆蓋率報(bào)告”或試圖在電子商務(wù)網(wǎng)站上查找“室內(nèi)無線攝像頭”，那么您使用的是某種全文搜索。
全文檢索(FTS)是一種用于在大量文檔中搜索特定文本的技術(shù)。文檔可以指網(wǎng)頁、報(bào)紙文章、電子郵件消息或任何結(jié)構(gòu)化文本。
今天我們將實(shí)現(xiàn)一個(gè)自己的FTS引擎。在這篇文章的結(jié)尾，我們將能夠在不到一毫秒的時(shí)間內(nèi)搜索數(shù)百萬個(gè)文檔。我們將從簡(jiǎn)單的搜索開始，比如“找出包含cat這個(gè)單詞的所有文檔”，然后我們將擴(kuò)展搜索引擎以支持更復(fù)雜的布爾查詢。

為什么需要FTS

在開始寫代碼之前，你可能會(huì)問“難道我們不能使用grep或循環(huán)檢查每個(gè)文件是否包含我們要搜索的內(nèi)容嗎？”。當(dāng)然可以。但不是最好的方式。

語料庫

我們將搜索英文維基百科的一部分摘要。最新的文檔集可以在dumps.wikimedia.org上找到。到目前為止，解壓后的文件大小為913 MB。XML文件包含超過600K個(gè)文檔。
文檔例子：

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

加載文檔

我們需要將所有的文件加載到內(nèi)存。內(nèi)置的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
}

每個(gè)加載的文檔都被分配一個(gè)惟一的標(biāo)識(shí)符。為了簡(jiǎn)單起見，第一個(gè)加載的文檔被分配ID=0，第二個(gè)文檔被分配ID=1，以此類推。

第一次嘗試搜索

既然我們已經(jīng)把所有的文檔都加載到內(nèi)存中，我們就可以試著找到關(guān)于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——不算太糟。如果您從輸出中抽查一些文檔，您可能會(huì)注意到該函數(shù)也匹配caterpillar和category，但不匹配大寫開頭的Cat。這不是我們想要的。
再進(jìn)行下一步之前，我們需要解決兩個(gè)事情：

• 確保搜索大小寫不敏感（因此可以查找Cat）。
• 在單詞邊界上匹配，而不是在子字符串上匹配(因此caterpillar和 communication不應(yīng)該匹配)。

使用正則表達(dá)式搜索

一個(gè)可以同時(shí)實(shí)現(xiàn)以上兩個(gè)需求的解決方案是正則表達(dá)式。
這里使用(?i)\bcat\b：

• (?i)使正則表達(dá)式不區(qū)分大小寫。
• \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
}

搜索過程花了兩秒多。正如您所看到的，即使只有60萬份文檔，搜索開始變得緩慢起來。雖然這種方法很容易實(shí)現(xiàn)，但擴(kuò)展性不好。隨著數(shù)據(jù)集越來越大，我們需要搜索越來越多的文檔。該算法的時(shí)間復(fù)雜度是線性的——需要搜索的文檔數(shù)量等于文檔總數(shù)。如果我們有600萬份而不是60萬份文件，搜索將需要20秒。我們需要更好方法。

倒排索引

為了使搜索更快，我們將對(duì)文本進(jìn)行預(yù)處理并預(yù)先構(gòu)建索引。
FTS全文搜索的核心是一種稱為倒排索引的數(shù)據(jù)結(jié)構(gòu)。倒排索引將文檔中的每個(gè)單詞與包含該單詞的文檔關(guān)聯(lián)起來。
例如：

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

下面是一個(gè)倒排索引的真實(shí)例子。在一本書中的索引:

文本分析

在開始構(gòu)建索引之前，需要將原始文本分解為適合于索引和搜索的單詞(tokens)列表。文本分析器由一個(gè)分詞器和多個(gè)過濾器組成。

分詞器

分詞器是文本分析的第一步。它的工作是將文本轉(zhuǎn)換為字符串列表。在單詞邊界上分割文本，并刪除標(biāo)點(diǎn)符號(hào):

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

結(jié)果：

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

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

過濾器

在大多數(shù)情況下，僅僅將文本轉(zhuǎn)換為字符串列表是不夠的。為了使文本更容易索引和被搜索，我們需要做額外的規(guī)范化。

小寫字母

為了使搜索不區(qū)分大小寫，小寫字母過濾器將字符串轉(zhuǎn)換為小寫。cAT，Cat和caT統(tǒng)一為cat。稍后，當(dāng)我們查詢索引時(shí)，我們也會(huì)將搜索條件設(shè)置為小寫。這將使搜索詞cAt與文本cAt匹配。

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

結(jié)果：

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

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

刪除常用詞

幾乎所有的英文文本都包含常用的單詞，如a, I, the或be。這樣的詞叫做停頓詞。我們將刪除它們，因?yàn)閹缀跛形臋n都會(huì)包含停頓詞。
沒有“官方”的停頓詞列表?？筛鶕?jù)需要添加，下面過濾這些停頓詞:

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
}

結(jié)果：

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

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

詞根提取

由于單詞語法規(guī)則的原因，文檔可能包含同一個(gè)單詞的不同形式。詞根提取將單詞簡(jiǎn)化為其基本形式。例如，fishing、fishing和fisher可以簡(jiǎn)化為基本形式fish。實(shí)現(xiàn)一個(gè)詞根提取是一項(xiàng)艱巨的任務(wù)，這篇文章沒有涉及。我們將使用一個(gè)現(xiàn)成庫來解析:

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
}

結(jié)果：

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

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

備注：詞根并不總是一個(gè)有效的單詞。例如，一些詞根提取可能會(huì)將airline縮減為airlin

組合分詞器

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

分詞器和過濾器將英文句子轉(zhuǎn)換為單詞列表。

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

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

這些單詞可以作為索引。

構(gòu)建索引

回到倒排索引。它將文檔中的每個(gè)單詞映射到文檔ID。內(nèi)置Map結(jié)構(gòu)體是存儲(chǔ)索引的很好選擇。map中的鍵是一個(gè)字符串，值是文檔ID列表:

type index map[string][]int

構(gòu)建索引包括分析文檔并將它們的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 {
                // 不重復(fù)添加文檔ID.
                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中的每個(gè)單詞都對(duì)應(yīng)包含該單詞的文檔ID列表。

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

查詢

要查詢索引，我們將應(yīng)用與索引時(shí)相同的分詞器和過濾器:

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
}

結(jié)果：

> idx.search("Small wild cat")

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

最后，我們可以找到所有包含cat的文件。搜索600K文檔用了不到一毫秒(18個(gè)μs)!
使用倒排索引，搜索文本的時(shí)間復(fù)雜度與搜索單詞的數(shù)量成線性關(guān)系。在上面的示例查詢中，除了分析輸入文本外，搜索只需要執(zhí)行三次map查找。

布爾查詢

上一節(jié)的查詢?yōu)槊總€(gè)查詢返回一個(gè)分離的文檔列表。當(dāng)我們?cè)谒阉骺蛑休斎搿皊mall wild cat”時(shí)，我們通常期望找到的結(jié)果是一個(gè)列表，其中同時(shí)包含了“small”、“wild”和“cat”。下一步是計(jì)算列表之間的交集。通過這種方式，我們將得到一個(gè)匹配所有單詞的文檔列表。

幸運(yùn)的是，倒排索引中的ID是按升序插入的。由于這些id是排序的，所以可以在線性時(shí)間內(nèi)計(jì)算兩個(gè)列表之間的交集。intersection函數(shù)同時(shí)對(duì)兩個(gè)列表進(jìn)行迭代，并收集兩個(gè)列表中都存在的ID:

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方法分析給定的查詢文本，查找單詞并計(jì)算相應(yīng)的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
}

下載的維基百科文件中只有兩個(gè)文件同時(shí)匹配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.

搜索結(jié)果符合預(yù)期。

總結(jié)

我們剛剛建立了一個(gè)全文搜索引擎。盡管它很簡(jiǎn)單，但它可以為更高級(jí)的項(xiàng)目提供堅(jiān)實(shí)的基礎(chǔ)。
這里沒有提到很多能夠顯著提高性能并讓引擎更加友好的內(nèi)容。以下是一些可以進(jìn)一步改進(jìn)的想法:

• 擴(kuò)展布爾查詢以支持OR和NOT
• 將索引存儲(chǔ)在磁盤上:
  *在每次應(yīng)用程序重啟時(shí)重新構(gòu)建索引可能需要一段時(shí)間。
  • 大量索引可能不適合內(nèi)存。
• 嘗試使用內(nèi)存和cpu高效的數(shù)據(jù)格式來存儲(chǔ)文檔ID集?？梢钥紤]Roaring Bitmaps。
• 支持索引多個(gè)文檔字段。
  *根據(jù)相關(guān)性對(duì)結(jié)果排序。
  完整的源代碼可以在GitHub上找到。