ElasticSearch 倒排索引(Inverted Index) |
您所在的位置:网站首页 › 倒排索引是什么数据结构的 › ElasticSearch 倒排索引(Inverted Index) |
简约理解版本2.0
正向索引,数据库创建索引,增加搜索速度。 倒排索引是根据关键字去找文档,然后记录一下出现的位置和次数。 分词=>倒排索引=>优化 Posting List /倒排列表(出现的id:位置:次数) 什么是倒排索引?ElasticSearch中一个重要的概念 : 倒排索引(Inverted Index)也叫反向索引,有反向索引必有正向索引。通俗地来讲,正向索引是通过key找value,反向索引则是通过value找key。 首先弄懂几个概念,如果类比现代汉语词典的话,那么Term就相当于词语,Term Dictionary相当于汉语词典本身,Term Index相当于词典的目录索引,Posting List相当于词语在字典的页数集合: Term(单词):一段文本经过分析器分析以后就会输出一串单词,这一个一个的就叫做Term(直译为:单词)Term Dictionary(单词字典):顾名思义,它里面维护的是Term,可以理解为Term的集合Term Index(单词索引):为了更快的找到某个单词,我们为单词建立索引。B-Tree通过减少磁盘寻道次数来提高查询性能,Elasticsearch也是采用同样的思路,直接通过内存查找term,不读磁盘,但是如果term太多,term dictionary也会很大,放内存不现实,于是有了Term Index,就像字典里的索引页一样,A开头的有哪些term,分别在哪页,可以理解term index是一颗树:Posting List(倒排列表):倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。(PS:实际的倒排列表中并不只是存了文档ID这么简单,还有一些其它的信息,比如:词频(Term出现的次数)、偏移量(offset)等,可以想象成是Python中的元组,或者Java中的对象) 倒排DEMO {"doc_id"="1","hospitalName":"北京大学第三附属医院"} {"doc_id"="2","hospitalName":"北京协和医院"} {"doc_id"="3","hospitalName":"解放军总医院第一附属医院"} {"doc_id"="4","hospitalName":"Peking University Third Hospital"} {"doc_id"="5","hospitalName":"Peking Union Medical College Hospital"}*.部分等你一边思考一边补充: Term ID / 单词IDTerm / 单词Posting List /倒排列表(出现的id:位置:次数)1医院(1::1),(2::1),(3::2)2北京(1::1),(2::1)3北京大学(1::1)4第三(1::1)5附属(1::1),(3::1)6协和(2::1)7解放军(3::1)8第一(3::1)9总(3::1) 标准化规则(normalization)&命中率问题为解决词条检索时词条命中率,ES在建立倒排索引时运用标准化规则即针对存储的索引词条进行一些相关预处理再作为索引进行存储。 例如:通常情况下,在搜索 Third 、 Hospital 这两个单词时候,文档4两个单词都出现了,计数为2;文档5只有 Hospital 这个单词出现了,计数为1,所以Total之后,文档4命中率高,排名靠前。 Termdoc_id=4doc_id=5Third10Hospital11Peking11Total32但是这样搜索就会存在下列问题: Third 与 third 用户认为是相同单词,但是首字母小写可能搜不到内容。hospitals 与 hospital 有相同的词根,如果存储了 hospitals ,那么 hospital 可能检索不到 。piking 与 beijing 为相同意思的词,如果存储了 piking , beijing 可能检索不到。基于以上问题,ES在建立倒排索引时,会对拆分的各个单词进行相应处理,以提升后面搜索的时候能够搜索到相关联的文档的概率,这就是标准化规则转换,主要包括:时态的转换(例如liked转换为like)、单复数的转换(hospitals转换为hospitals)、同义词的转换(small转换为little)、大小写的转换(默认转换为小写)。 标准分词器standard analyzerstandard analyzer 标准分词器中做的操作,跟标准化规则有一定关联: standard tokenizer:以单词边界进行切分standard token filter:什么都不做lowercase token filter:将所有字母转换为小写(by normalization)stop token filer(默认被禁用):移除停用词,比如a the it等等 相关度分数score的计算当利用ES进行查询时,查询结果都会返回一个对应词条的相关度分数(score)。相关度分数的计算基于TF/IDF算法(Term Frequence&Inverse Doucument Frequency),翻译大意为:词条在文档中出现的频率及在倒排索引中出现的频率。 Term Frequence ,TF(t in f):我们查询的词条在文本中出现多少次,出现次数越多,相关度越高。例如:前面所列医院信息文档中,“医院”,“北京大学”这两个单词,在第1文档中都出现了,但是第2和第3个文档只出现了“医院”,所以第1个相关度分数高。Inverse Doucument Frequency,IDF(t in all-f):查询词条在所有文本中出现的次数,出现次数越高,相关度越低。例如:“医院”在3个文档中出现4次,而“北京大学”出现1次,所以“医院”这个单词的相关度越低。Field-length(字段长度规约):字段的长度越长,相关度越低。例如:“北京大学第三附属医院”长度大于“北京协和医院”,那么在检索“医院”这个单词时,第二个文档中分数要大于第一个文档的分数。So,ES相关度分数计算结果直接影响搜索排名顺序,对用户检索命中率有极大的影响。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |