第四讲文本信息检索研究TextProcessing.ppt

《第四讲文本信息检索研究TextProcessing.ppt》由会员分享，可在线阅读，更多相关《第四讲文本信息检索研究TextProcessing.ppt（93页珍藏版）》请在三一文库上搜索。

1、第四讲 文本信息检索研究 (Text Processing),陆铭 66134922 mingler.ccshu.org,2,Outline,经典文本检索方法 (1)菊池敏典算法 (2)福岛算法 (3)加权检索 文本预处理分词、词干 索引和排序 全文检索方法 国内文本和全文检索研究,3,1.1 菊池敏典算法信息检索系统的构成,信息采集子系统 广泛地、定期地采集各种信息源 标引子系统 人工或者自动标引 建库子系统 数据录入、错误检查与处理、数据格式转换、生成各种文档。仅提供定题(SDI)服务，则建立能支持顺序检索的顺排文档。若需支持回溯检索，则建立各种倒排档 词表管理子系统 管理维护系统中已有

2、的词表，使它与标引、建库等子系统相连接，支持用户查询操作 用户接口子系统 由用户模型、信息显示、命令语言和反馈机制 提问处理子系统 接收提问 提问校验 提问加工，指对原提问式进行解释性或编译性的加工，生成便于机器处理的目标提问式。加工方式常有顺序检索中的表展开法、倒排检索分别以菊池敏典法和福岛方式 检索,4,菊池敏典算法,展开表概念 1968年，日本科技情报中心的菊池敏典研究出脱机批处理检索信息的表展开法(菊池敏典算法) 属于传统的布尔逻辑检索模型，基于文本信息检索，主要适用于二次文献信息的检索。 主要思想是将代表用户的逻辑提问式转换成表的形式。该表规定了表的内容走向和是否命中的判断，检索时根

3、据表的走向及其相关信息来判断每条记录是否命中。,5,菊池敏典算法,表展开法的概念 用表来表达逻辑提问式，要求： 能够充分体现提问式中复杂的逻辑运算关系 能够准确反映每个检索词的检索匹配要求 能够准确给出记录最终的命中与否,6,菊池敏典算法,最简单的例子 以展开表法处理提问查询 A*B 表中，“命中”表示被查比的文献满足查询要求的出口，“落选”表示反之,7,菊池敏典算法,当一篇文献满足条件A时，还应再去查比提问条件B是否也能被满足。如果能，则该文献应被该提问选中，否则，该文献没有被该提问所选中，即落选。 当一篇文献不能满足检索条件A时，则不必再去查比检索条件B是否能被满足，即可判定该文献也为落选

4、。,8,菊池敏典算法,(A+B)*(C+D)的表展开形式,9,菊池敏典算法,过程,10,菊池敏典算法展开表生成,前处理 判断提问式中的字符，从上而下填写表格 若是检索词 则将其存入展开表内的检索词栏，并记下在表中的地址 若是运算符 “+”：前一词满足，指向“*”；不满足，指向后一词 “*”：前一词满足，指向后一词 若是括号 “（”：逢“（”在其后的检索词所在行的“级位”栏值加1 “）” ：逢“）”在其后的检索词所在行的“级位”栏值减1 若遇结束，则最后一个检索词所在行的“条件满足指向”栏放入“命中”，“条件不满足”放入“落选”,11,菊池敏典算法,后处理 依据表中“级位”值，从下而上填写 若当

5、前行级位值大于上一行的级位值，表示上一行的检索词后有右括号 若所在行的“条件不满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“*”运算，应把上一行“落选”内容复制到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“+”运算，应把上一行“命中”内容复制到当前行的不满足栏 若当前行的级位值等于上一行的级位值，则作以下处理： 若所在行的“条件不满足指向”栏为“空”，复制上一行“落选”内容到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制第一个右括号或提问式结束号前检索词所在行的满足栏内容到当前行的满足栏 若当前行的级位值小于上一行的级位

