字典工作原理_全文检索引擎Solr系列—–全文检索基本原理

场景&＃xff1a;小时候我们都使用过新华字典&＃xff0c;妈妈叫你翻开第38页&＃xff0c;找到“坑爹”所在的位置&＃xff0c;此时你会怎么查呢&＃xff1f;毫无疑问&＃xff0c;你的眼睛会从38页的第一个字开始从头至尾地扫描&＃xff0c;直到找到“坑爹”二字为止。这种搜索方法叫做顺序扫描法。对于少量的数据&＃xff0c;使用顺序扫描是够用的。但是妈妈叫你查出坑爹的“坑”字在哪一页时&＃xff0c;你要是从第一页的第一个字逐个的扫描下去&＃xff0c;那你真的是被坑了。此时你就需要用到索引。索引记录了“坑”字在哪一页&＃xff0c;你只需在索引中找到“坑”字&＃xff0c;然后找到对应的页码&＃xff0c;答案就出来了。因为在索引中查找“坑”字是非常快的&＃xff0c;因为你知道它的偏旁&＃xff0c;因此也就可迅速定位到这个字。

那么新华字典的目录(索引表)是怎么编写而成的呢&＃xff1f;首先对于新华字典这本书来说&＃xff0c;除去目录后&＃xff0c;这本书就是一堆没有结构的数据集。但是聪明的人类善于思考总结&＃xff0c;发现每个字都会对应到一个页码&＃xff0c;比如“坑”字就在第38页&＃xff0c;“爹”字在第90页。于是他们就从中提取这些信息&＃xff0c;构造成一个有结构的数据。类似数据库中的表结构&＃xff1a;

这样就形成了一个完整的目录(索引库)&＃xff0c;查找的时候就非常方便了。对于全文检索也是类似的原理&＃xff0c;它可以归结为两个过程&＃xff1a;1.索引创建(Indexing)2. 搜索索引(Search)。那么索引到底是如何创建的呢&＃xff1f;索引里面存放的又是什么东西呢&＃xff1f;搜索的的时候又是如何去查找索引的呢&＃xff1f;带着这一系列问题继续往下看。

索引

Solr/Lucene采用的是一种反向索引&＃xff0c;所谓反向索引&＃xff1a;就是从关键字到文档的映射过程&＃xff0c;保存这种映射这种信息的索引称为反向索引

• 左边保存的是字符串序列
• 右边是字符串的文档(Document)编号链表&＃xff0c;称为倒排表(Posting List)

字段串列表和文档编号链表两者构成了一个字典。现在想搜索”lucene”&＃xff0c;那么索引直接告诉我们&＃xff0c;包含有”lucene”的文档有&＃xff1a;2&＃xff0c;3&＃xff0c;10&＃xff0c;35&＃xff0c;92&＃xff0c;而无需在整个文档库中逐个查找。如果是想搜既包含”lucene”又包含”solr”的文档&＃xff0c;那么与之对应的两个倒排表去交集即可获得&＃xff1a;3、10、35、92。

索引创建

假设有如下两个原始文档&＃xff1a;

文档一&＃xff1a;Students should be allowed to go out with their friends, but not allowed to drink beer.

文档二&＃xff1a;My friend Jerry went to school to see his students but found them drunk which is not allowed.

创建过程大概分为如下步骤&＃xff1a;

一&＃xff1a;把原始文档交给分词组件(Tokenizer)

分词组件(Tokenizer)会做以下几件事情(这个过程称为&＃xff1a;Tokenize)&＃xff0c;处理得到的结果是词汇单元(Token)

1. 将文档分成一个一个单独的单词
2. 去除标点符号
3. 去除停词(stop word)

• 所谓停词(Stop word)就是一种语言中没有具体含义&＃xff0c;因而大多数情况下不会作为搜索的关键词&＃xff0c;这样一来创建索引时能减少索引的大小。英语中停词(Stop word)如&＃xff1a;”the”、”a”、”this”&＃xff0c;中文有&＃xff1a;”的&＃xff0c;得”等。不同语种的分词组件(Tokenizer)&＃xff0c;都有自己的停词(stop word)集合。经过分词(Tokenizer)后得到的结果称为词汇单元(Token)。上例子中&＃xff0c;便得到以下词汇单元(Token)&＃xff1a;

