文本信息检索技术与方法分析

1、第第 3 章章 文本信息检索文本信息检索技术与方法技术与方法文本是一种极其重要的信息和知识交流媒介。从远古时期的象形文字开始，人类社会已发展和创造了各种形式的文字和语言系统。自计算机诞生以来，各种文本数据一直是其处理和加工的主要对象，信息检索领域也不例外。3.1 文本信息概述文本信息概述l3.1.1 文本信息的基本知识l一、文本的概念l文本文本是基于一定的语言符号系统而形成的一个有限符号序列l符号符号是不能再分割的记号单位，如数字符号、字母符号、标点符号等3.1 文本信息概述文本信息概述l符号表符号表是有限个任意符号组成的非空集合，符号表中的元素即是“符号”，如由所有汉字组成的集合，由所有英语

2、词汇组成的集合等l符号串符号串是指由符号表中的符号组成的长度有限的序列。例如，如果符号表是汉语中所有词汇的集合，那么，任何汉语句子和短语都是该符号表上的符号串l这样我们就可以将文本文本定义为某符号表上的符号串的集合二、文本的信息量二、文本的信息量l假设在某一给定的文本片段中共出现有个符号，而在该文本段中每个符号的出现概率为pi(i=1,2, ),则该段文本的信息熵定义为： 熵的单位是比特l例：在某一文本片段中，取=16，每个符号以等概率方式出现，则该段文本的信息熵为4比特21 logiiiEpp 三、文本文档的格式与编码三、文本文档的格式与编码l当把文本信息输入、存放在计算机存储器中，通常需要

3、结合具体应用任务来指定一定的文档格式。l常用的文档格式：TXT、RTF、DOC、PDF、MIME、ARJ、ZIP3.1.2、自然语言文本中词汇的频率、自然语言文本中词汇的频率与数量分布规律与数量分布规律l在基于某种自然语言系统的文本文档集合中，词汇的出现频率和数量是有一定规律的。l一、词汇的频率与齐普夫分布模型 词的出现频率和按照频率高低降序排列后产生的词的序号是一个频率词典的两个最基本的数量指标。齐普夫分布模型齐普夫分布模型l齐普夫定律即在一个给定的文本文档集合中，如果将所有单词按照其出现频率递减排列，并用自然数依次给单词赋予等级序号1、2、3、，那么，单词频率与其等级序号的乘积为一个常数，

4、其数学表达式为 fr = C 或者 f = C / r 上式中f为某个单词的出现频率，r为该单词的等级序号，C为常数。齐普夫分布模型齐普夫分布模型词频的齐普夫分布模型齐普夫分布模型齐普夫分布模型l齐普夫定律的更普遍形式 或者上式中的参数 因学科样本等不同而有所变化，其取值范围约在1.5-2之间l对于文本信息检索来说，齐普夫定律在词表编制、自动标引、倒排文档组织等方面有比较重要的理论指导价值frC/fC r二、词汇的数量与二、词汇的数量与Heaps分布模型分布模型l在文本文档集合中，不仅词汇的频率分布具有显著的规律性，词汇的数量及其增长变化也表现出一定的规律性。l为了预测自然语言文本中词汇的增长

5、变化，研究人员提出了Heaps模型l该模型认为，在一个长度为n个词的文本片段中，它的词汇量V与n之间具有以下关系lK通常取10-100， 则是小于1的正实数VK n二、词汇的数量与二、词汇的数量与Heaps分布模型分布模型词汇量的Heaps分布模型3.2、布尔检索、布尔检索l布尔检索主要以索引文档为基础，通过布尔逻辑运算符对检索词进行组配，形成检索提问式，进而以此提问式为匹配依据完成对索引文档的匹配处理并获取查询结果3.2.1 布尔逻辑运算符号及其使用布尔逻辑运算符号及其使用l一、布尔逻辑运算符及其运算含义 布尔逻辑运算符是构造用户检索提问式的一组主要连接组配符号，主要包括：逻辑或（OR）逻辑

6、与（AND）逻辑非（NOT）逻辑或（逻辑或（OROR）l也称为“析取联接词”，形式上还可以写作“+”l检索词A和检索词B若用“OR”组配，则检索提问式可表示为l A OR B 或者 A + B逻辑或（逻辑或（OROR） 逻辑或（XOR）运算的文氏图表示逻辑或（逻辑或（OROR）l例如，研究网络搜索引擎的用户，对有关Google、Excite、百度的文献信息都比较感兴趣，就可以使用“OR”构造如下的提问检索式： Google OR Excite OR 百度逻辑或（逻辑或（OROR）l对于检索提问式“A OR B”, 假设检索词A的所有命中文档有m篇，检索词B的所有命中文档有n篇，“A OR B”