6、值，表示当前行的检索词前有左括号： 若所在行的“条件不满足指向”栏为“空”，复制表中已处理过的第一个与当前行级位值相等或小的不满足栏到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制当前行紧后复合检索项中最后一个检索词所在词所在行的满足栏内容到当前行的满足栏,12,菊池敏典算法展开表生成示例,A*(B+C)+(D*(E+F+G)的表展开形式示例,13,菊池敏典算法展开表法的检索,生成的展开表为若干逻辑提问式的集合，形成展开表提问档 检索时，提问展开表调入内存 查比时，每从数据库中读取一条记录，生成一个由可检索项组成的检索标识表，每一检索项查对展开表，并对命中的检索词做上标记 所有检

7、索项查询完毕，分析提问是否命中，命中者在相应的提问号下记下记录号 再取下一记录比对,14,菊池敏典算法优点,以提问中的提问条件项为检索查比的主动项 由于每个独立的提问所涉及的提问条件项的属性范围都不太多，因此，检索时，在文献巾查找的范围只需局限于单个提问所涉及的那一小部分(如关键词，标题等等，具体的提问条件项只在其本身属性范围内查找)。 菊池敏典算法用便于查找的提问展开表代替了原来的提问逻辑式 电脑可以顺着提问的思路查阅有关文献。一旦提问要求得到判定性的答案后，则可立即停止关于其他提问项的查比，而不一定要求将提问中所有提问条件项都一一查比。 菊池敏典算法的实质是: 凡是可不查阅的文献属性一定不

8、查， 凡是可不再查比的提问条件项一定不再查， 节约了机器的查比时间，使菊池敏典算法在早期开发情报检索自动化系统得到相当的重视及广泛的应用,15,福岛算法倒排文档的建立,倒排文档相对顺排文档而言，是将顺排文档中的可检索字段取出，按照一定的规则排序，归并相同词汇，并把在顺排文档中的记录号集合赋予其后，形成的文档，可看成为辅助文档。 倒排文档将两个检索词的逻辑运算转换成了两个检索词之间的记录号集合的运算。目前最常见的倒排文档检索为逆波兰展开法。 倒排文档的组成元素主要包括 关键字：作者，主题词，分类号 目长： 含有该关键字记录的条数 记录号集合：所有与该关键字有关的记录号,16,福岛算法,1929年

9、波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式” 日本的福岛首先将逆波兰表达式应用于情报检索，故又称“福岛方法” 逻辑提问式 A*(B+C)+D 逆波兰表达式 ABC+*D+ 逻辑提问式中运算符优先次序（）， -， *， + 逆波兰表达式中的次序（），+，*，-,17,福岛算法逆波兰表达式,18,福岛算法逆波兰表达式,19,福岛算法简单理解一下堆栈,可以把堆栈理解为一个只能容纳一个人宽的死胡同，ABCD四人进去，先进去的只有等后进去的人出来才能出来，进去越早出来越晚。,所以“先进后出”就是这种结构的特点。,20,福岛算法堆栈中的术语,栈底：就是开始放入数据的

10、单元 。 压栈：就是把一个人弄进死胡同里。 弹出（POP）：就是死胡同里的最后一个人出来了,21,福岛算法逆波兰表达式,例: 当遇到这样的计算式时,2,4,-,4,2,*,-3,-,+,-2,8,11,9,22,福岛算法逆波兰表达式,s,2,4,-2,4,-2,9,8,2,8,-3,11,11,9,23,福岛算法倒排文档的建立,24,福岛算法,作者索引,25,福岛算法作者索引,26,福岛算法,选择需要做索引的字段属性(如作者、关键词等)，抽出其中的内容，并在其后附上记录号 对抽出的内容进行排序，使之便于归并相同内容 对相同内容进行归并，把合并后的内容放入倒排文档的主键字段(如标引词、作者等)，

11、统计每一数据的频次为目长，把每一内容后的记录号顺序放在记录号集合字段 为转换处理开辟三个存储： 算子区：用于存放转换过程中的运算符 检索表存储区：用于存放检索词 逆波兰输出区：用于存放逻辑提问式的逆波兰表达式,27,福岛算法,遇运算符 若当前运算符的优先级高于前一算符，将该算符送算子栈 若当前运算符的优先级低于或等于前一算符，将顶部算符送逆波兰输出区，当前算符再与栈内顶部算符比较，优先级别低者送逆波兰输出区，否则送算子栈 遇左括号 表示其后存在一个复合检索项，暂不组成运算，而将左括号无条件放入算子栈 遇右括号 表示与其对应的左括号之间的所有算符都可以组成运算，栈内括号间的所有算符无条件出栈，并

12、送逆波兰输出区，同时放弃这对括号 遇运算项 将运算项(检索词)存入检索词表，并将其在检索词表的位置送逆波兰输出区 遇结束号 算子栈内的算子依次出栈送逆波兰输出区,28,福岛算法,逆波兰法处理示意图,检索词表,逻辑提问式 （A+B）*（C+EF）,04 03 02 01,词表地址,算子,区分运算项 还是运算符,逆波兰输出区,29,福岛算法检索指令表的生成,逐行扫描逆波兰输出表 ，实现从逆波兰表转换为检索指令表 若为检索词 若为运算符 若为结束行 转储操作结束,30,福岛算法检索实施,按照检索指令表的顺序，依赖检索词表和检索指令表，进行操作： 若操作码为“1”，进行查找和输入操作 若操作码为“2”

13、，转储操作 若操作码大于“2”，逻辑运算操作 若操作码为“0”，逻辑检索提问式检索结束,31,1.3 加权检索,根据用户的检索要求来确定检索词，并根据每个词在检索要求中的重要程度不同，分别给予一定的数值(权值)加以区别，同时利用给出的检索命中界限（ 阈值，threshold）限定检索结果的输出 加权检索是对每个检索词赋予一个数值，即“权”，权值越大，检索出的文献命中程度越高。 不同的检索系统对加权有不同的定义，也并非所有计算机检索系统都具备加权检索功能。 加权检索的侧重点不在于是否检索到某篇文献，而是对检索出的文献与需求的相关度作评判。,32,加权检索检索词赋权检索,检索要求： 为了改进企业管

14、理模式，接受新的管理理念，提高企业的竞争力，希望获取知识管理、竞争情报、企业文化父母的文献资料，用加权法列出的提问式如下： W知识管理（4）竞争情报（2）企业文化（1） 在所有存储的记录中查找满足上述检索词的文献，然后对检索词加权，文献按匹配的检索词权值之和从大到小排列显示,33,加权检索检索词赋权检索,加权检索结果实例,34,加权检索词频加权检索,根据检索词在记录中出现的频次来计算命中记录的权和，依据命中记录权和从大到小排列，最后由阈值控制输出命中结果 词频加权检索建立在全文数据库和文摘数据库基础之上，以免信息量过小，词频加权检索失去意义 简单词频加权检索：不论文章长短，以篇为单位计算权和

15、相对词频加权检索： 指定词在文中的频次 文内频率 该文献词汇总频次 指定词在文中的频次 文外频率 该词在整个数据库中总频次,35,加权检索加权标引检索,在文献标引时，根据每个标引词在文献中的重要程度不同为它们附上不同的权值，检索时通过对检索词标引权值相加来筛选命中记录 反映文献主要内容的标引词给予高权值，反映次要内容的标引词给予低权值。比较检索词赋权检索，结果更具科学性 根据词在文中不同位置、出现频率来综合，由计算机自动给予标引词加权,36,2 文本预处理,不论是文档还是查询，都要变成index term的某种形式(布尔表达式、向量、概率、统计语言模型参数) 抽取什么样东西的作为index t

16、erm? 将文档的字符串序列变成词序列 英文词法分析：书写时英文词之间通常通过空格或者标点进行区分，因此从英文字符串变成英文词是相对比较容易的。 中文词法分析：书写时通常没有空格，需要分词 中文分词就是将词语之间没有边界的中文句子分解为一个中文词语ID序列。分词是索引中速度最慢的环节,37,文本预处理,一般完成待索引文档的导入及规范化 从文档中抽取文字部分 完成编码转换 将字符串映射到整数流 其他操作,38,文本预处理分词,语素是最小的语音语义结合体，是最小的语言单位。 “字”：简单高效,国家标准GB2312-80 中定义的常用汉字为6763个.表示能力比较差，不能独立地完整地表达语义信息。

17、词是代表一定的意义，具有固定的语音形式，可以独立运用的最小的语言单位。 “词”：表示能力较强，但汉字的词的个数在10万个以上,面临复杂的分词问题,39,文本预处理,哈希函式从上世纪八十年代开始就有了相关研究 Knuth的研究结果表明，对最常用的31个英文单词建立哈希函式，获得1043种可能的搜索空间，对39个Pascal预定义标识符建立哈希函式，获得搜索空间为2039个节点,40,文本预处理分词主要方法,基于字符串匹配的分词方法 1）正向最大匹配法 2）逆向最大匹配法 3) 双向最大匹配法 4）最少切分 基于理解的分词方法 基于统计的分词方法,41,文本预处理正向最大匹配分词,就是从左至右尽可

