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

1、网络搜索引擎关键技术文本处理,主要内容,本讲稿对搜索引擎的关键技术进行了概 述，着重讨论了信息预处理技术中的文本处 理。,一.搜索引擎的关键技术,信息收集和存储技术 包括两种方式：人工和自动。 人工方式采用传统的信息收集、分类、存储、组织和检索的方法。 自动方式通常是由网络机器人来完成的。 一般来说，人工方式收集信息的准确性要远优于“网络机器人”，但其收集信息的效率及全面性低于“网络机器人”。,2.信息预处理技术 信息预处理系统的主要工作是从抓取的网页中提取能够代表网页的属性，并将这些属性组成网页的对象，然后根据一定的相关度算法进行计算，得到每一个网页针对页面内容及链接每一个关键词的相关度，并

2、用这些信息建立索引数据库。 关键词的提取 重复或转载网页的消除 链接分析 网页重要程度的计算,3.信息索引技术 信息索引就是创建文档信息的特征记录，以便用户能够快速地检索到所需信息。 信息语词切分和语词词法分析 进行词性标注及相关的自然语言处理 建立检索项索引 检索结果处理技术,二.文本处理,文本处理是指将网络爬虫搜集到的文本信息进行预处理，以便进行网络信息检索的下一个流程索引处理。,网页噪声去除,待处理网页,干净网页,词汇分析,词序列,词干提取,排除停用词,有用词序列,关键词,HTML文档预处理流程,文本处理的过程包括如下5个步骤： 文本的词法分析 无用词汇的删除 词干提取 索引词条/词干的

3、选择 构造词条的分类结构,1.词法分析,词法分析的过程是将字符串转换成词条的过程，因此词法分析的主要目的就是识别文本中的词条。 关于词法分析，中英文存在较大的区别，英文单词有空格分隔，易于识别，而中文文本以句子为自然分隔单位，要提取出词语来，需要复杂的分词技术。,在对英文进行分词的过程中，除了空格分隔符，还有几种特殊的情况要处理：数字、连字符、标点符号和字母的大小写。 数字 数字一般不作为索引词，因为如果没有上下文的联系，它们的含义是模糊不清的。 现在常用的做法是保留一些专门指出的（通过与正规表达式的匹配）数字，而将其他数字过滤掉。,连字符 对连字符来说，也有两难情况。 一种方法是将连字符都忽

4、略掉，例如state-of-the-art等同于state of the art。但是，有些带有连字符的单词本身是一个完整的单词，如gilt-edged。 对于连字符的处理，目前常用的是首先采用一定的规则选出那些对词义有影响的连字符号，然后将其他连字符都过滤掉。,标点符号 对于文本中的标点符号，一般说来在词法分析过程中将被全部去除。但是，对于那些成为单词中一部分的标点符号来说，又要慎重考虑是否删除标点。 另外一种特殊情况是程序片段出现在文本中，这时就要区分变量x.id与xid了。这种情况下，标点符号应该保留。,字母的大小写 字母的大小写对于区分索引词条来说一般不是很重要，因此可以将文本中的所有

5、词条都转换成大写或者小写。 但是也存在特殊情况，例如对于描写UNIX命令的文档，由于大小写都是约定俗成的，因此用户并不希望改变文档中的大小写。对于此种情况，就要特殊处理。,2.中文分词技术,中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。 与英文相比，中文词与词之间没有分界符，需要人为切分，而且汉语中存在大量歧义现象，对几个字分词可能有好多种结果，因此将中文分词技术专门提出来做详细总结。,中文分词方式,单字切分 按照中文一个字、一个字地进行分词。以这种方式切分出来的词再进入索引，称为字索引。 缺点