"Students"&＃xff0c;"allowed"&＃xff0c;"go"&＃xff0c;"their"&＃xff0c;"friends"&＃xff0c;"allowed"&＃xff0c;"drink"&＃xff0c;"beer"&＃xff0c;"My"&＃xff0c;"friend"&＃xff0c;"Jerry"&＃xff0c;"went"&＃xff0c;"school"&＃xff0c;"see"&＃xff0c;"his"&＃xff0c;"students"&＃xff0c;"found"&＃xff0c;"them"&＃xff0c;"drunk"&＃xff0c;"allowed"

二&＃xff1a;词汇单元(Token)传给语言处理组件(Linguistic Processor)

语言处理组件(linguistic processor)主要是对得到的词元(Token)做一些语言相关的处理。对于英语&＃xff0c;语言处理组件(Linguistic Processor)一般做以下几点&＃xff1a;

1. 变为小写(Lowercase)。
2. 将单词缩减为词根形式&＃xff0c;如”cars”到”car”等。这种操作称为&＃xff1a;stemming。
3. 将单词转变为词根形式&＃xff0c;如”drove”到”drive”等。这种操作称为&＃xff1a;lemmatization。

语言处理组件(linguistic processor)处理得到的结果称为词(Term)&＃xff0c;例子中经过语言处理后得到的词(Term)如下&＃xff1a;

"student"&＃xff0c;"allow"&＃xff0c;"go"&＃xff0c;"their"&＃xff0c;"friend"&＃xff0c;"allow"&＃xff0c;"drink"&＃xff0c;"beer"&＃xff0c;"my"&＃xff0c;"friend"&＃xff0c;"jerry"&＃xff0c;"go"&＃xff0c;"school"&＃xff0c;"see"&＃xff0c;"his"&＃xff0c;"student"&＃xff0c;"find"&＃xff0c;"them"&＃xff0c;"drink"&＃xff0c;"allow"。

经过语言处理后&＃xff0c;搜索drive时drove也能被搜索出来。Stemming 和 lemmatization的异同&＃xff1a;

• 相同之处&＃xff1a;

1. Stemming和lemmatization都要使词汇成为词根形式。

• 两者的方式不同&＃xff1a;

1. Stemming采用的是”缩减”的方式&＃xff1a;”cars”到”car”&＃xff0c;”driving”到”drive”。
2. Lemmatization采用的是”转变”的方式&＃xff1a;”drove”到”drove”&＃xff0c;”driving”到”drive”。

• 两者的算法不同&＃xff1a;

1. Stemming主要是采取某种固定的算法来做这种缩减&＃xff0c;如去除”s”&＃xff0c;去除”ing”加”e”&＃xff0c;将”ational”变为”ate”&＃xff0c;将”tional”变为”tion”。
2. Lemmatization主要是采用事先约定的格式保存某种字典中。比如字典中有”driving”到”drive”&＃xff0c;”drove”到”drive”&＃xff0c;”am, is, are”到”be”的映射&＃xff0c;做转变时&＃xff0c;按照字典中约定的方式转换就可以了。
3. Stemming和lemmatization不是互斥关系&＃xff0c;是有交集的&＃xff0c;有的词利用这两种方式都能达到相同的转换。

三&＃xff1a;得到的词(Term)传递给索引组件(Indexer)

1. 利用得到的词(Term)创建一个字典

1. 对字典按字母顺序排序&＃xff1a;

1. 合并相同的词(Term)成为文档倒排(Posting List)链表

• Document Frequency&＃xff1a;文档频次&＃xff0c;表示多少文档出现过此词(Term)
• Frequency&＃xff1a;词频&＃xff0c;表示某个文档中该词(Term)出现过几次

对词(Term) “allow”来讲&＃xff0c;总共有两篇文档包含此词(Term)&＃xff0c;词(Term)后面的文档链表总共有两个&＃xff0c;第一个表示包含”allow”的第一篇文档&＃xff0c;即1号文档&＃xff0c;此文档中&＃xff0c;”allow”出现了2次&＃xff0c;第二个表示包含”allow”的第二个文档&＃xff0c;是2号文档&＃xff0c;此文档中&＃xff0c;”allow”出现了1次

