第四讲 文本信息检索研究 (Text Processing)陆铭66134922richard.lushu.edu.cnmingler.ccshu.org2Outline 经典文本检索方法 (1)菊池敏典算法 (2)福岛算法 (3)加权检索 文本预处理分词、词干 索引和排序 全文检索方法 国内文本和全文检索研究31.1 菊池敏典算法信息检索系统的构成 信息采集子系统广泛地、定期地采集各种信息源 标引子系统 人工或者自动标引 建库子系统数据录入、错误检查与处理、数据格式转换、生成各种文档。仅提供定题(SDI)服务，则建立能支持顺序检索的顺排文档。若需支持回溯检索，则建立各种倒排档 词表管理子系统 管理维护系统中已有的词表，使它与标引、建库等子系统相连接，支持用户查询操作 用户接口子系统 由用户模型、信息显示、命令语言和反馈机制 提问处理子系统 接收提问 提问校验 提问加工，指对原提问式进行解释性或编译性的加工，生成便于机器处理的目标提问式。加工方式常有顺序检索中的表展开法、倒排检索分别以菊池敏典法和福岛方式 检索4菊池敏典算法展开表概念 1968年，日本科技情报中心的菊池敏典研究出脱机批处理检索信息的表展开法(菊池敏典算法) 属于传统的布尔逻辑检索模型，基于文本信息检索，主要适用于二次文献信息的检索。 主要思想是将代表用户的逻辑提问式转换成表的形式。该表规定了表的内容走向和是否命中的判断，检索时根据表的走向及其相关信息来判断每条记录是否命中。5菊池敏典算法表展开法的概念 用表来表达逻辑提问式，要求： 能够充分体现提问式中复杂的逻辑运算关系 能够准确反映每个检索词的检索匹配要求 能够准确给出记录最终的命中与否6菊池敏典算法最简单的例子以展开表法处理提问查询 A*B表中，“命中”表示被查比的文献满足查询要求的出口，“落选”表示反之行地址本行项满足后查比所在行的指针本行项未满足后查比所在行的指针提问条件项12落选A2命中落选B7菊池敏典算法 当一篇文献满足条件A时，还应再去查比提问条件B是否也能被满足。如果能，则该文献应被该提问选中，否则，该文献没有被该提问所选中，即落选。 当一篇文献不能满足检索条件A时，则不必再去查比检索条件B是否能被满足，即可判定该文献也为落选。8菊池敏典算法地址检索词条件满足指向条件不满足指向级位比较条件检索标识1A32省略2B3落选3C命中44D命中落选(A+B)*(C+D)的表展开形式9菊池敏典算法过程检索词检索运算符改变运算次序的括号供检索匹配的表格前处理10菊池敏典算法展开表生成 前处理 判断提问式中的字符，从上而下填写表格 若是检索词 则将其存入展开表内的检索词栏，并记下在表中的地址 若是运算符 “+”：前一词满足，指向“*”；不满足，指向后一词 “*”：前一词满足，指向后一词 若是括号 “（”：逢“（”在其后的检索词所在行的“级位”栏值加1 “）” ：逢“）”在其后的检索词所在行的“级位”栏值减1 若遇结束，则最后一个检索词所在行的“条件满足指向”栏放入“命中”，“条件不满足”放入“落选”11菊池敏典算法 后处理 依据表中“级位”值，从下而上填写 若当前行级位值大于上一行的级位值，表示上一行的检索词后有右括号 若所在行的“条件不满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“*”运算，应把上一行“落选”内容复制到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“+”运算，应把上一行“命中”内容复制到当前行的不满足栏 若当前行的级位值等于上一行的级位值，则作以下处理： 若所在行的“条件不满足指向”栏为“空”，复制上一行“落选”内容到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制第一个右括号或提问式结束号前检索词所在行的满足栏内容到当前行的满足栏 若当前行的级位值小于上一行的级位值，表示当前行的检索词前有左括号： 若所在行的“条件不满足指向”栏为“空”，复制表中已处理过的第一个与当前行级位值相等或小的不满足栏到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制当前行紧后复合检索项中最后一个检索词所在词所在行的满足栏内容到当前行的满足栏12菊池敏典算法展开表生成示例A*(B+C)+(D*(E+F+G)的表展开形式示例地址检索词条件满足指向条件不满足指向级位比较条件检索标识1A2）33）428） 01） 省略2B5）命中27）36）14）3C7）命中26）49）08）4D11） 512）落选25）110）5E14）命中24）615）213）6F17）718）落选23）216）7G19）命中21）落选22）020）13菊池敏典算法展开表法的检索 生成的展开表为若干逻辑提问式的集合，形成展开表提问档 检索时，提问展开表调入内存 查比时，每从数据库中读取一条记录，生成一个由可检索项组成的检索标识表，每一检索项查对展开表，并对命中的检索词做上标记 所有检索项查询完毕，分析提问是否命中，命中者在相应的提问号下记下记录号 再取下一记录比对14菊池敏典算法优点 以提问中的提问条件项为检索查比的主动项 由于每个独立的提问所涉及的提问条件项的属性范围都不太多，因此，检索时，在文献巾查找的范围只需局限于单个提问所涉及的那一小部分(如关键词，标题等等，具体的提问条件项只在其本身属性范围内查找)。 菊池敏典算法用便于查找的提问展开表代替了原来的提问逻辑式 电脑可以顺着提问的思路查阅有关文献。一旦提问要求得到判定性的答案后，则可立即停止关于其他提问项的查比，而不一定要求将提问中所有提问条件项都一一查比。菊池敏典算法的实质是: 凡是可不查阅的文献属性一定不查， 凡是可不再查比的提问条件项一定不再查， 节约了机器的查比时间，使菊池敏典算法在早期开发情报检索自动化系统得到相当的重视及广泛的应用15福岛算法倒排文档的建立 倒排文档相对顺排文档而言，是将顺排文档中的可检索字段取出，按照一定的规则排序，归并相同词汇，并把在顺排文档中的记录号集合赋予其后，形成的文档，可看成为辅助文档。 倒排文档将两个检索词的逻辑运算转换成了两个检索词之间的记录号集合的运算。目前最常见的倒排文档检索为逆波兰展开法。 倒排文档的组成元素主要包括关键字：作者，主题词，分类号目长： 含有该关键字记录的条数记录号集合：所有与该关键字有关的记录号16福岛算法1929年波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”日本的福岛首先将逆波兰表达式应用于情报检索，故又称“福岛方法”逻辑提问式 A*(B+C)+D逆波兰表达式 ABC+*D+逻辑提问式中运算符优先次序（）， -， *， + 逆波兰表达式中的次序（），+，*，-17福岛算法逆波兰表达式a + b运算符运算分量运算分量18福岛算法逆波兰表达式19福岛算法简单理解一下堆栈简单理解一下堆栈可以把堆栈理解为一个只能容纳一个人宽的可以把堆栈理解为一个只能容纳一个人宽的死胡同，死胡同，ABCDABCD四人进去，先进去的只有等后四人进去，先进去的只有等后进去的人出来才能出来，进去越早出来越晚。进去的人出来才能出来，进去越早出来越晚。所以所以“先进后出先进后出”就是这种结构的特点。就是这种结构的特点。20福岛算法堆栈中的术语堆栈中的术语栈底：就是开始放入数据的单元 。压栈：就是把一个人弄进死胡同里。弹出（POP）：就是死胡同里的最后一个人出来了21福岛算法逆波兰表达式例例: :当遇到这样的计算式时当遇到这样的计算式时 24-42*-3-+24-242*8 8-3-11-211+922福岛算法逆波兰表达式s s24-42*-3-+P24-24P24-29P8242*8P-38-3-1111P-211+9A0A1A223福岛算法倒排文档的建立记录号篇名作者标引词1知识管理与企业管理信息系统建设A知识管理，管理信息系统，企业信息化2论知识链与知识管理B知识管理，知识链，学习型组织，知识创新3刍议知识故那里及其体系框架C知识管理，知识创新，知识共享4知识管理的知识基础A知识管理，学习型组织5论技术创新的知识空间C技术创新，知识空间，知识创新6建立企业竞争性的信息结构A企业信息化，信息结构，竞争情报7知识管理在企业竞争情报研究中的应用B知识管理，竞争情报，知识创新8管理信息系统中文化行为研究B管理信息系统，企业文化9企业竞争情报管理系统的构建研究C管理信息系统，竞争情报10企业知识管理主体研究C知识管理，企业文化，管理创新24福岛算法作者索引作者目长记录号集合A31；4；6B32；7；8C43；5；9;1025福岛算法作者索引标引词目长记录号集合管理创新110管理信息系统31；8；9技术创新15竞争情报36；7；9企业文化28；10企业信息化21；6信息结构16学习型组织22；4；知识创新42；3；5；7；知识共享13知识管理61；2；3；4；7；10知识空间15知识链1226福岛算法选择需要做索引的字段属性(如作者、关键词等)，抽出其中的内容，并在其后附上记录号对抽出的内容进行排序，使之便于归并相同内容对相同内容进行归并，把合并后的内容放入倒排文档的主键字段(如标引词、作者等)，统计每一数据的频次为目长，把每一内容后的记录号顺序放在记录号集合字段为转换处理开辟三个存储： 算子区：用于存放转换过程中的运算符 检索表存储区：用于存放检索词 逆波兰输出区：用于存放逻辑提问式的逆波兰表达式27福岛算法遇运算符 若当前运算符的优先级高于前一算符，将该算符送算子栈 若当前运算符的优先级低于或等于前一算符，将顶部算符送逆波兰输出区，当前算符再与栈内顶部算符比较，优先级别低者送逆波兰输出区，否则送算子栈遇左括号 表示其后存在一个复合检索项，暂不组成运算，而将左括号无条件放入算子栈遇右括号 表示与其对应的左括号之间的所有算符都可以组成运算，栈内括号间的所有算符无条件出栈，并送逆波兰输出区，同时放弃这对括号遇运算项 将运算项(检索词)存入检索词表，并将其在检索词表的位置送逆波兰输出区遇结束号 算子栈内的算子依次出栈送逆波兰输出区28福岛算法地址检索词01A02B03C04EF特征内容0010021+0030041+1*0逆波兰法处理示意图（+检索词表逻辑提问式（A+B）*（C+EF）04030201词表地址算子区分运算项还是运算符逆波兰输出区29福岛算法检索指令表的生成逐行扫描逆波兰输出表 ，实现从逆波兰表转换为检索指令表若为检索词若为运算符若为结束行转储操作结束操作码第一操作数第二操作数第三操作数1032操作码第一操作数第二操作数第三操作数4341操作码第一操作数第二操作数第三操作数247操作码第一操作数第二操作数第三操作数0 30福岛算法检索实施按照检索指令表的顺序，依赖检索词表和检索指令表，进行操作：若操作码为“1”，进行查找和输入操作若操作码为“2”，转储操作若操作码大于“2”，逻辑运算操作若操作码为“0”，逻辑检索提问式检索结束311.3 加权检索根据用户的检索要求来确定检索词，并根据每个词在检索要求中的重要程度不同，分别给予一定的数值(权值)加以区别，同时利用给出的检索命中界限（ 阈值，threshold）限定检索结果的输出加权检索是对每个检索词赋予一个数值，即“权”，权值越大，检索出的文献命中程度越高。不同的检索系统对加权有不同的定义，也并非所有计算机检索系统都具备加权检索功能。加权检索的侧重点不在于是否检索到某篇文献，而是对检索出的文献与需求的相关度作评判。32加权检索检索词赋权检索检索要求： 为了改进企业管理模式，接受新的管理理念，提高企业的竞争力，希望获取知识管理、竞争情报、企业文化父母的文献资料，用加权法列出的提问式如下：W知识管理（4）竞争情报（2）企业文化（1）在所有存储的记录中查找满足上述检索词的文献，然后对检索词加权，文献按匹配的检索词权值之和从大到小排列显示33加权检索检索词赋权检索加权检索结果实例组合号包含的提问词权和知识管理竞争情报企业文化142172426345444521362271134加权检索词频加权检索根据检索词在记录中出现的频次来计算命中记录的权和，依据命中记录权和从大到小排列，最后由阈值控制输出命中结果词频加权检索建立在全文数据库和文摘数据库基础之上，以免信息量过小，词频加权检索失去意义简单词频加权检索：不论文章长短，以篇为单位计算权和相对词频加权检索： 指定词在文中的频次 文内频率 该文献词汇总频次 指定词在文中的频次文外频率 该词在整个数据库中总频次35加权检索加权标引检索在文献标引时，根据每个标引词在文献中的重要程度不同为它们附上不同的权值，检索时通过对检索词标引权值相加来筛选命中记录反映文献主要内容的标引词给予高权值，反映次要内容的标引词给予低权值。比较检索词赋权检索，结果更具科学性根据词在文中不同位置、出现频率来综合，由计算机自动给予标引词加权362 文本预处理不论是文档还是查询，都要变成index term的某种形式(布尔表达式、向量、概率、统计语言模型参数)抽取什么样东西的作为index term? 将文档的字符串序列变成词序列 英文词法分析：书写时英文词之间通常通过空格或者标点进行区分，因此从英文字符串变成英文词是相对比较容易的。 中文词法分析：书写时通常没有空格，需要分词中文分词就是将词语之间没有边界的中文句子分解为一个中文词语ID序列。分词是索引中速度最慢的环节37文本预处理一般完成待索引文档的导入及规范化从文档中抽取文字部分完成编码转换将字符串映射到整数流其他操作38文本预处理分词语素是最小的语音语义结合体，是最小的语言单位。 “字”：简单高效,国家标准GB2312-80 中定义的常用汉字为6763个.表示能力比较差，不能独立地完整地表达语义信息。词是代表一定的意义，具有固定的语音形式，可以独立运用的最小的语言单位。 “词”：表示能力较强，但汉字的词的个数在10万个以上,面临复杂的分词问题 39文本预处理哈希函式从上世纪八十年代开始就有了相关研究 Knuth的研究结果表明，对最常用的31个英文单词建立哈希函式，获得1043种可能的搜索空间，对39个Pascal预定义标识符建立哈希函式，获得搜索空间为2039个节点40文本预处理分词主要方法 基于字符串匹配的分词方法 1）正向最大匹配法 2）逆向最大匹配法 3) 双向最大匹配法 4）最少切分 基于理解的分词方法 基于统计的分词方法 41文本预处理正向最大匹配分词 就是从左至右尽可能查找最长的词，直到当前字符与已经处理的字符串不构成词，输出已经识别的词，并从识别出来的词后面接着查找词。 分词速度比较快 但是分词错误率比较高42文本预处理快速检索词典的意义分词是索引的瓶颈分词的速度决定了索引的速度分词就是循环的词典查找过程词典的查找速度决定索引的速度43文本预处理汉字分词N元切分法(N-gram) ：对一个字符串序列以N为一个切分单位进行切分。如二元切分法： “ABCDEFG” “ABCDEFG” 交叉二元切分法(Overlapping Bigram)：“ABCDEFG” “ABBCCDDEEFFG”简单快速，但会产生大量无意义的标引词，导致标引产生的索引文件的空间，以及检索和进行标引的时间都大大增加。同时，因为它的切分单位并非语言学意义上的词语，所以也会导致检索的查准率下降。 44文本预处理汉字分词SentenceC1C2C3C4C5C6UnigramC1 C2 C3 C4 C5 C66BigramC1C2 C2C3 C3C4 C4C5 C5C65trigramC1C2C3 C2C3C4 C3C4C5 C4C5C6 4Sentence中国大陆新发现的油田Unigram中 国 大 陆 新 发 现 的 油 田10Bigram中国 国大 大陆 陆新 新发 发现 现的 的油 油田9trigram中国大 国大陆 大陆新 陆新发 新发现 发现的 现的油 的油田845文本预处理汉字分词切分歧义(Ambiguition)的消除交集型歧义（交叉歧义）：“组合成” 我们/小组/合成/氢气了；组合/成/分子； “部分居民生活水平”：部分、分居、居民、民生、生活、活水 “学生会组织义演活动” : “学生/会/组织/义演/活动” or “学生会/组织/义演/活动”?组合型歧义（覆盖歧义）：他/从/马/上/下/来；我/马上/就/来/了 ；“老人家在天津”：老人、老人家请请把手把手拿开拿开 这个门这个门把手把手坏了坏了 真/伪歧义“大学生活象白纸”大学 生活 象白纸大学生 活象 白纸46文本预处理中文词法分析正向最大匹配(基于词典的方法) 47文本预处理中文词法分析逆向最大匹配(基于词典的方法) 48文本预处理基于词典和规则的方法最大匹配正向最大匹配、反向最大匹配和双向最大匹配实现简单，而且切分速度快。但无法发现覆盖歧义，对于某些复杂的交叉歧义也会遗漏。 全切分利用词典匹配，获得一个句子所有可能的切分结果。时空开销非常大。 基于理解的分词算法模拟人的理解过程，在分词过程中加入句法和语义分析来处理歧义问题。难以将各种语言信息组织成机器可直接读取的形式，还处在试验阶段49文本预处理汉字分词1.按字切分优点：采用单汉字切分的方法,字典体积最小,切分方法最为简单,最接近自然语言。单汉字存储是处理新词和任意汉字串的天然单元,具有其它方法无法比拟的优点缺点不能自动切分主题词,只能在检索时由用户通过对单字的多词匹配组合主题词。另外,随着数据库容量的增加,索引量急骤上升,耗费时空,且检索速度慢,效率低，其查准率和查全率的高低取决于后控制的智能水平。50文本预处理2.按词切分优点：字典体积较小,比采用规范主题词更灵活,比单汉字更接近自然语言,便于与其他自然语言处理系统联系。缺点由于切词存在歧义的可能性,切词的组合有随意性,一个名词性概念有代用、相关、属分等关系,动词性概念有方式、工具、强度、时间和原因等谓词框架,所以按词切分技术需要结合其他技术措施。3.按主题词切分优点按主题词切分的方法,以综合、专业主题词典为切词依据,优点是切词正确率和专指性高,借助主题词典便于隐含标引。缺点系统空间开销大,而且不能切分主题词典没有收入的自由词和新词等51文本预处理三种汉字分词方法的效率比较52文本预处理按字检索对海量数据库不合适。数据库规模越大，查询性能会指数级下降，在5G以内的数据库上最好的性能为1-5秒（根据检索的复杂性不同），但当数据库规模达几十G以上，则实用性相当差。 信息检索用自动分词和自然语言理解用的自动分词在词的定义和收集范围方面有很大不同，依据语义规则和上下文语境来提高分词准确率对信息检索的贡献不大，而且在某些情况下，产生负作用（如查询需求的自然语言描述缺少上下文）。 N-gram 方法产生的冗余很大，并且没有词典、知识的支持，查准率比较差。 字词混合的索引方式的词索引+BI-GRAM是较好的中文文本索引方式。 开发专用的歧义片断识别软件，并进而建立条歧义处理实例规则库是有效提高分词准确率的手段。 53文本预处理规则和统计结合的方法通常利用词典进行初切分，然后用其它的概率统计方法和简单规则消歧和进行未登录词识别。比如：利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路径法。最大匹配算法、state-of-the-art分类器和支持向量机的结合。通过词典匹配找出所有交叉歧义，利用Bigram语言模型或其变形来消除歧义。基于大规模语料库的统计方法规则和统计结合的方法 54文本预处理适用于大规模中文信息检索的分词算法l分词算法的时间性能要比较高l web搜索实时性要求很高，作为中文信息处理基础的分词应占用尽可能少的时间l分词正确率的提高并不一定带来检索性能的提高l 分词到达一定精度之后，对中文信息检索的影响不再会很明显，虽然仍然还是有一些影响，但是这已经不是CIR的性能瓶颈。在时间和精度之间存在矛盾无法兼顾的情况下，应在二者之间找到一个合适的平衡点 l切分的颗粒度仍然可以依照长词优先准则l 在查询扩展层面进行相关后续处理。在信息检索中，分词算法应集中精力考虑如何消除交叉歧义 l未登录词识别的准确率要比查全率更加重要l 要尽量保证未登录词识别时不进行错误结合，避免因此切分出错误的未登录词。如果将单字错误的结合成未登录词了，则有可能导致无法正确检索到相应的文档55文本预处理待切分文本初切分结果核心词典消除交叉歧义未登录词识别新词词典切分结果交叉歧义检测图3面向大规模中文信息检索的分词算法流程图 56文本预处理 未登录词(Out of Vocabulary )识别 命名实体：数词、人名、地名、机构名、译名、时间、货币 缩略语和术语：“超女”、“非典”、“去离子水” 新词：“酱紫”、“星盘” 先识别已知词还是先识别未登录词 先识别已知词：“内塔尼亚/胡说” 先识别未登录词：“胜利取决/于勇/气”57文本预处理英文分词英文词法分析数字的考虑： 某人想查询1978到1989年间车祸的死亡人数，可能查出来的结果有很多这两年本身的死亡人数，因此，上面的查询中，数字不是一个很好的index term。 但是，一些和字符组合的数字，如“510B.C.”，还有一些长数字，如身份证号、手机号，3.1415926，可能是非常好的index term。 最简单的做法就是所有数字都去掉，复杂的方法需要引入规则来分析，包括对时间的识别和归一化，如：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, butB.C., B.S.: without periods, these are just single lettersURLs as index terms?对大小写的考虑：通常情况下，不考虑大小写，词法分析程序会将所有字母全部变成大写或者小写。但是，某些情况下，同一个单词的大小写含义不一样，如: China和china 进行词法分析时需要考虑引入一些规则方法59文本预处理禁用词消除 禁用词(stop words) 那些在文档中出现过于频繁(如超过80%以上的文档均出现该词)而对于检索没有区分意义的词，常见的禁用词包括冠词、介词、连词 优点： 禁用词消除可以减少term的个数，降低存储空间 缺点： 有时消除的禁用词对检索是有意义的，如：“的士”中的“的”，“to be or not to be”中的各个词，因此有些搜索引擎直接采用全文索引（full index） 60文本预处理 消除方法： 查表法 建立一个禁用词表，通过查表的方式去掉禁用词 基于词频的方法 统计每个词的词频，如果超过总文档数目的某个百分比(如80%)，则作为禁用词去掉61文本预处理 Stemming算法Stemming的必要性名词的单复数形式，动词的各种时态，形容词的各种级等本身含义非常类似。当用户提交某个查询时，很有可能各种相关形式都是用户期望的结果提高检索的召回率用户输入查询关键词goose，一篇介绍goose的文档，虽然不包含单词goose，只包含单词geese，应该是相关的。62文本预处理常用stemming算法Elementarymethods：大小写合并Stemmer算法：单复数合并Porter算法：使用规则去后缀使用一系列后缀变换规则对单词进行变换ednullingnullationalatetionaltionLovinssmethod：特例表Thedictionarymethod：词典保存后缀Corpus-BasedStemming：根据单词的共现度63文本预处理stemming算法的争议很多论文指出，stemming对英文检索系统没有效果。很多结果表明，stemming对荷兰语、阿拉伯语、斯拉夫语等有很大必要。不同的论文用同样的stemming工具，针对同样的测试集得出完全相反的结论。一般认为：Stemming降低了查准率，提高了查全率。查准率的降低不是stemming本身的问题，而是算法实现的效果不好。Stemming本身很有必要，关键是要提高stmming的效果。64文本预处理词干还原中文重叠词还原汉语的某些形容词有重叠式用法。这些重叠式用法是词典里所没有的，所以必须通过还原算法从重叠式用法变回到基本形式上也可以看成是一种“词干”还原 65文本预处理中文重叠词还原文本框: 双字形容词的重叠用法共有三种：ABAB式，AABB式、A里AB式。请看下表示例：66文本预处理中文重叠词还原单字形容词的重叠用法共有两种：ABB式和ABCD式。请看示例：67文本预处理进行词干还原： 好处：减少词典量； 坏处：按词形查不到，词根还原还可能出现错误不进行词干还原：Stopped sto+ppe+d 好处：支持词形查询； 坏处：增加词典量683 索引和排序排序就是扫描每篇文档产生的（文档号，单词号，出现位置）三元组按照单词号重新排序，单词号相同的项再按照文档号排序，单词号和文档号都相同的再按照出现位置排序。排序的过程正好是实现“倒排”的过程排序以后的结果写入临时索引文件。693 索引和排序前向索引 直接对文本进行逐篇扫描费时费力，为解决这个问题，考虑将文本预先处理（由前向索引转换成倒排索引）后进行匹配，就能较快地得到结果。前向索引(Forward index) 将每篇文档表示成Doc ID及其文本内容组成的类向量模式。70索引和排序前向索引实例71索引和排序 前向索引的特征 仍然是依次扫描每个文档，但是对于一个字符串的多次出现不需要一一扫描，而且对同一文档内的字符串查找可以采用二分查找的方式，加快匹配过程。也就是说通过预处理的方式加快对每篇文档的匹配速度。 72索引和排序 倒排索引 使用前向索引，仍然需要逐篇扫描每个文档。如果文档数目较多，那么就非常费时费力。 倒排索引(inverted index) 能够直接从查询词定位到文档。 73索引和排序倒排索引实例74索引和排序对文档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索引和排序倒排索引的更新情况一：出现了新的词，则需要修改词典结构，在词典中增加词条。情况二：出现了新的文档，则在相应的词条下增加posting list。情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。倒排索引对于单个查询词，搜索就是词典查找的过程，不需要扫描所有文档，只需要访问这个词对应的posting list，速度相当快。 774 全文检索方法位置级检索位置检索的四种类型： 记录级 字段或段落级 子字段或自然句级 词位置级78全文检索方法顺序相邻 (W)顺序隔词 (nW)位置相邻(N) 隔词相邻(nN)79全文检索方法子字段内“与”运算 (S)字段内“与”运算(F)主题词字段内“与”运算(L) 80全文检索方法相当于一般逻辑运算多数中文检索系统采用记录级位置检索81全文检索方法采用同义词典，提高查全率关联含义相同的词汇，当用户使用某个词汇检索时，系统直接将同义词取出，构成“或”运算检索式，在全文中匹配查询采用排除词词典，提高查准率关联检索词(例如民法)与希望排除的词(例如人民法院、移民法等)，一种排除方法是系统直接将排除词取出，构成“非”运算检索式，在全文中匹配查询82全文检索方法多级索引结构。采用B+树、INVERT FILE等多种基本索引及其改进模型，实现了一个多级索引结构，使得海量数据库上的查询速度达到亚秒级。 基于成本优化的索引跳跃式扫描技术，比如用户的检索词为“中国足球”，检索词“中国”的命中篇数非常多，而“足球”相对较少，因此在检索逻辑运算时，可以利用索引中的信息，以足球为主运算对象，这样可以有效提高检索速度。 基于词频的BI-GRAM算法。多库并行检索。大内存技术和CACHE技术83全文检索方法一般认为一个优秀的全文检索算法，一个百兆级的全文数据库，检索速度在一两秒内反应提高检索速度的措施： 集合运算中，减少对比次数 分高频和低频词索引，一般只在高频词索引中检索84全文检索方法位置级检索布尔查询的处理 And 关系：A and B，取出A、B的posting list进行交叉合并。 Or 关系：A or B，取出A、B的posting list进行叠加。 Not 关系：A And not B，取出A、B的posting list进行减操作。短语查询的处理 比如查AB，取出A、B的posting list，然后进行交叉合并，并且合并时要满足位置相邻的关系。 855 国内文本和全文信息检索研究概况关键词分析全文检索文本检索向量空间模型数据库超文本检索全文检索系统文本检索会议图像检索数字图书馆全文数据库自然语言处理文本分析文本分类搜索引擎检索效果基于内容的检索倒排文档865 国内文本和全文信息检索研究概况作者分析复旦大学计算机科学系 黄萱菁 ，吴立德, 夏迎炬, 周水庚, 胡运发, 钟亦平, 薛向阳 VSM模型文本过滤文本过滤QA系统全文索引模型中国科学院计算技术研究所杨志峰,王斌,白硕,程学旗,杨哲文本检索算法，TREC，词语权重解放军理工大学指挥自动化学院王元元, 刘海峰，王倩 文本检索VSM模式, 加权模型大连理工大学计算机系 姚天顺,林鸿飞 文本过滤文本结构北京大学信息管理系马张华，李季中文问答系统中国科技大学研究生院计算机学部史忠植,吴斌 概念空间875 国内文本和全文信息检索研究概况发展全文检索系统的研究热点自动标引 单汉字自动标引、词典切分标引、主题词标引全文检索软件 EBSCO TRS,中信所QuickIMS,浙江天宇CGRS885 国内文本和全文信息检索研究概况发展汉字分词技术信息处理用现代汉语分词词表的制定汉语词自动切分算法,:最大匹配法!逆向最大匹配法,逐词遍历法、设立切分标志法、最佳匹配法、有穷多层次列举消除切分歧义的方法：基于规则的方法: 基于统计的方法主要有:基于互信息和T-Test的方法、基于隐Markov模型的方法 .基于SVM和k-NN结合的汉语交集型歧义切分方法、基于EM的方法等。未登录词的识别。利用词颁、上下文信息和未登录词候选词表汉语自动分词应用研究。目前,汉语自动分词主要在信息检索、自动标引、自动文摘、机器翻译、语言文字研究、搜索引擎研究、自然语言理解和中文信息处理等方面的应用取得了可喜的成绩。这一研究成果将会被更广泛的应用到更多的研究领域,如词频统计、内容分析、概念分析、认知心理学和汉语语言学等方面。895 国内文本和全文信息检索研究概况发展优化面向用户的全文检索技术全文数据采集的广泛化 CJFD:期刊、学位论文、会议、专利数据加工的知识元化 从以篇为单位，深入到以知识元为单位检索查询的自动分词化 应用bi-gram为主的分词技术，对查询进行自动分词知识揭示的网络化 数据库内外知识的网络化链接：关键词、作者、引文等本库知识元链接，相同主题的本系统外库链接905 国内文本和全文信息检索研究概况发展存在问题查准率问题 “长江” 长江大学检索结果过多问题主题引擎网页命中结果过多数据更新问题数据滞后915 国内文本和全文信息检索研究概况文本检索存在的问题和发展方向 检索性能较低，查全率和查准率均不尽人意目前进行的智能Agent在全文检索系统中的应用研究，其目的正是为了解决这个问题，尽管已经取得一些初步的成果，今后仍旧是需要研究的方向92本讲总结经典文本检索方法菊池敏典算法，福岛算法，加权检索的原理文本预处理汉字分词方法、词干、禁用词 索引和排序前向索引和倒排索引全文压缩方法和全文检索方法93课后思考题 简述菊池敏典算法，福岛算法的原理和基本功能 比较单汉字、双汉字分词的优缺点，何谓汉字分词粒度？ 试解释负数值的全文索引的膨胀系数