6、：随着索引的增大，相应索引条目的内容会不断增大，严重影响效率。,二分法 二分法是指每两个字进行一次切分。 该方法完全不考虑语义、语境，机械地对语句进行处理，不是很好的分词方式。 词库分词 该方法是用一个已经建立好的词的集合（按某种算法）去匹配目标，当遇上集合中已经存在的词时，就将其切分出来，是一种较理想的中文分词方式。,中文分词算法,基于字符串匹配的分词方法 该方法又叫做机械分词方法，基本思想是：截取一个字符串，把它与词典中的词条进行匹配，若在词典中找到对应的词，该字符串就被识别为一个词。 按照扫描方向的不同，可分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可分为最大匹配和最小匹配；按照

7、是否与词性标注过程相结合，可分为单纯分词方法和分词与标注相结合的一体化方法。,正向最大匹配法FMM（Forward Maximum Matching method）,主要思想：选取包含68个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉最右边一个汉字继续匹配，直到在词典中找到相应的单词为止。 正向是指匹配方式从左向右。 例：“计算机科学和工程”,逆向最大匹配法BMM（Backward Maximum Matching method）,其分词过程与正向最大匹配法相同，不同的是每次是从待处理语料的末尾开始处理，每次匹配不成功时去掉的是前面一个汉字，即匹配方向

8、是从右到左。 FMM方法的错误切分率为1/169，BMM方法的精度要高一些，其错误切分率为1/245。,双向匹配法BM（Bi-direction Matching method）,基本原理：分别用FMM法和BMM法进行正向和逆向的扫描和切分，通过比较两者的切分结果来决定正确的切分，而且可以识别出分词中的交叉歧义。但是对于正、逆向的扫描结果一致但实际切分不正确的字段（如“结合成分子时”）仍不能正确处理。 缺点：时间复杂度增加，而且词库结构比一般的分词词库要复杂很多。,最少匹配算法FWM（Fewest Words Matching method） 该算法实现的分词结果中含词数最少。 设立切分标识法

9、 该算法的思想是：优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串，然后用FMM或BMM法进行细分。 例：“这种设计方法学的理论，不可能有用”,基于理解的分词方法,这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 该分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。,基于统计的分词方法,从形式上看，词是稳定的字的组合，因此在上下文中，相邻的

10、字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好地反映成词的可信度。 于是可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。,分词中的难题,歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法，这是由中文本身的特性形成的。 包括： 交叉歧义，如“表面的”； 组合歧义，如“这个门把手坏了”； 真歧义，如“乒乓球拍卖完了”。,新词识别,由于中文信息检索系统中的索引项是基于一定的词库构建而成的，定期更新，那么对于一些没有收入词库而用户提交

11、查询的新词，检索系统是无法按照用户的本意来识别这些新词的。 人名、机构名、地名、产品名、商标名、简称、省略语等都可能是新词，目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。,3.无用词删除,在网页或文档集合中出现频率高于80%的单词通常被称为无用词或停用词（stopword），它们对文档的含义没有任何意义，不具有很好的文档区分能力，需要被过滤、屏蔽掉。 删除无用词，一方面可以减小索引空间，另一方面可以提高检索精度，但也可能会降低系统的召回率（查全率），使得用户不能查到自己需要的网页。,4.词干提取,词干是去除单词的前缀和后缀后剩下的部分。词干提取就是把同词干同义的不同词语中的相同

12、部分提取出来。 优点 a.在一定程度上提高信息获取的性能 b.缩小索引空间的大小 缺点 可能会有勿截，造成词义的改变，影响查询的结果,词干提取方法,查表法 词缀删除法 后继变化数 N个字符列 应用最多的，最实际的词干提取方法是去除词缀法。 Porter算法是最著名的词缀去除方法。,5.索引词选择,并不一定对文档中出现的所有词条都建立索引，而是选择一些比较重要的词条来建立索引。 科技文献一般由专家来选择索引词汇，方法准确，但需消耗大量人力； 另一种可选的方法是通过对文档的分析来自动选择索引词，该方法没有第一种方法准确，但可由系统自动实现。,6.词典,词典是用来根据词汇找到对应词汇信息的数据汇编。 词典的主要内容 a. 有关某个领域知识的重要词汇； b.