7、的所有命中文档有s篇，则：当A与B不相关时，s = m + n；当A与B有一定相关性时，s m + n；当A与B密切相关时，s = Max(m,n)；综合以上三种情况，有 Max(m,n) s m + n逻辑与（逻辑与（ANDAND）l也称为“合成联接词”，形式上还可以写作“*”l检索词A和检索词B若用“AND”组配，则检索提问式可表示为l A AND B 或者 A * B逻辑与（逻辑与（ANDAND） 逻辑与（AND）运算的文氏图表示逻辑与（逻辑与（ANDAND）l例如，研究网络搜索引擎的用户，对同时出现Google、Excite、百度的文献信息比较感兴趣，就可以使用“AND”构造如下的提问

8、检索式： Google AND Excite AND 百度逻辑与（逻辑与（ANDAND）l对于检索提问式“A AND B”, 假设检索词A的所有命中文档有m篇，检索词B的所有命中文档有n篇，“A AND B”的所有命中文档有s篇，则：当A与B完全无关时，s = 0；当A与B有一定相关性时， 0 s m 或者 0 s n ；当A与B密切相关时，s = Min(m,n)；综合以上三种情况，有 0 s Min(m,n)逻辑非（逻辑非（NOTNOT）l也称为“否定联接词”，形式上还可以写作“-”l检索词A和检索词B若用“NOT”组配，则检索提问式可表示为l A NOT B 或者 A - B逻辑非（逻辑

9、非（NOTNOT） 逻辑非（NOT）运算的文氏图表示逻辑非（逻辑非（NOTNOT）l例如，查找云南大学的相关信息，但不想了解云大附中的信息，就可以使用“NOT”构造如下的提问检索式： 云南大学 NOT 云大附中逻辑非（逻辑非（NOTNOT）l对于检索提问式“A NOT B”, 假设检索词A的所有命中文档有m篇，检索词B的所有命中文档有n篇，“A NOT B”的所有命中文档有s篇，则：当A与B完全无关时，s = m；当A与B有一定相关性时，s n时，则 s = m n，当m n, 则 s = 0综合以上三种情况，有 0 s m布尔逻辑运算符的使用说明布尔逻辑运算符的使用说明l运算规则同级运算自左

10、向右进行布尔运算AND和NOT先执行，OR次之当检索提问式含有截词符、位置算符、限制符时，布尔运算最后执行先括号内，后括号外，具有多层括号时，按层次从内到外逐层进行3.2.2 3.2.2 布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理l在以布尔模型为概念基础的信息检索系统中，检索软件需要对用户输入的布尔逻辑提问式进行必要的加工和编辑，以满足后续的检索处理要求。l通常，我们在书写算术（逻辑）表达式时，总是把运算符放在两个运算项的中间，如“A加上B求和，再乘以C”可以写成(A + B) * C3.2.2 3.2.2 布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理表达式对应的二叉

11、树结构示意图3.2.2 3.2.2 布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理l一般（中缀）表示法 中序遍历二叉树: (A + B) * Cl正波兰（前缀）表示法 前序遍历二叉树: * + ABCl逆波兰（后缀）表示法 后序遍历二叉树: AB + C *3.2.2 3.2.2 布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理l例：lA + B * (C + D) 正波兰表示法：+ A * B + CD 逆波兰表示法：ABCD + * +l(A + B) * (C + D) 正波兰表示法：* + AB + CD 逆波兰表示法：AB + CD + * 3.2.2 3.2.2

12、布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理l准波兰变换法 检索提问式的准波兰法处理算法：创建检索提问式的二叉树表示比较二叉树中每一层次上的左、右子树是否对称。如不对称，把大的一枝保留或调到左边，小的一枝保留或调到右边，直到全部节点的左、右子树都这样处理完为止后序遍历该二叉树，节点的输出序列即为检索提问式的准波兰式3.2.2 3.2.2 布尔逻辑检索提问式的变布尔逻辑检索提问式的变换处理换处理l例：lA + B * (C + D)逆波兰表示法：ABCD + * +准波兰表示法：CD+B*A+3.3 3.3 截词检索截词检索l截词检索是基于布尔检索框架的一种常用联机检索技术，尤其是西

13、方语言文本检索中，更是广泛使用。西方语言的一个共同特点是：构词灵活，在词干上加上不同性质的前缀（或后缀），就可以派生出很多新的词汇。3.3 3.3 截词检索截词检索l截词截词，是指检索者将检索词汇在他认为合适的地方截断l截词检索截词检索，是指使用被截断的词汇进行检索匹配，并认为凡满足这个词局部中的所有字符（串）要求的记录，都为命中结果l按照截断的位置，分为：后截断、前截断、中截断l按照截断的字符数量，分为：有限截断、无限截断一、后截词检索一、后截词检索l将截词符号置放在一个字符串右方，以表示其右边的有限或无限个字符不影响该字符串的检索匹配。l例：检索提问式“brows*”是一个无限后截词的例子

14、，可能检索出来的词汇有 browse browser browsable browsers browsed browsing 一、后截词检索一、后截词检索l不难看出，后截词检索具有隐含的“逻辑或”（OR）运算特性，上例中的检索提问式等价于下面的检索提问式：browse OR browser OR browsers OR browsing 一、后截词检索一、后截词检索l例：检索提问式“acid?”是一个有限后截词的例子，可能检索出来的词汇有 acid acidic acids l但不能检出下列词汇 acidicity acidify acidity 一、后截词检索一、后截词检索l后截词检索主要应

