image
内容概要
- 倒排索引是什么？为什么需要倒排索引？
- 倒排索引是怎么工作的？
1. 倒排索引是什么？
假设有一个交友网站，信息表如下：
image
美女1：“我要找在上海做 PHP 的哥哥。”
需要匹配 性别、城市、语言列。
美女2：“我要找北京的爱旅游、爱美食的 JAVA 哥哥。”
更复杂了是吧，实际场景中，会有更复杂的排列组合。
对于这类的搜索，关系型数据库的索引就很难应付了，适合使用全文搜索的倒排索引。
倒排索引是一种数据库的索引形式，存储了 “内容 -> 文档” 映射关系，目的是快速的进行全文搜索。
2. 倒排索引是怎么工作的？
主要包括2个过程：
- 创建倒排索引
- 倒排索引搜索
2.1 创建倒排索引
举个例子，有2个文档：
- Document#1
“Recipe of pasta with sauce pesto”
- Document#2
“Recipe of delicious carbonara pasta”
先对文档进行分词，形成一个个的 token，也就是 单词，然后保存这些 token 与文档的对应关系。
结果如下：
image
2.2 倒排索引搜索
搜索示例：
- 搜索 “pasta recipe”**
先分词，得到2个 token，( “pasta”、“recipe” )。
然后去倒排索引中进行匹配。
image
这2个词在2个文档中都匹配，所以2个文档都会返回，而且分数相同。
- 搜索 “carbonara pasta”**
image
同样，2个文档都匹配，都会返回。
这次 document#2 的分数要比 document#1 高。
因为 #2 匹配了2个词（“carbonara”、“pasta”），#1 只匹配了一个（“pasta”）。
2.3 转换
有时我们可以在保存和搜索之前对 token 进行一些转换，最普遍的例如：
- 扔掉停止词
停止词是那些使用量非常大，但又没有什么意义的词。
例如英文中的 “of”, “the”, “for” ……
- 元素化
把单词处理为字典中的标准词，例如：
“running” => “run”
“walks” => “walk”
“thought” =>“think”
- 词干分析
通过切断词尾将一个词转换成词根形式的过程。
不能处理不规则动词的情况，但可以处理字典中没有的词。
推荐阅读：
image
网友评论