开源搜索引擎Lucene-学习札记(1) 信息检索技术(Information retrieval)中的基本理论

开源搜索引擎Lucene---学习笔记(1) 信息检索技术(Information retrieval)中的基本理论
Lucene是一种非常优秀的开源搜索引擎。因为最近在看《Lucene 3.0 原理与代码分析完整版》，所以决定写下学习笔记。大家可以去看看其作者的博客： http://forfuture1978.javaeye.com



1、什么是全文检索(Full-text Search)：
     先建立索引，再对索引进行搜索的过程就叫全文检索(Full-text Search)。          ? 索引创建：将现实世界中所有的结构化和非结构化数据提取信息，创建索引的过程。          ? 搜索索引：就是得到用户的查询请求，搜索创建的索引，然后返回结果的过程。缺点：          建立索引的代价高，尤其是数据量小的时候。优点：          一劳永逸。
2、反向索引          一般的，非结构化的数据存储的信息是每个文件包含哪些字符，即通过文件获取字符。但是这种存储方式并不适合我们查询信息。我们需要通过一些关键字符，从而查询到特定文件。因此，我们需要建立索引保存字符到文件的映射，即反向索引。
3、如何建立索引
        1、将原文档传给分词组件(Tokenizer)。

分词组件(Tokenizer)会做以下几件事情(此过程称为Tokenize)：1. 将文档分成一个一个单独的单词。2. 去除标点符号。3. 去除停词(Stop word)。
经过分词组件处理得到的结果叫：词元(Token)。
2、将得到的词元(Token)传给语言处理组件(Linguistic Processor)。
对于英语，语言处理组件(Linguistic Processor)一般做以下几点：1. 变为小写(Lowercase)。2. 将单词缩减为词根形式，如“cars”到“car”等。这种操作称为：stemming。3. 将单词转变为词根形式，如“drove”到“drive”等。这种操作称为：lemmatization。
经过语言处理组件(linguistic processor)的结果称为 ：词(Term)。
3、将得到的词(Term)传给索引组件(Indexer)
索引组件(Indexer)主要做以下几件事情：1. 利用得到的词(Term)创建一个字典。2. 对字典按字母顺序进行排序。3. 合并相同的词(Term)成为文档倒排(Posting List)链表。

如，有以下实例：

文件一：Students should be allowed to go out with their friends, but not allowed to drink beer.文件二：My friend Jerry went to school to see his students but found them drunk which is not allowed.

步骤1:  经过分词组件得到以下词元(Token)：          “Students” ，“allowed ”，“ go”， “their” ，“friends ”，“ allowed”， “drink” ，“beer ”，“My” ，“friend ”,“Jerry”，“ went”， “school” ，“see ”，“ his”， “students” ，“found ”，“ them”， “drunk” ，“allowed ”。
步骤2：经过语言处理，得到的词Term)如下：“student”，“allow”，“go”，“their”，“friend”，“allow”，“drink”，“beer”，“my”，“friend”,“jerry”，“go”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。
步骤3.1：利用词（Term）创建一个字典：     

Term            DocumentID

student              1

allow                  1

go                       1

Their                  1

friend                 1

Allow                  1

Drink                  1

beer                    1

my                      2

friend                 2

jerry                   2

go                       2

school                2

see                     2

his                      2

student              2

find                    2

them                  2

drink                  2

allow                  2

步骤3.2：对字典按字母顺序进行排序。

Term                DocumentID     

allow                          1

allow                          1

allow                          2

beer                           1

drink                          1

drink                          2

find                            2

friend                         1

friend                         2

go                               1

go                               2

his                              2

jerry                           2

my                              2

school                        2

see                             2

student                      1

student                      2

their                           1

them                          2

步骤3.3：合并相同的词(Term)成为文档倒排(Posting List)链表。


４、如何对索引进行搜索？
          大家如果仔细想想，上诉的方法其实有很大的缺陷，如果我查找的范围不止上诉的两个，而是成千上万个，我们如何从这么大的数据中找到最接近我们查询所需要的呢？               这里就引用到了词的权重（Ｔｅｒｍ　Ｗｅｉｇｈｔ）的概念。          词的权重(Term weight)表示此词(Term)在此文档中的重要程度，越重要的词(Term)有越大的权重(Termweight)，因而在计算文档之间的相关性中将发挥更大的作用。
判断词(Term)之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法(Vector SpaceModel)ＶＳＭ。
４.1: 计算权重(Term weight)的过程。

影响一个词(Term)在一篇文档中的重要性主要有两个因素：? Term Frequency (tf)：即此Term在此文档中出现了多少次。tf 越大说明越重要。? Document Frequency (df)：即有多少文档包含次Term。df 越大说明越不重要。

       计算权重的公式如下（这是一种简单典型的实现，具体情况可调整，比如Ｌｕｃｅｎｅ就不是这么做的）：

４.２：判断Term之间的关系从而得到文档相关性的过程，也即向量空间模型的算法(VSM)。

我们把所有此文档中词(term)的权重(term weight) 看作一个向量。

Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}

同样我们把查询语句看作一个简单的文档，也用向量来表示。

Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}

我们把所有搜索出的文档向量及查询向量放到一个N维空间中，每个词(term)是一维。

我们认为两个向量之间的夹角越小，相关性越大。所以我们计算夹角的余弦值作为相关性的打分，夹角越小，余弦值越大，打分越高，相关性越大。
相关性打分公式如下：

于是文档二相关性最高，先返回，其次是文档一，最后是文档三。到此为止，我们可以找到我们最想要的文档了。

下面的这张图是建立索引及搜索的全过程：

---

２０１２年９月１日１５：０３：１７

查看更多 下一篇