当前位置: Coin163 >>

全文搜索基本原理介绍

2013-09-17 | 所属分类:全文搜索 lucence
现实中有两种数据
  结构化数据:指具有固定格式的数据
  非结构化数据:指无固定格式的数据,对这种类型的数据又可称为全文数据
因此搜索也有两种
  对结构化数据的搜索: 如数据库的查询等
  对非结构化数据的搜索: 如Windows的文件搜索,Google的内容搜索等 .这种类型的搜索又称全文数据搜索.
全文数据搜索的方法:
  顺序扫描法:要找内容包含某一个字符串的文件,就是一个文档一个文档的看,对于每一个文档,从头看到尾,如果此文档包含此字符串,则此文档为我们要找的文件,接着看下一个文件,直到扫描完所有的文件.Windows的文件搜索就是这种方式,当文件多时,是相当的慢.
       全文搜索:  由于对结构化数据的搜索可以按照一定算法进行搜索相对而言还是很快的,因此将非结构化数据中的一部分信息提取出来,重新组织,使其变得有一定结构,然后对此有一定结构的数据进行搜索.这也就成了我们所说的全文搜索技术的基本思想.
 全文搜索包括两个主要的部分:
  索引创建:既将非结构化数据中的一部分信息提取出来,重新组织结构.
        搜索索引:在新的数据结构下根据用户的条件进行搜索
一、索引创建过程
1. 准备需要搜索的文档
  Document1: Students should be allowed to go out with their friends, but not allowed to drink beer
      Document2: My friend Jerry went to school to see his students but found them drunk which is not allowed.
2. 对文档进行分词处理
  这个过程称作Tokenize,基本包括三个处理:
  • 将文档分成一个一个单独的单词
  • 去除标点符号。
  •  去除停词(Stop word).在英文语法中如"the" " a " " this" 等,这些一般都不是搜索的关键词.
  经过分词(Tokenizer)后得到的结果称为词元(Token).如上面的两个文档,处理完后得到如下词元:
    “Students”,“allowed”,“go”,“their”,“friends”,“allowed”,“drink”,“beer”,“My”,“friend”,“Jerry”,“went”,“school”,“see”,“his”,“students”,“found”,“them”,“drunk”,“allowed”
3.对词元进行语意处理
  对于英语的处理一般有如下几点
  Lowercase:变为小写;
       Stemming: 将单词缩为词根形式,如:“cars”到“car”等;
       Lemmatization:将单词转变为词根形式,如“drove”到“drive”等;
经过处理后的结果为词Term,上述词的处理结果:
 “student”,“allow”,“go”,“their”,“friend”,“allow”,“drink”,“beer”,“my”,“friend”,“jerry”,“go”,“school”,“see”,“his”,“student”,“find”,“them”,“drink”,“allow”。     
 
 
 
4.将得到的词进行索引
  • 建立字典
Term
Document ID
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
 
 
 
 
 
 
 
 
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  • 对字典按字母排序
Term
Document ID
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
  • 合并相同的词进行文档倒排序列表

Document Frequency 即文档频次,表示总共有多少文件包含此词(Term)。
Frequency 即词频率,表示此文件中包含了几个此词(Term)。
对词(Term) “allow”来讲,总共有两篇文档包含此词(Term),从而词(Term)后面的文档链表总共有两项,第一项表示包含“allow”的第一篇文档,即 1号文档,此文档中,“allow”出现了2次,第二项表示包含“allow”的第二个文档,是2号文档,此文档中,“allow”出现了1次.
 
二、搜索索引
1.输入查询语句
  查询语句具有一定的语法,例如:Drunk  OR  beer,表示用户想搜索包含Drunk 或 beer 的文档.
2.对查询语句进行词法分析、语法分析及语言处理
  词法分析用来识别单词和关键字
  对上述查询语句分析后,得到词 Drunk ,beer ,关键字:OR .对结果生成一棵逻辑判断的语法树.
  接着进行语言处理,这个过程跟建立索引时的语言处理一样.如:Drunk会转化成drink
3.  搜索索引,得到合乎语法树的结果文档.
   在反向搜索列表中查找drink或beer的文档,等到文档Document1 和Document2.
4.  根据得到的文档和查询语句的相关性,对结果进行排序
   这个过程是一个复杂的算法,不同的语系以及社会文化背景都会影响到算法的设计.
上一篇:
下一篇:

相关文章推荐

最新文章

关于Coin163网站地图

Copyright 2012-2013 Coin163.com ( Coin163 ) All Rights Reserved