全文搜索是人们在不知不觉中每天使用的工具之一。如果您曾经在谷歌上搜索过覆盖报告，或者试图在电子商务网站上查找室内无线摄像头，那么您使用的是某种全文搜索。
全文搜索(FTS)是一种在文档集合中搜索文本的技术。文档可以指网页、报纸文章、电子邮件消息或任何结构化文本。
今天，我们将构建我们自己的FTS引擎。到本文结束时，我们将能够在不到1毫秒的时间内搜索数百万个文档。我们将从简单的搜索查询(如)开始，给出所有包含单词cat；的文档，然后我们将扩展引擎以支持更复杂的布尔查询。
最著名的FTS引擎是Lucene(以及构建在其之上的Elasticsearch和Solr)。
在我们开始编写代码之前，您可能会问，我们不能只使用grep吗？或者使用一个循环来检查是否每个文档都包含单词“我正在寻找？”。是的，我们可以。然而，这并不总是最好的主意。
我们要搜索英文维基百科摘要的一部分。最新的转储可以在dumps.wikimedia.org上找到。截至今天，解压缩后的文件大小为913MB。XML文件包含600K多个文档。
<；title>；维基百科：Kit-Cat Klock<；/Title>；<；url>；https://en.wikipedia.org/wiki/Kit-Cat_Klock<；/url>；<；抽象>；Kit-Cat Klock是一个装饰艺术的新奇挂钟，形状像一只咧嘴笑的猫，卡通的眼睛随着它的摆尾随时间旋转。<；/摘要>；
首先，我们需要从转储中加载所有文档。内置的编码/XML包非常方便：
Import("；coding/xml"；"；os"；)类型文档结构{标题字符串`xml："；title"；`URL字符串`xml："；url"；`文本字符串`xml："；摘要"；`ID int}func loadDocuments(路径字符串)([]document，error){f，err：=os。如果err！=nil{return nil，err}延迟f，则打开(路径)。Close()dec：=xml。NewDecoder(F)dump：=struct{Documents[]document`xml："；doc"；`}{}if err：=dec。解码(&；dump)；err！=nil{return nil，err}docs：=dump。I：=范围文档{docs[i]的文档。Id=i}退回单据，空}。
每个加载的文档都分配了一个唯一的标识符，为了简单起见，第一个加载的文档分配ID=0，第二个分配ID=1，依此类推。
现在我们已经将所有文档加载到内存中，我们可以尝试查找关于猫的文档。首先，让'；循环遍历所有文档并检查它们是否包含子字符串cat：
函数搜索(docs[]document，术语字符串)[]document{var r[]document for_，doc：=range docs{if string。包含(文档。Text，term){r=追加(r，doc)}}返回r}。
在我的笔记本电脑上，搜索阶段耗时103ms--不算太差。如果你从输出中抽查几个文档，你可能会注意到，该函数与caterpillar和类别相匹配，但与Cat的大写字母C不匹配。这不完全是我要找的。
在单词边界而不是子字符串上匹配(因此caterpillar和Communication不匹配)。
一种快速浮现并允许实现这两个需求的解决方案是正则表达式。
\B匹配单词边界(一边是单词字符，另一边不是单词字符的位置)
函数搜索(docs[]document，词汇字符串)[]document{re：=regexp。MustCompile(`(？i)\b`+Term+`\b`)//不要在生产中这样做，这会带来安全风险。学期需要清理一下。Var r[]document for_，doc：=范围文档{如果是。MatchString(文档。Text){r=追加(r，doc)}}返回r}。
啊，搜索花了两秒钟多的时间。如您所见，即使有600K的文档，事情也开始变慢。虽然这种方法很容易实现，但它没有很好的伸缩性。随着数据集变得越来越大，我们需要扫描越来越多的文档。该算法的时间复杂度是线性的--需要扫描的文档数量等于文档总数。如果我们有600万个文档，而不是600K，搜索将需要20秒。我们需要做得更好。
为了使搜索查询更快，我们将对文本进行预处理，并提前建立索引。
FTS的核心是一种称为倒排索引的数据结构，倒排索引将文档中的每个单词与包含该单词的文档相关联。
文档={1："；玻璃盘上的甜甜圈"；，2："；只有甜甜圈"；，3："；听鼓机"；，}index={"；a"；：[1]，"；甜甜圈"；：[1，2]，"；on"；：[1]，"；玻璃"；：[1]，"；板材"；：[1]，"；仅"；：[2]，"；"；：[2，3]，"；收听"；：[3]，"；至"；：[3]，"；鼓"；：[3]，"；机器"；：[3]，}。
下面是倒排索引的真实示例。书中术语引用页码的索引：
在开始构建索引之前，我们需要将原始文本分解成适合索引和搜索的单词(标记)列表。
标记器是文本分析的第一步。它的工作是将文本转换为令牌列表。我们的实现在单词边界上拆分文本并删除标点符号：
函数标记化(文本字符串)[]string{返回字符串。FieldsFunc(text，func(R Rune)bool{//拆分不是字母或数字的任何字符。回来！Unicode。IsLetter(R)&；&；！Unicode。IsNumber(R)})}。
将玻璃盘上的甜甜圈标记化(>；tokenize(>；tokenize))。仅限甜甜圈。"；)["；A"；，"；甜甜圈"；，"；上"；，"；，"；玻璃"；，"；盘子"；，"；仅"；，"；甜甜圈"；，"；]。
在大多数情况下，仅将文本转换为令牌列表是不够的。为了使文本更容易索引和搜索，我们需要进行额外的规范化。
为了使搜索不区分大小写，小写过滤器将令牌转换为小写。猫、猫和猫被规范化为猫。稍后，当我们查询索引时，我们也会将搜索词小写。这将使搜索词CAT与文本Cat匹配。
Func lowercaseFilter(tokens[]string)[]string{r：=make([]string，len(Tokens))for i，Token：=Range Tokens{r[i]=string。Tolower(Token)}返回r}。
>；lowercaseFilter([]string{"；A"；，"；甜甜圈"；，"；上的"；，"；，"；玻璃"；，"；盘子"；，"；仅"；，"；"；，"；甜甜圈"；})["；a"；，"；甜甜圈"；，"；上的"；，"；，"；玻璃"；，"；板"；，"；仅"；，"；上的"；，"；甜甜圈"；]。
几乎所有的英文文本都包含像a、i、the或be这样的常用单词。这样的话被称为“停用词”。我们将删除它们，因为几乎所有文档都会匹配停用字词。
没有官方的停用词列表。让我们按照OEC排名排除前10名。您可以随时添加更多内容：
Var stopwords=map[string]struct{}{//我希望Go有内置的集合。"；a"；：{}，"；和"；：{}，"；为"；：{}，"；具有"；：{}，"；i"；：{}，"；位于"；：{}，"；中：{}，"；那个"；：{}，"；"；：{}，"；到"；：{}，}func stopwordFilter(tokens[]string)[]string{r：=make([]string，0，len(Tokens))for_，Token：=Range Tokens{if_，ok：=stopwords[Token]；！确定{r=追加(r，Token)}}返回r}。
>；stopwordFilter([]string{"；a"；，"；甜甜圈"；，"；上的"；，"；，"；玻璃"；，"；盘"；，"；仅"；，"；甜甜圈"；})["；甜甜圈"；})["；甜甜圈"；})["；甜甜圈"；，"；在"；，"；玻璃"；，"；盘子"；，"；上仅"；，"；甜甜圈"；]。
由于语法规则的原因，文档可能包含同一单词的不同形式。模版将单词缩减为其基本形式。例如，垂钓、捕捞和捕捞可能会被简化为基型(茎)鱼。
实现词干分析器不是一件微不足道的任务，这篇文章中没有涉及到这一点。我们将选择现有模块之一：
为i导入Snowball Eng"；github.com/kljensen/snowball/english"；Func stemmerFilter(Tokens[]String)[]String{r：=Make([]String，len(Tokens)，Token：=范围令牌{r[i]=Snowball Eng。STEM(TOKEN，FALSE)}返回r}。
词干并不总是有效的单词。例如，一些干枝可能会将航空公司减少到航空公司。
Func Analyze(文本字符串)[]string{tokens：=tokenize(文本)tokens=lowercaseFilter(Tokens)tokens=stopwordFilter(Tokens)tokens=stemmerFilter(Tokens)返回令牌}。
>；分析(玻璃盘上的甜甜圈。仅限甜甜圈。"；)["；甜甜圈"；，"；上"；，"；，"；盘子"；，"；仅"；，"；甜甜圈"；]
回到倒排索引。它将文档中的每个单词映射到文档ID。内置映射是存储映射的理想候选。映射中的键是令牌(字符串)，值是文档ID列表：
构建索引包括分析文档并将其ID添加到地图中：
函数(idx索引)add(docs[]document){for_，doc：=范围文档{for_，Token：=范围分析(doc.。Text){ids：=idx[Token]if ids！=nil&；&；ids[len(Ids)-1]==doc。ID{//不要添加同一ID两次。CONTINUE}IDX[TOKEN]=APPEND(ID，doc.。Id)}func main(){idx：=make(Index)idx。在玻璃盘上添加([]文档{{ID：1，text："；一个甜甜圈。只有甜甜圈。"；})IDX。添加([]文档{{ID：2，text："；Donut is a Donut"；}})fmt。Println(IDX)}。
它起作用了!。映射中的每个令牌都引用包含该令牌的文档的ID：
要查询索引，我们将应用用于索引的相同标记器和筛选器：
函数(idx索引)search(文本字符串)[][]int{var r[][]int for_，TOKEN：=范围分析(文本){IF ID，ok：=IDX[TOKEN]；ok{r=append(r，id)}}返回r}。
>；idx。搜索("；小野猫"；)[[24,173,303，...]，[98,173,765，...]，[[24，51,173，...]]。
最后，我们可以找到所有提到猫的文件。搜索600K文档只用了不到1毫秒(18微秒)！
利用倒排索引，搜索查询的时间复杂度与搜索标记的数量成线性关系。在上面的示例查询中，除了分析输入文本之外，Search只需要执行三次地图查找。
上一节中的查询返回每个令牌的独立文档列表。当我们在搜索框中键入Small Wildcat时，通常会发现同时包含Small、Wild和CAT的结果列表。下一步是计算列表之间的集合交集。这样，我们将获得与所有令牌匹配的文档列表。
幸运的是，倒排索引中的ID是按升序插入的。由于ID是排序的，所以可以在线性时间内计算两个列表之间的交集。交集函数同时迭代两个列表，并收集两个列表中都存在的ID：
函数交集(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++}}返回r}。
更新的搜索分析给定的查询文本，查找令牌，并计算ID列表之间的集合交集：
函数(idx索引)search(文本字符串)[]int{var r[]int for_，TOKEN：=范围分析(文本){IF ID，ok：=IDX[TOKEN]；OK{IF r==nil{r=IDS}ELSE{r=交集(r，ID)}}ELSE{//TOKEN不存在。返回nil}}返回r}。
维基百科转储只包含两个同时匹配Small、Wild和cat的文档：
>；idx。搜索(#34；小野猫)130764野猫是一个物种复合体，由两个小野猫物种组成，欧洲野猫(Felis Silvestris)和非洲野猫(F.。利比卡)。131692猫科动物是一个包含两个亚洲小型野生猫科动物的属，即亚洲金猫(C.。Temminckii)和海湾猫。
顺便说一下，这是我第一次听说Catopuma，这是其中之一：
我们刚刚建立了一个全文搜索引擎。尽管它很简单，但它可以为更高级的项目奠定坚实的基础。
我没有提到很多可以显著提高性能并使引擎更加用户友好的东西。以下是一些进一步改进的想法：
尝试使用内存和CPU高效的数据格式来存储文档ID集。看看咆哮的位图。