全文搜索的基本原理

此文内容大多是阅读了Lucene原理与代码分析一文，以及网络上一些其他文章的总结
Lucene原理与代码分析 作者：觉先(forfuture1978)

数据分类

• 结构化数据：具有固定格式或有限长度的数据，如关系型数据库（先有结构再有数据）
• 半结构化数据：如XML、HTML，数据的结构和内容混在一起，没有明显的区分（先有数据再有结构）
• 非结构化数据：无固定格式或不定长度的数据，包括所有格式的办公文档、文本、图片、图像、音频、视频信息等等

非结构化数据搜索（全文搜索）

• 顺序扫描法：一个文档一个文档的找，对于每一个文档，从头找到尾，如果此文档找到指定的内容，则此文档为我们要找的文件，接着找下一个文件，直到扫描完所有的文件为止。这种方法对小数据量来说是最直接最方便的，但对于大数据量处理就太耗时了。
• 索引搜索法：将非结构化数据中一部分内容提取出来，重新组织，使其变为有一定的结构，然后对此有一定结构的数据进行搜索，以达到加快搜索的目的。

倒排索引（Inverted Index）
倒排索引是目前搜索引擎最常用的存储方式，也是搜索引擎的核心！在搜索时我们一般按照某些关键词来查找记录，所以也就需要按关键词来建立索引，这个索引我们就称之为：倒排索引（也可称反向索引）
倒排索引所保存的信息一般如下：假设有100篇文档，文档编号从1到100，得到下面的结构图

• 词典：对某种语言分词处理后，得到的一系列字符串。每个字符串都指向包含此字符串的文档(Document)链表，此文档链表又称为倒排表(Posting List)。
• 倒排表：倒排表主要优点是，在处理复杂的多关键词查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样把对记录的查询转换为地址集合的运算，从而提高查询速度！

创建索引

• 准备数据：从数据库、Word文档、HTML网页文件等数据源抓取数据
• 分词：将准备好的数据传给分词组件（Tokenizer）

1）将文档切分为一个一个单独的词
2）去除标点符号
3）去除停词（Stop Word）
• 语言处理：将分词后得到的词（Token）传给语言处理组件（Linguistic Processor），对于英文一般做如下处理

1）将单词转为小写（Lowercase）
2）将单词缩减为词根形式（Stemming）
3）将单词转变为词根形式（Lemmatization）
• 建立词典与倒排表（倒排索引）：将语言处理处理后得到的词（Term）传给索引组件（Indexer），它主要做以下事情

1）将得到的词建立词典
2）对词典按字母顺序排序
3）合并相同的词成为倒排表

搜索索引

• 输入查询语句

就像SQL语句一样，全文搜索系统的查询语句也有语法，最基本的如：and,or,not等
举例，输入的查询语句为：lucene AND solr NOT hadoop
• 对查询语句进行词法分析、语言处理、语法分析

分析查询语句中的单词、关键字，对语句中的单词进行语言处理（等同创建索引中的语言处理），然后按语法规则生成语法树。

• 搜索索引，得到符合语法树的文档结果

过程大概如下
1）首先，在倒排索引中，分别找出包含单词lucene, solr, hadoop的文档链表
2）其次，对包含lucene, solr的文档链表进行合并操作，得到即包含lucene又包含solr的文档链表
3）然后，对得到的文档链表与hadoop的文档链表比较排除，得到即包含lucene又包含solr的但不包含hadoop的文档链表
4）最后，得到的文档链表就是我们要找的结果集
• 根据文档与查询语句的相关性，对结果集进行排序

对结果集中的每个文档按相关性（relevance）进行打分（scoring），分数最高的排在最前面。而推算文档的相关性一般分为两个过程
1）找出词（Term）在文档中重要性的过程，也称计算权重（Term weight）的过程
影响一个词（Term）在一篇文档中的重要性主要有两个因素
Term Frequency (tf)：即此Term在此文档中出现了多少次，tf越大说明越重要
Document Frequency (df)：即有多少文档包含次Term，df越大说明这个词越普通，也就越不重要
2）判断Term之间的关系从而得到文档相关性的过程，也即向量空间模型的算法（Vector Space Mode）
这个算法研究中
• 返回搜索结果

未完

评论

1 楼 ilovejavaforever 2010-08-15  

遗漏了很多关键内容.....