至此索引创建完成&＃xff0c;搜索”drive”时&＃xff0c;”driving”&＃xff0c;”drove”&＃xff0c;”driven”也能够被搜到。因为在索引中&＃xff0c;”driving”&＃xff0c;”drove”&＃xff0c;”driven”都会经过语言处理而变成”drive”&＃xff0c;在搜索时&＃xff0c;如果您输入”driving”&＃xff0c;输入的查询语句同样经过分词组件和语言处理组件处理的步骤&＃xff0c;变为查询”drive”&＃xff0c;从而可以搜索到想要的文档。

搜索步骤

搜索”microsoft job”&＃xff0c;用户的目的是希望在微软找一份工作&＃xff0c;如果搜出来的结果是:”Microsoft does a good job at software industry…”&＃xff0c;这就与用户的期望偏离太远了。如何进行合理有效的搜索&＃xff0c;搜索出用户最想要得结果呢&＃xff1f;搜索主要有如下步骤&＃xff1a;

一&＃xff1a;对查询内容进行词法分析、语法分析、语言处理

1. 词法分析&＃xff1a;区分查询内容中单词和关键字&＃xff0c;比如&＃xff1a;english and janpan&＃xff0c;”and”就是关键字&＃xff0c;”english”和”janpan”是普通单词。
2. 根据查询语法的语法规则形成一棵树

2. 语言处理&＃xff0c;和创建索引时处理方式是一样的。比如&＃xff1a;leaned–>lean&＃xff0c;driven–>drive

二&＃xff1a;搜索索引&＃xff0c;得到符合语法树的文档集合

三&＃xff1a;根据查询语句与文档的相关性&＃xff0c;对结果进行排序

我们把查询语句也看作是一个文档&＃xff0c;对文档与文档之间的相关性(relevance)进行打分(scoring)&＃xff0c;分数高比较越相关&＃xff0c;排名就越靠前。当然还可以人工影响打分&＃xff0c;比如百度搜索&＃xff0c;就不一定完全按照相关性来排名的。

如何评判文档之间的相关性&＃xff1f;一个文档由多个(或者一个)词(Term)组成&＃xff0c;比如&＃xff1a;”solr”&＃xff0c; “toturial”&＃xff0c;不同的词可能重要性不一样&＃xff0c;比如solr就比toturial重要&＃xff0c;如果一个文档出现了10次toturial&＃xff0c;但只出现了一次solr&＃xff0c;而另一文档solr出现了4次&＃xff0c;toturial出现一次&＃xff0c;那么后者很有可能就是我们想要的搜的结果。这就引申出权重(Term weight)的概念。

权重表示该词在文档中的重要程度&＃xff0c;越重要的词当然权重越高&＃xff0c;因此在计算文档相关性时影响力就更大。通过词之间的权重得到文档相关性的过程叫做空间向量模型算法(Vector Space Model)

影响一个词在文档中的重要性主要有两个方面&＃xff1a;

• Term Frequencey(tf)&＃xff0c;Term在此文档中出现的频率&＃xff0c;ft越大表示越重要
• Document Frequency(df)&＃xff0c;表示有多少文档中出现过这个Trem&＃xff0c;df越大表示越不重要
• 物以希为贵&＃xff0c;大家都有的东西&＃xff0c;自然就不那么贵重了&＃xff0c;只有你专有的东西表示这个东西很珍贵&＃xff0c;权重的公式&＃xff1a;

空间向量模型

文档中词的权重看作一个向量

Document &＃61; {term1, term2, …… ,term N}Document Vector &＃61; {weight1, weight2, …… ,weight N}

把欲要查询的语句看作一个简单的文档&＃xff0c;也用向量表示&＃xff1a;

Query &＃61; {term1, term 2, …… , term N}Query Vector &＃61; {weight1, weight2, …… , weight N}

把搜索出的文档向量及查询向量放入N维度的空间中&＃xff0c;每个词表示一维&＃xff1a;

夹角越小&＃xff0c;表示越相似&＃xff0c;相关性越大