18、能查找最长的词，直到当前字符与已经处理的字符串不构成词，输出已经识别的词，并从识别出来的词后面接着查找词。 分词速度比较快 但是分词错误率比较高,42,文本预处理快速检索词典的意义,分词是索引的瓶颈 分词的速度决定了索引的速度 分词就是循环的词典查找过程 词典的查找速度决定索引的速度,43,文本预处理汉字分词,N元切分法(N-gram) ：对一个字符串序列以N为一个切分单位进行切分。 如二元切分法： “ABCDEFG” “ABCDEFG” 交叉二元切分法(Overlapping Bigram)：“ABCDEFG” “ABBCCDDEEFFG” 简单快速，但会产生大量无意义的标引词，导致标引产生

19、的索引文件的空间，以及检索和进行标引的时间都大大增加。同时，因为它的切分单位并非语言学意义上的词语，所以也会导致检索的查准率下降。,44,文本预处理汉字分词,45,文本预处理汉字分词,切分歧义(Ambiguition)的消除 交集型歧义（交叉歧义）：“组合成” 我们/小组/合成/氢气了；组合/成/分子； “部分居民生活水平”：部分、分居、居民、民生、生活、活水 “学生会组织义演活动” : “学生/会/组织/义演/活动” or “学生会/组织/义演/活动”? 组合型歧义（覆盖歧义）： 他/从/马/上/下/来；我/马上/就/来/了 ； “老人家在天津”：老人、老人家 请把手拿开 这个门把手坏了 真

