搜索引擎关键技术文本处理.ppt

网络搜索引擎关键技术网络搜索引擎关键技术 文本处理文本处理 主要内容主要内容 本讲稿对搜索引擎的关键技术进行了概 述，着重讨论了信息预处理技术中的文本处 理。 一一. .搜索引擎的关键技术搜索引擎的关键技术 1. 信息收集和存储技术 包括两种方式：人工和自动。 人工方式采用传统的信息收集、分类、存储、 组织和检索的方法。 自动方式通常是由网络机器人来完成的。 一般来说，人工方式收集信息的准确性要远优 于“网络机器人”，但其收集信息的效率及全面性 低于“网络机器人”。 2.信息预处理技术 信息预处理系统的主要工作是从抓取的网页 中提取能够代表网页的属性，并将这些属性组成 网页的对象，然后根据一定的相关度算法进行计 算，得到每一个网页针对页面内容及链接每一个 关键词的相关度，并用这些信息建立索引数据库 。 关键词的提取 重复或转载网页的消除 链接分析 网页重要程度的计算 3.信息索引技术 信息索引就是创建文档信息的特征记录，以 便用户能够快速地检索到所需信息。 信息语词切分和语词词法分析 进行词性标注及相关的自然语言处理 建立检索项索引 检索结果处理技术 二二. .文本处理文本处理 文本处理是指将网络爬虫搜集到的文 本信息进行预处理，以便进行网络信息检 索的下一个流程索引处理。 网页噪声去除 待处理网页干净网页 词汇分析 词序列 词干提取 排除停用词 有用词序列关键词 HTML文档预处理流程 文本处理的过程包括如下5个步骤： 文本的词法分析 无用词汇的删除 词干提取 索引词条/词干的选择 构造词条的分类结构 1.1.词法分析词法分析 词法分析的过程是将字符串转换成词 条的过程，因此词法分析的主要目的就是 识别文本中的词条。 关于词法分析，中英文存在较大的区 别，英文单词有空格分隔，易于识别，而 中文文本以句子为自然分隔单位，要提取 出词语来，需要复杂的分词技术。 在对英文进行分词的过程中，除了空 格分隔符，还有几种特殊的情况要处理： 数字、连字符、标点符号和字母的大小写 。 数字 数字一般不作为索引词，因为如果没 有上下文的联系，它们的含义是模糊不清 的。 现在常用的做法是保留一些专门指出 的（通过与正规表达式的匹配）数字，而 将其他数字过滤掉。 连字符 对连字符来说，也有两难情况。 一种方法是将连字符都忽略掉，例如 state-of-the-art等同于state of the art 。但是，有些带有连字符的单词本身是一 个完整的单词，如gilt-edged。 对于连字符的处理，目前常用的是首 先采用一定的规则选出那些对词义有影响 的连字符号，然后将其他连字符都过滤掉 。 标点符号 对于文本中的标点符号，一般说来在 词法分析过程中将被全部去除。但是，对 于那些成为单词中一部分的标点符号来说 ，又要慎重考虑是否删除标点。 另外一种特殊情况是程序片段出现在 文本中，这时就要区分变量x.id与xid了。 这种情况下，标点符号应该保留。 字母的大小写 字母的大小写对于区分索引词条来说 一般不是很重要，因此可以将文本中的所 有词条都转换成大写或者小写。 但是也存在特殊情况，例如对于描写 UNIX命令的文档，由于大小写都是约定俗 成的，因此用户并不希望改变文档中的大 小写。对于此种情况，就要特殊处理。 2.中文分词技术 中文分词技术属于自然语言处理技术 范畴，对于一句话，人可以通过自己的知 识来明白哪些是词，哪些不是词，但如何 让计算机也能理解？其处理过程就是分词 算法。 与英文相比，中文词与词之间没有分 界符，需要人为切分，而且汉语中存在大 量歧义现象，对几个字分词可能有好多种 结果，因此将中文分词技术专门提出来做 详细总结。 中文分词方式中文分词方式 a. 单字切分 按照中文一个字、一个字地进行分词 。以这种方式切分出来的词再进入索引， 称为字索引。 缺点：随着索引的增大，相应索引条 目的内容会不断增大，严重影响效率。 b. 二分法 二分法是指每两个字进行一次切分。 该方法完全不考虑语义、语境，机械 地对语句进行处理，不是很好的分词方式 。 c. 词库分词 该方法是用一个已经建立好的词的 集合（按某种算法）去匹配目标，当遇上 集合中已经存在的词时，就将其切分出来 ，是一种较理想的中文分词方式。 中文分词算法 a. 基于字符串匹配的分词方法 该方法又叫做机械分词方法，基本思 想是：截取一个字符串，把它与词典中的 词条进行匹配，若在词典中找到对应的词 ，该字符串就被识别为一个词。 按照扫描方向的不同，可分为正向匹 配和逆向匹配；按照不同长度优先匹配的 情况，可分为最大匹配和最小匹配；按照 是否与词性标注过程相结合，可分为单纯 分词方法和分词与标注相结合的一体化方 法。 a) 正向最大匹配法FMM（Forward Maximum Matching method） 主要思想：选取包含68个汉字的符 号串作为最大符号串，把最大符号串与词 典中的单词条目相匹配，如果不能匹配， 就削掉最右边一个汉字继续匹配，直到在 词典中找到相应的单词为止。 正向是指匹配方式从左向右。 例：“计算机科学和工程” b) 逆向最大匹配法BMM（Backward Maximum Matching method） 其分词过程与正向最大匹配法相同， 不同的是每次是从待处理语料的末尾开始 处理，每次匹配不成功时去掉的是前面一 个汉字，即匹配方向是从右到左。 FMM方法的错误切分率为1/169， BMM方法的精度要高一些，其错误切分率 为1/245。 c)双向匹配法BM（Bi-direction Matching method） 基本原理：分别用FMM法和BMM法进 行正向和逆向的扫描和切分，通过比较两 者的切分结果来决定正确的切分，而且可 以识别出分词中的交叉歧义。但是对于正 、逆向的扫描结果一致但实际切分不正确 的字段（如“结合成分子时”）仍不能正确处 理。 缺点：时间复杂度增加，而且词库结 构比一般的分词词库要复杂很多。 d) 最少匹配算法FWM（Fewest Words Matching method） 该算法实现的分词结果中含词数最少 。 e) 设立切分标识法 该算法的思想是：优先在待分析字符 串中识别和切分出一些带有明显特征的词 ，以这些词作为断点，可将原字符串分为 较小的串，然后用FMM或BMM法进行细 分。 例：“这种设计方法学的理论，不可 能有用” b.基于理解的分词方法 这种分词方法是通过让计算机模拟人 对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句 法、语义分析，利用句法信息和语义信息 来处理歧义现象。 该分词方法需要使用大量的语言知识 和信息。由于汉语语言知识的笼统、复杂 性，难以将各种语言信息组织成机器可直 接读取的形式，因此目前基于理解的分词 系统还处在试验阶段。 c.基于统计的分词方法 从形式上看，词是稳定的字的组合， 因此在上下文中，相邻的字同时出现的次 数越多，就越有可能构成一个词。因此字 与字相邻共现的频率或概率能够较好地反 映成词的可信度。 于是可以对语料中相邻共现的各个字 的组合的频度进行统计，计算它们的互现 信息。互现信息体现了汉字之间结合关系 的紧密程度。当紧密程度高于某一个阈值 时，便可认为此字组可能构成了一个词。 d.分词中的难题 a) 歧义识别 歧义是指同样的一句话，可能有两种 或者更多的切分方法，这是由中文本身的 特性形成的。 包括： 交叉歧义，如“表面的”； 组合歧义，如“这个门把手坏了”； 真歧义，如“乒乓球拍卖完了”。 b)b)新词识别新词识别 由于中文信息检索系统中的索引项是 基于一定的词库构建而成的，定期更新， 那么对于一些没有收入词库而用户提交查 询的新词，检索系统是无法按照用户的本 意来识别这些新词的。 人名、机构名、地名、产品名、商标 名、简称、省略语等都可能是新词，目前 新词识别准确率已经成为评价一个分词系 统好坏的重要标志之一。 3.3.无用词删除无用词删除 在网页或文档集合中出现频率高于 80%的单词通常被称为无用词或停用词（ stopword），它们对文档的含义没有任何 意义，不具有很好的文档区分能力，需要 被过滤、屏蔽掉。 删除无用词，一方面可以减小索引空 间，另一方面可以提高检索精度，但也可 能会降低系统的召回率（查全率），使得 用户不能查到自己需要的网页。 4.4.词干提取词干提取 词干是去除单词的前缀和后缀后剩 下的部分。词干提取就是把同词干同义 的不同词语中的相同部分提取出来。 优点 a.在一定程度上提高信息获取的性能 b.缩小索引空间的大小 缺点 可能会有勿截，造成词义的改变，影响 查询的结果 词干提取方法词干提取方法 a. 查表法 b. 词缀删除法 c. 后继变化数 d. N个字符列 应用最多的，最实际的词干提取方法 是去除词缀法。 Porter算法是最著名的词缀去除方法 。 5.5.索引词选择索引词选择 并不一定对文档中出现的所有词条都 建立索引，而是选择一些比较重要的词条 来建立索引。 科技文献一般由专家来选择索引词汇，方 法准确，但需消耗大量人力； 另一种可选的方法是通过对文档的分析来 自动选择索引词，该方法没有第一种方法 准确，但可由系统自动实现。 6.6.词典词典 词典是用来根据词汇找到对应词汇信 息的数据汇编。 词典的主要内容 a. 有关某个领域知识的重要词汇； b. 对于词典中的