15、用与以下四种情形：词的单复数，如：book?, potato?年代，如：199？， 19？；作者，如 Lancaster *同根词，如：biolog*, physic*l注意：使用后截词检索有可能检出无关词汇，Google就不提供截词检索功能二、前截词检索二、前截词检索l将截词符号置放在一个字符串左方，以表示其左的有限或无限个字符不影响该字符串的检索匹配。l例：检索提问式“*magnetic”是一个无限前截词的例子，可能检索出来的词汇有 magnetic electromagnetic(电磁的) paramagnetic(顺磁的) thermomagnetic（热磁的） 二、前截词检索二、前截

16、词检索l前截词检索和后截词检索一样，也存在隐含的“逻辑或”（OR）运算特性l在有些情况下，前后截词检索可以结合起来使用l由于技术实现上比较复杂，目前检索系统中前截词检索还比较少见三、中截词检索三、中截词检索l这种截词方式是把截词符号放置在一个检索词的中间，而不是左右两侧。中截词检索一般只允许检索词的有限截断l中截词检索主要应用于以下两种情形：英语单词的英美拼写方式不同： defence、defense defen?edefen?e；sulphur、sulfur sul?ursul?ur某些词在元音位置上出现单复数的不同 woman、women wom?nwom?n3.4 3.4 限制检索限制检

17、索l在文本检索系统中，为了提高或保证检索的准确率，常常提供一些缩小或约束检索结果的检索技术，称之为“限制检索”。限制检索一般仍需要建立在布尔检索的基础之上，因此可以把它看做是一种受限的布尔检索3.4 3.4 限制检索限制检索l限制检索的方式很多，其中最主要的限制技术是通过限制检索词在命中结果记录中的出现位置（主要指文本数据库记录的不同字段位置）来实现的，这种限制检索也因此被称为“字段检索”l具体指定检索字段的方式有两种：菜单选择方式检索命令方式3.4 3.4 限制检索限制检索l菜单选择方式3.4 3.4 限制检索限制检索l检索命令方式例: overload wn AB(seatbelt* OR

18、 (seat belt*) wn TI 用法:Term wn code3.4 3.4 限制检索限制检索l除字段检索外，对文本信息进行限制检索的另一种形式是“二次检索”，即提供用户在检索结果中进行再次检索，l位置检索位置检索是一类针对自然语言文本中检索词与检索词之间特定位置关系而进行的检索匹配技术。位置检索允许用户使用自然语言作为检索入口，并可深入到原文的章、节、段、句等文本范围内进行信息的查找和匹配l因此这种检索技术可以显著提高文本信息的检索精度，改善布尔检索等既有技术特定信息的筛选能力3.5 位置检索位置检索l目前，联机检索系统中提供的位置检索方法已经非常丰富多样。总结起来看，我们可以将这些

19、位置检索方法划分为以下不同类型:邻接检索同句检索同字段检索同记录检索一、一、邻接检索邻接检索l邻接检索是一种对检索词之间相互位置关系要求最为严格的位置检索方式。一般地，邻接检索需要通过专门的位置运算符来规定检索提问式中的检索词在检索结果中出现是应满足的相对位置要求。l在邻接检索检索中，经常使用的位置运算符有(W)与(nW)(N)与(nN)一、一、邻接检索邻接检索l(1) (W)与(nW)l(W)算符的运算含义是：在检索提问式中，它所连接的两个检索词必须在文本中按照前后顺序紧挨着出现，两个检索词之间除可以有一个空格、一个标点符号和一个连字符外，不得夹有其他任何其他单词、字母或汉字。l(nW)算符

20、是从(W)算符引申出来的，允许在连接的两个检索词之间最多夹入n个其他单词一、一、邻接检索邻接检索l例1：对于检索提问式“digital(W)library”来说，可以查找出在文献中出现“digital library”的相关资料l例2：对于检索提问式“large(W)scale(W) integrated(W)circuit”来说，则可以检索出含有“large scale integrated circuit”的资料l例3：对于检索提问式“云南(3W)大学”,则在检索结果中，将会出现包含“云南大学”、“云南师范大学”、“位于云南的一些大学”等内容的相关信息一、一、邻接检索邻接检索l(2) (N)与(nN)l(N)算符的运算含义是：在检索提问式中，它所连接的两个检索词必须在文本中紧密相连着出现，两个检索词之间除可以有一个空格、一个标点符号和一个连字符外，不得夹有其他任何其他单词、字母或汉字。l它与(W)的区别是，(N)算符两侧的检索词出现顺序可以颠倒l(nN)算符是从(N)算符引申出来的，允许在连接的两个检索词之间最多夹入n个其他单词一、一、邻接检索邻接检索l例4：对于检索提问式“money(N)supply”的检索结果中，将会包括含有“money supply”和“sup