20、/伪歧义 “大学生活象白纸” 大学 生活 象白纸 大学生 活象 白纸,46,文本预处理中文词法分析,正向最大匹配(基于词典的方法),47,文本预处理中文词法分析,逆向最大匹配(基于词典的方法),48,文本预处理基于词典和规则的方法,最大匹配 正向最大匹配、反向最大匹配和双向最大匹配 实现简单，而且切分速度快。但无法发现覆盖歧义，对于某些复杂的交叉歧义也会遗漏。 全切分 利用词典匹配，获得一个句子所有可能的切分结果。 时空开销非常大。 基于理解的分词算法 模拟人的理解过程，在分词过程中加入句法和语义分析来处理歧义问题。 难以将各种语言信息组织成机器可直接读取的形式，还处在试验阶段,49,文本预处

21、理汉字分词,1.按字切分 优点： 采用单汉字切分的方法,字典体积最小,切分方法最为简单,最接近自然语言。单汉字存储是处理新词和任意汉字串的天然单元,具有其它方法无法比拟的优点 缺点 不能自动切分主题词,只能在检索时由用户通过对单字的多词匹配组合主题词。另外,随着数据库容量的增加,索引量急骤上升,耗费时空,且检索速度慢,效率低，其查准率和查全率的高低取决于后控制的智能水平。,50,文本预处理,2.按词切分 优点： 字典体积较小,比采用规范主题词更灵活,比单汉字更接近自然语言,便于与其他自然语言处理系统联系。 缺点 由于切词存在歧义的可能性,切词的组合有随意性,一个名词性概念有代用、相关、属分等关

22、系,动词性概念有方式、工具、强度、时间和原因等谓词框架,所以按词切分技术需要结合其他技术措施。 3.按主题词切分 优点 按主题词切分的方法,以综合、专业主题词典为切词依据,优点是切词正确率和专指性高,借助主题词典便于隐含标引。 缺点 系统空间开销大,而且不能切分主题词典没有收入的自由词和新词等,51,文本预处理,三种汉字分词方法的效率比较,52,文本预处理,按字检索对海量数据库不合适。数据库规模越大，查询性能会指数级下降，在5G以内的数据库上最好的性能为1-5秒（根据检索的复杂性不同），但当数据库规模达几十G以上，则实用性相当差。 信息检索用自动分词和自然语言理解用的自动分词在词的定义和收集范

