本文来源于Artem Krylysov的博客。
全文搜索是我们每天都在使用却没察觉的常用工具之一。如果您曾经在谷歌上搜索过“Golang覆盖率报告”或试图在电子商务网站上查找“室内无线摄像头”，那么您使用的是某种全文搜索。
全文检索(FTS)是一种用于在大量文档中搜索特定文本的技术。文档可以指网页、报纸文章、电子邮件消息或任何结构化文本。
今天我们将实现一个自己的FTS引擎。在这篇文章的结尾，我们将能够在不到一毫秒的时间内搜索数百万个文档。我们将从简单的搜索开始，比如“找出包含cat这个单词的所有文档”，然后我们将扩展搜索引擎以支持更复杂的布尔查询。
为什么需要FTS
在开始写代码之前，你可能会问“难道我们不能使用grep或循环检查每个文件是否包含我们要搜索的内容吗？”。当然可以。但不是最好的方式。
语料库
我们将搜索英文维基百科的一部分摘要。最新的文档集可以在dumps.wikimedia.org上找到。到目前为止，解压后的文件大小为913 MB。XML文件包含超过600K个文档。
文档例子：
<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=0，第二个文档被分配ID=1，以此类推。
第一次尝试搜索
既然我们已经把所有的文档都加载到内存中，我们就可以试着找到关于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——不算太糟。如果您从输出中抽查一些文档，您可能会注意到该函数也匹配caterpillar和category，但不匹配大写开头的Cat。这不是我们想要的。
再进行下一步之前，我们需要解决两个事情：
- 确保搜索大小写不敏感（因此可以查找Cat）。
- 在单词边界上匹配，而不是在子字符串上匹配(因此caterpillar和 communication不应该匹配)。
使用正则表达式搜索
一个可以同时实现以上两个需求的解决方案是正则表达式。
这里使用(?i)\bcat\b：
- (?i)使正则表达式不区分大小写。
- \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万份文档，搜索开始变得缓慢起来。虽然这种方法很容易实现，但扩展性不好。随着数据集越来越大，我们需要搜索越来越多的文档。该算法的时间复杂度是线性的——需要搜索的文档数量等于文档总数。如果我们有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],
}
下面是一个倒排索引的真实例子。在一本书中的索引:
文本分析
在开始构建索引之前，需要将原始文本分解为适合于索引和搜索的单词(tokens)列表。文本分析器由一个分词器和多个过滤器组成。
分词器
分词器是文本分析的第一步。它的工作是将文本转换为字符串列表。在单词边界上分割文本，并删除标点符号:
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匹配。
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"]
删除常用词
几乎所有的英文文本都包含常用的单词，如a, I, the或be。这样的词叫做停顿词。我们将删除它们，因为几乎所有文档都会包含停顿词。
没有“官方”的停顿词列表。可根据需要添加，下面过滤这些停顿词:
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"]
词根提取
由于单词语法规则的原因，文档可能包含同一个单词的不同形式。词根提取将单词简化为其基本形式。例如，fishing、fishing和fisher可以简化为基本形式fish。实现一个词根提取是一项艰巨的任务，这篇文章没有涉及。我们将使用一个现成库来解析:
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
组合分词器
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结构体是存储索引的很好选择。map中的键是一个字符串，值是文档ID列表:
type index map[string][]int
构建索引包括分析文档并将它们的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 {
// 不重复添加文档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中的每个单词都对应包含该单词的文档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, ...]]
最后，我们可以找到所有包含cat的文件。搜索600K文档用了不到一毫秒(18个µs)!
使用倒排索引，搜索文本的时间复杂度与搜索单词的数量成线性关系。在上面的示例查询中，除了分析输入文本外，搜索只需要执行三次map查找。
布尔查询
上一节的查询为每个查询返回一个分离的文档列表。当我们在搜索框中输入“small wild cat”时，我们通常期望找到的结果是一个列表，其中同时包含了“small”、“wild”和“cat”。下一步是计算列表之间的交集。通过这种方式，我们将得到一个匹配所有单词的文档列表。
幸运的是，倒排索引中的ID是按升序插入的。由于这些id是排序的，所以可以在线性时间内计算两个列表之间的交集。intersection函数同时对两个列表进行迭代，并收集两个列表中都存在的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方法分析给定的查询文本，查找单词并计算相应的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
}
下载的维基百科文件中只有两个文件同时匹配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.
搜索结果符合预期。
总结
我们刚刚建立了一个全文搜索引擎。尽管它很简单，但它可以为更高级的项目提供坚实的基础。
这里没有提到很多能够显著提高性能并让引擎更加友好的内容。以下是一些可以进一步改进的想法:
- 扩展布尔查询以支持OR和NOT
- 将索引存储在磁盘上:
*在每次应用程序重启时重新构建索引可能需要一段时间。- 大量索引可能不适合内存。
- 尝试使用内存和cpu高效的数据格式来存储文档ID集。可以考虑Roaring Bitmaps。
- 支持索引多个文档字段。
*根据相关性对结果排序。
完整的源代码可以在GitHub上找到。
网友评论