第6章内容索引子系统设计及核心算法.doc

第6章 内容索引子系统设计及核心算法 数据抓取子系统：收集网页数据； 内容检索子系统：提供高效的查询服务； 索引子系统：组织好网页数据，使内容检索子系统能够高效地进行检索。 检索子系统进行检索： 有二种方式 顺序扫描所有网页，判断其是否含有查询词； 建倒排索引； Termi词项，i词项编号； 词项是一个语言单位；英文，单词看作词项；中文，词语看作词项； 建立索引时，将网页文本处理成词项集合，建立倒排索引；检索时，将查询词处理成词项的集合，在索引中检索包含这些词项的网页； 倒排索引结构中，词项后面是含有这个词项的网页列表； pi有多少个网页含有第i个词项； Doc表示一个网页； Docji了表示包含有第i个词项的第j个文档； Posk表示词项在对应文档中第k次出现时的位置。 本章介绍： 由页文本生成词项集合； 倒排索引数据结构； 索引子系统的工作方式。 6.1 最小的语义单位-词项 6.1.1 中文分词问题 英文文本: 单词作为词项，有空格隔开，容易将文本处理成词项的集合。 中文文本： 词和词之间并没有分隔符，不能直接将文本转换成词项的集合。 需要分词过程，将连续的字序列按照一定的规则分成词序列。 什么是词？ 词是需要结合紧密且使用频繁的。 中文分词方法 基于词典的方法； 基于理解的方法； 基于统计的方法。 1．基于词典的分词方法 基于词典的分词方法： 又叫机械分词法，苏联学者20世纪50年代末提出； 依赖机器词典，将要进行分词的句子与词典中的词语进行匹配，如果匹配成功，则将匹配的部分分出来，作为一个词，最后生成一个词语序列。 基于词典匹配分词方法的分类： 正向匹配法（forward matching method）； 逆向匹配法（backward matching method）。 根据匹配时的优先长度，又可分为最大匹配法、最小匹配法。 常见的基于词典的分词方法： 正向最大匹配法； 逆向最大匹配法； 最少切分法。 逆向最大匹配法： 扫描过程从右到左，优先匹配长度最大的词语，匹配不到则逐次减少匹配字数，直到匹配成功或者字数为1作为单字词。 最少切分法： 使切分出来的词语个数尽可能地少，可以看作有向图中有哪些信誉好的足球投注网站最短路径。 例： 在词典中含有词语：“发展”、“中国”、“国家”，那么句子“发展中国家”就可以被抽象成如下图所示的有向图。 最少切分法的分词过程就相当于在这个图中有哪些信誉好的足球投注网站从节点①到节点⑥的最短路径。 2．分词算法中面临的问题 研究表明： 正向最大匹配法的分词错误率为1/169； 逆向最大匹配法的分词错误率为1/245； 机器词典的规模、质量对分词效果影响很大；没有出现在词典中的词，无法被正确分词。 新词、派生词不断出现；没有被词典收录的词，被称作“未登录词”。 分词算法面临的问题： 识别未登录词； 识别未登录词主要使用统计方法； 词是稳定的字的组合；上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词； 统计两个字在语料集合中的出现频率，可以一定程度地表明两个字能够构成一个词的概率； 如在语料中发现“蓝”字和“牙”字同时出现的次数非常多，那么它们就很有可能构成一个新词。 这种方法也会抽取出一些非常高频的但是并不是一个词的常用组合，比如“我的”、“这一”等等。 歧义问题； 交集型歧义 汉字串“ABC” ( A、B、C 都为汉字串）中“AB”和“BC ”都是词，无法确定是分割成“AB / C”，还是“A / BC”时， ABC ，被称为“交集型歧义”，汉字串“B”被称为“交集串”。 “结合成分子”，可以被分为“结合／成分／子”，也可以被分成“结合／成／分子”，还可以被分成“结／合成／分子”。 覆盖型歧义 当汉字串“A”、“B”、“AB”同时是词时，“AB”则被称为“覆盖型歧义”； 如：汉字串“起身”，在句子“他站起身来”中，要被分开成“他／站／起／身／来”；而在“他明天起身去北京”中，要分为一个词“他／明天／起身／去／北京”。 为了解决歧义问题，出现了基于理解的分词方法，模拟人理解句子的过程，对句子进行句法分析和语义分析。 有哪些信誉好的足球投注网站引擎分词方法 强调实时性、时间开销；一般使用词典匹配方法； 正确率到一定程度后，对检索性能提高不大，不必过分追求准确率； 尽可能使长词优先匹配，对覆盖型歧义，可以采用多粒度分词； 如“中国科学院”，分词之后既保留“中国／科学院”，又保留“中国／科学／院”； 未登录词，有哪些信誉好的足球投注网站引擎对准确率的要求很高，要求识别出来的未登录词尽可能是正确的，对能不能把所有未登录词都识别出来则要求不高； 有哪些信誉好的足球投注网站引擎分词使用的词典，要符合用户语言习惯； 处理网页文本、用户查询时，使用同样的分词方法，这样可以保证一定的容错性。 6.1.