23、围方面有很大不同，依据语义规则和上下文语境来提高分词准确率对信息检索的贡献不大，而且在某些情况下，产生负作用（如查询需求的自然语言描述缺少上下文）。 N-gram 方法产生的冗余很大，并且没有词典、知识的支持，查准率比较差。 字词混合的索引方式的词索引+BI-GRAM是较好的中文文本索引方式。 开发专用的歧义片断识别软件，并进而建立条歧义处理实例规则库是有效提高分词准确率的手段。,53,文本预处理规则和统计结合的方法,通常利用词典进行初切分，然后用其它的概率统计方法和简单规则消歧和进行未登录词识别。 比如： 利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路

24、径法。 最大匹配算法、state-of-the-art分类器和支持向量机的结合。 通过词典匹配找出所有交叉歧义，利用Bigram语言模型或其变形来消除歧义。 基于大规模语料库的统计方法 规则和统计结合的方法,54,文本预处理适用于大规模中文信息检索的分词算法,分词算法的时间性能要比较高 web搜索实时性要求很高，作为中文信息处理基础的分词应占用尽可能少的时间 分词正确率的提高并不一定带来检索性能的提高 分词到达一定精度之后，对中文信息检索的影响不再会很明显，虽然仍然还是有一些影响，但是这已经不是CIR的性能瓶颈。在时间和精度之间存在矛盾无法兼顾的情况下，应在二者之间找到一个合适的平衡点 切分的

25、颗粒度仍然可以依照长词优先准则 在查询扩展层面进行相关后续处理。在信息检索中，分词算法应集中精力考虑如何消除交叉歧义 未登录词识别的准确率要比查全率更加重要 要尽量保证未登录词识别时不进行错误结合，避免因此切分出错误的未登录词。如果将单字错误的结合成未登录词了，则有可能导致无法正确检索到相应的文档,55,文本预处理,待切分文本,初切分结果,核心词典,消除交叉歧义,未登录词识别,新词词典,切分结果,交叉歧义检测,图3 面向大规模中文信息检索的分词算法流程图,56,文本预处理,未登录词(Out of Vocabulary )识别 命名实体：数词、人名、地名、机构名、译名、时间、货币 缩略语和术语：

26、“超女”、“非典”、“去离子水” 新词：“酱紫”、“星盘” 先识别已知词还是先识别未登录词 先识别已知词：“内塔尼亚/胡说” 先识别未登录词：“胜利取决/于勇/气”,57,文本预处理英文分词,英文词法分析 数字的考虑： 某人想查询1978到1989年间车祸的死亡人数，可能查出来的结果有很多这两年本身的死亡人数，因此，上面的查询中，数字不是一个很好的index term。 但是，一些和字符组合的数字，如“510B.C.”，还有一些长数字，如身份证号、手机号，3.1415926，可能是非常好的index term。 最简单的做法就是所有数字都去掉，复杂的方法需要引入规则来分析，包括对时间的识别和归

27、一化，如：October 1978，Oct. 1978都要归一化成某个统一表示。,58,文本预处理英文词法分析,对连字号的考虑： 有些连字号中的词可以分开，如state-of-the-art变成state of the art 有些连字号中的词不宜分开，如B-49(一款分机型号) end-of-line hyphens are noise 对标点符号的考虑 Obvious: segment on puctuation, but “B.C.“, “B.S.“: without periods, these are just single letters URLs as index terms?

28、对大小写的考虑： 通常情况下，不考虑大小写，词法分析程序会将所有字母全部变成大写或者小写。但是，某些情况下，同一个单词的大小写含义不一样，如: China和china 进行词法分析时需要考虑引入一些规则方法,59,文本预处理禁用词消除,禁用词(stop words) 那些在文档中出现过于频繁(如超过80%以上的文档均出现该词)而对于检索没有区分意义的词，常见的禁用词包括冠词、介词、连词 优点： 禁用词消除可以减少term的个数，降低存储空间 缺点： 有时消除的禁用词对检索是有意义的，如：“的士”中的“的”，“to be or not to be”中的各个词，因此有些搜索引擎直接采用全文索引（f

29、ull index）,60,文本预处理,消除方法： 查表法 建立一个禁用词表，通过查表的方式去掉禁用词 基于词频的方法 统计每个词的词频，如果超过总文档数目的某个百分比(如80%)，则作为禁用词去掉,61,文本预处理 Stemming算法,Stemming的必要性 名词的单复数形式，动词的各种时态，形容词的各种级等本身含义非常类似。 当用户提交某个查询时，很有可能各种相关形式都是用户期望的结果 提高检索的召回率 用户输入查询关键词goose，一篇介绍goose的文档，虽然不包含单词goose，只包含单词geese，应该是相关的。,62,文本预处理常用stemming算法,Elementary

