Lucene第二篇:Lucene索引和搜索原理

2018-03-10 11:10:52 +0000

       Lucene第一篇中我提到 “使用Lucene你不必深入了解信息索引及检索的工作原理",解释下这是肯定Lucene优秀的简单易用API,可以避免让我们陷入复杂难懂的搜索算法细节,并不意味着我们可以对此一无所知。虽然可以略过本篇直接讲创建索引的API上代码,但是大概了解下全文索引的概念和运行原理,不管是对于初学者快速入门,还是攻克算法细节立志成为搜索专家都是大有裨益的。

       Lucene要实现搜索必须先建立索引,对文本进行分词处理,创建字典和倒排表等索引文件。

       第一步:准备一些要索引的原文档(Document),也就是文本内容。

       第二步:分析器(Analyzer)语义分析和分词。

          1)分词组件(Tokenizer)将文档分成单独的单词,去除标点符号,去除停词(Stop word),这样就得到词元(Token);

           停词(Stop word)是指一种语言中最普通的没有意义的单词,大多数情况下不能成为搜索的关键词,为减少索引会被排除。英语中停词如:“the”,“a”,“this”等,汉语中停词如“的”,“也”。对于每一种语言的分词组件,都有一个停词集合。

          2)语言处理组件(linguistic processor)会继续对词元进行处理得到词(Term) 。

             英文中词元(Token)会传给语言处理组件(Linguistic Processor)还会进行中Stemming和lemmatization。

             a)变为小写(Lowercase) ;

             b)将单词缩减为词根形式,如“cars ”到“car ”等。这种操作称为:stemming ;

             c)将单词转变为词根形式,如“drove ”到“drive ”等。这种操作称为:lemmatization 。

       第三步:将词(Term)交给索引组件(Indexer),创建字典和倒排表。倒排表除了存储document编号外,还会存储词在document中的位置和出现的频率等信息,下图仅为直观理解索引过程和数据结构,实际索引数据结构远比下图复杂的多。(下图原图来源于互联网,未找到出处链接)

 

       假设要查询单词 “sky”,lucene先对词典二元查找算法找到该词,通过指向倒排表的指针读出所有文章号,然后返回结果。词典通常非常小,整个过程的时间是毫秒级的。而用普通的顺序匹配算法不建索引,逐个遍历所有文章的内容进行字符串匹配,当文章数目和内容量很大时,查询过程将会相当缓慢,耗时往往是无法忍受的。

       可以通过下表格对比数据库的模糊查询,全文检索和数据库模糊查询最大的不同在于,让匹配度最高的前100条结果满足98%以上用户的需求。实际上Lucene会对每一个结果(文档)的匹配度进行评分,再按分数从大到小降序排列。数据库模糊查询没有匹配度高低,只有匹配和不匹配。

 Lucene全文索引引擎数据库
索引将文本数据都通过全文索引一一建立反向索引对于LIKE查询来说,数据传统的索引是根本用不上的。数据需要逐个便利记录进行GREP式的模糊匹配,比有索引的搜索速度要有多个数量级的下降。
匹配效果通过词元(term)进行匹配,通过语言分析接口的实现,可以实现对中文等非英语的支持。使用:like "%net%" 会把netherlands也匹配出来,
多个关键词的模糊匹配:使用like "%com%net%":就不能匹配词序颠倒的xxx.net..xxx.com
匹配度有匹配度算法,将匹配程度(相似度评分高)比较高的结果排在前面。没有匹配程度评分机制:比如有记录中net出现5次和出现1次的,结果是一样的。
结果输出通过特别的算法,将最匹配度最高的头100条结果输出,结果集是缓冲式的小批量读取的。返回所有的结果集,在匹配条目非常多的时候(比如上万条)需要大量的内存存放这些临时结果集。
可定制性通过不同的语言分析接口实现,可以方便的定制出符合应用需要的索引规则(包括对中文的支持)没有接口或接口复杂,无法定制
结论高负载的模糊查询应用,需要负责的模糊查询的规则,索引的文本内容量比较大使用率低,模糊匹配规则简单或者需要模糊查询的文本内容量少

 

相关链接:

字典表的常见结构
Lucene倒排索引原理
搜索引擎:该如何设计你的倒排索引?