30、methods：大小写合并 Stemmer算法：单复数合并 Porter算法：使用规则去后缀 使用一系列后缀变换规则对单词进行变换 ed null ing null ational ate tional tion Lovinss method：特例表 The dictionary method：词典保存后缀 Corpus-Based Stemming：根据单词的共现度,63,文本预处理stemming算法的争议,很多论文指出，stemming对英文检索系统没有效果。 很多结果表明，stemming对荷兰语、阿拉伯语、斯拉夫语等有很大必要。 不同的论文用同样的stemming工具，针对同样的测试

31、集得出完全相反的结论。 一般认为：Stemming降低了查准率，提高了查全率。 查准率的降低不是stemming本身的问题，而是算法实现的效果不好。 Stemming本身很有必要，关键是要提高stmming的效果。,64,文本预处理词干还原,中文重叠词还原 汉语的某些形容词有重叠式用法。这些重叠式用法是词典里所没有的，所以必须通过还原算法从重叠式用法变回到基本形式上也可以看成是一种“词干”还原,65,文本预处理,中文重叠词还原 文本框: 双字形容词的重叠用法共有三种：ABAB式，AABB式、A里AB式。请看下表示例：,66,文本预处理,中文重叠词还原 单字形容词的重叠用法共有两种：ABB式和A

32、BCD式。请看示例：,67,文本预处理,进行词干还原： 好处：减少词典量； 坏处：按词形查不到，词根还原还可能出现错误 不进行词干还原： Stopped sto+ppe+d 好处：支持词形查询； 坏处：增加词典量,68,3 索引和排序,排序就是扫描每篇文档产生的（文档号，单词号，出现位置）三元组按照单词号重新排序，单词号相同的项再按照文档号排序，单词号和文档号都相同的再按照出现位置排序。 排序的过程正好是实现“倒排”的过程 排序以后的结果写入临时索引文件。,69,3 索引和排序,前向索引 直接对文本进行逐篇扫描费时费力，为解决这个问题，考虑将文本预先处理（由前向索引转换成倒排索引）后进行匹配，

33、就能较快地得到结果。 前向索引(Forward index) 将每篇文档表示成Doc ID及其文本内容组成的类向量模式。,70,索引和排序,前向索引实例,71,索引和排序,前向索引的特征 仍然是依次扫描每个文档，但是对于一个字符串的多次出现不需要一一扫描，而且对同一文档内的字符串查找可以采用二分查找的方式，加快匹配过程。也就是说通过预处理的方式加快对每篇文档的匹配速度。,72,索引和排序,倒排索引 使用前向索引，仍然需要逐篇扫描每个文档。如果文档数目较多，那么就非常费时费力。 倒排索引(inverted index) 能够直接从查询词定位到文档。,73,索引和排序,倒排索引实例,74,索引和排

34、序,对文档1分析产生的三元组如下： b d a b b c b a d c (文档号，单词号，位置） (1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10),75,索引和排序,对文档2分析产生的三元组如下： a b c d a c d b d a b (文档号，单词号，位置） (2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11),76,索引和排序,倒排索引的更新 情

35、况一：出现了新的词，则需要修改词典结构，在词典中增加词条。 情况二：出现了新的文档，则在相应的词条下增加posting list。 情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。 倒排索引对于单个查询词，搜索就是词典查找的过程，不需要扫描所有文档，只需要访问这个词对应的posting list，速度相当快。,77,4 全文检索方法位置级检索,位置检索的四种类型： 记录级 字段或段落级 子字段或自然句级 词位置级,78,全文检索方法,顺序相邻 (W) 顺序隔词 (nW) 位置相邻(N) 隔词相邻(nN),79,全文检索方法,子字段内“与”运算 (S) 字段内“

36、与”运算(F) 主题词字段内“与”运算(L),80,全文检索方法,相当于一般逻辑运算 多数中文检索系统采用记录级位置检索,81,全文检索方法,采用同义词典，提高查全率 关联含义相同的词汇，当用户使用某个词汇检索时，系统直接将同义词取出，构成“或”运算检索式，在全文中匹配查询 采用排除词词典，提高查准率 关联检索词(例如民法)与希望排除的词(例如人民法院、移民法等)，一种排除方法是系统直接将排除词取出，构成“非”运算检索式，在全文中匹配查询,82,全文检索方法,多级索引结构。采用B+树、INVERT FILE等多种基本索引及其改进模型，实现了一个多级索引结构，使得海量数据库上的查询速度达到亚秒级

37、。 基于成本优化的索引跳跃式扫描技术，比如用户的检索词为“中国足球”，检索词“中国”的命中篇数非常多，而“足球”相对较少，因此在检索逻辑运算时，可以利用索引中的信息，以足球为主运算对象，这样可以有效提高检索速度。 基于词频的BI-GRAM算法。 多库并行检索。 大内存技术和CACHE技术,83,全文检索方法,一般认为一个优秀的全文检索算法，一个百兆级的全文数据库，检索速度在一两秒内反应 提高检索速度的措施： 集合运算中，减少对比次数 分高频和低频词索引，一般只在高频词索引中检索,84,全文检索方法位置级检索,布尔查询的处理 And 关系： A and B，取出A、B的posting list进

38、行交叉合并。 Or 关系： A or B，取出A、B的posting list进行叠加。 Not 关系： A And not B，取出A、B的posting list进行减操作。 短语查询的处理 比如查AB，取出A、B的posting list，然后进行交叉合并，并且合并时要满足位置相邻的关系。,85,5 国内文本和全文信息检索研究概况关键词分析,86,5 国内文本和全文信息检索研究概况作者分析,87,5 国内文本和全文信息检索研究概况发展,全文检索系统的研究热点 自动标引 单汉字自动标引、词典切分标引、主题词标引 全文检索软件 EBSCO TRS,中信所QuickIMS,浙江天宇CGRS,8

39、8,5 国内文本和全文信息检索研究概况发展,汉字分词技术 信息处理用现代汉语分词词表的制定 汉语词自动切分算法,:最大匹配法!逆向最大匹配法,逐词遍历法、设立切分标志法、最佳匹配法、有穷多层次列举 消除切分歧义的方法：基于规则的方法: 基于统计的方法主要有:基于互信息和T-Test的方法、基于隐Markov模型的方法 .基于SVM和k-NN结合的汉语交集型歧义切分方法、基于EM的方法等。 未登录词的识别。利用词颁、上下文信息和未登录词候选词表 汉语自动分词应用研究。目前,汉语自动分词主要在信息检索、自动标引、自动文摘、机器翻译、语言文字研究、搜索引擎研究、自然语言理解和中文信息处理等方面的应用

40、取得了可喜的成绩。这一研究成 果将会被更广泛的应用到更多的研究领域,如词频统计、内容分析、概念分析、认知心理学和汉语语言学等方面。,89,5 国内文本和全文信息检索研究概况发展,优化面向用户的全文检索技术 全文数据采集的广泛化 CJFD:期刊、学位论文、会议、专利 数据加工的知识元化 从以篇为单位，深入到以知识元为单位 检索查询的自动分词化 应用bi-gram为主的分词技术，对查询进行自动分词 知识揭示的网络化 数据库内外知识的网络化链接：关键词、作者、引文等本库知识元链接，相同主题的本系统外库链接,90,5 国内文本和全文信息检索研究概况发展,存在问题 查准率问题 “长江” 长江大学 检索结

41、果过多问题 主题引擎网页命中结果过多 数据更新问题 数据滞后,91,5 国内文本和全文信息检索研究概况,文本检索存在的问题和发展方向 检索性能较低，查全率和查准率均不尽人意 目前进行的智能Agent在全文检索系统中的应用研究，其目的正是为了解决这个问题，尽管已经取得一些初步的成果，今后仍旧是需要研究的方向,92,本讲总结,经典文本检索方法 菊池敏典算法，福岛算法，加权检索的原理 文本预处理 汉字分词方法、词干、禁用词 索引和排序 前向索引和倒排索引 全文压缩方法和全文检索方法,93,课后思考题,简述菊池敏典算法，福岛算法的原理和基本功能 比较单汉字、双汉字分词的优缺点，何谓汉字分词粒度？ 试解释负数值的全文索引的膨胀系数,