搜索引擎PPT课件

1、第11章 搜索引擎,主要内容,语言和文字 语法分析 统计语言分析 中文分词 网络爬虫 文本分类 搜索引擎,语言文字,在人类文明中，语言文字和数学一样都是信息的载体，但直到半个世纪前，香农的信息论才把两者结合在了一起。 1948年，贝尔实验室的香农发表了“通信的数学原理”，奠定了现代信息理论的基础。 香农（Claude ElwoodShannon，19162001），美国数学家、电子工程师和密码学家。,语言文字,古代文字象形文字 中国：殷墟文化遗址的甲骨文距今约3200年 古埃及：“亚尼的死亡之书”距今约33003400年,语言文字,古代文字拼音文字 古巴比伦：位于美索不达米亚平原，现伊拉克境内

2、，距今约5000年。 楔形文字：约公元前3200年苏美尔人发明了象形文字，后来发展、简化为楔形文字，常见于考古发现的大量泥板,语言文字,古代文字拼音文字 公元前七世纪，希腊人和罗马人统治埃及，古埃及象形文字失传，出现拼音文字 罗塞塔石碑：1799年由法军上尉在埃及的罗塞塔发现，在战争中辗转到英国，现为大英博物馆镇馆之宝。制作于公元前196年，用3种文字刻有古埃及法老托勒密五世诏书，考古学家依此对照解读失传千余年的埃及象形文字，现代人得以了解3000多年前的古埃及。,语言文字,古代的计数方法 文字和数字几乎是同时出现的 中国、古罗马、巴比伦的数字都使用象形文字（横、竖、楔形），古印度则使用抽象的

3、符号 中国人、印度人发现了倍数进位制，如中国的个十百千万。罗马人采用加减法进位，如IV、XXII 其他进制：玛雅人使用20进制；在印度、斯里兰卡等地曾使用12进制，见于混乱的英制（美国是唯一一个使用英制的国家）,语言文字,印欧语系 腓尼基人将楔形文字传播到希腊后，与古希腊的文字结合，逐步发展成为现在的欧亚非大陆体系语言印欧语系 圣经：犹太人将创世纪以来的历史记录在圣经中，并广为传送。为防止抄录错误，发明了数字校验码,语言文字,古文：因书写困难，不得不简化 中国古文：如诗经、易经 西方古文字：如旧约 但语言不是语法： 中国的白话文形如口语，口语几千年未变，如岭南客家话 莎士比亚喜剧的语言不符合语

4、法规则，但为大家所接受,语法分析,语言的出现实现了通信，语句是信息的表现形式，文字、数字是信息的编码方式，语法规则是编码、解码的算法 1950年，图灵的“计算的机器和智能”就提出了机器智能（即人工智能）的问题，但直到1970年代，随着统计语言分析方法的研究，才取得了突破性的成绩 两个阶段： 5070年代，让机器学习人类智能，分析语法 70年代以后，利用统计学规律,语义分析,早期研究是基于语言的句法分析的，主要考虑语法规则 例：徐志摩喜欢林徽因。 分析：每个句子可分为3部分，每个部分又可以进一步分析，构成语法分析树分析句子的文法规则叫规则重写,语义分析,重写规则包括： 句子主语 谓语 句号 主语

5、名词 谓语动词 名词短语 名词短语名词 名词徐志摩 动词喜欢 名词林徽因 句号。,语义分析,自然语言处理依靠人工书写文法规则，如机器翻译公司SysTran，直到2000年后，仍采用人工方法 但复杂语句的规则重写困难重重，例：美联储主席本伯南克昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司。这个句子的文法（其他略）为：主语美联储主席本伯南克 谓语昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司 句号。,语法分析,70年代，基于规则的句法分析走到了尽头。不仅是因为规则的复杂性，同时还要考虑句子的多义性。例如（1966年，明斯基）： The pen

6、is in the box. The box is in the pen. 70年代，IBM贾里尼克领导的小组在研究语音识别系统时采用了统计学方法，极大地提高了识别率和速度，促进了统计语言分析的发展 直到2005年，随着Google推出基于统计学的翻译系统，SysTran才放弃规则分析方法,统计语言分析,例：下面的句子合理吗？ 美联储主席本伯南克昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司。 本伯南克保险美联储主席告诉昨天上百家7000亿媒体美元的资金救助银行、公司汽车和公司将借给。 百本伯美席助主司告联南克储和天诉体7000公车元险的救亿资将美昨借媒给上司银金家行

7、、保公汽。 句子是否合理取决于语法、语义吗？ 人类智能符合这一规律，但下面的句子呢？ 乒乓球拍卖完了。 问：“在吗？”，答：“在。”,统计语言分析,贾里尼克：语句的合理性取决于它在语言中出现的可能性 语句出现的可能性由该语句在人类语言中的出现概率决定，包括口语、文字记录、文学、新闻报道等等 语句1、2、3的概率可能是10-20、10-25、10-80 因此语句1更合理,统计语言分析,显然无法直接统计句子的出现概率 可采用条件概率：设语句s由n个词（w1、w2、wn）组成，即s=w1w2wn，语句s出现的概率为p(s)=p(w1, w2, . wn)，利用条件概率公式，进一步表示为p(s)=p(

8、w1)*p(w2|w1)*p(w3|w1,w2)*p(wn|w1,w2,wn-1)，其中，p(w2|w1)表示已知w1的条件下w2的出现概率若把wi的概率简化为只与wi-1有关，则简化为： p(s)=p(w1)*p(w2|w1)*p(w3|w2)*p(wn|wn-1)p(wi|wi-1)可通过统计语言中词wi在wi-1之后的出现频率获得 因此，语句的概率可通过分析构成语句的词汇的条件概率计算出来,中文分词,分词即把语句的词分割、提取出来 拼音文字无需分词 中文分词： 基于字典的分词 按最长词匹配 先从左到右、再从右到左二次分词,例：（1）乒乓球拍卖完了（2）乒乓球拍卖完了,中文分词,统计学分词

9、：先按一般方法分词，再分析各种分词方案形成语句的统计学概率语句s可有多种分词方案，比如：SA=A1A2AnSB=B1B2BkSC=C1C2Cm则各种组合的概率为p(SA)、p(SB)、p(SC)若p(SA)p(SB)且p(SA)p(SC)则应采用A方案 实际上，并不穷举所有分词方案,网络爬虫,网络爬虫（crawler，spider，robot) 是一种按照一定规则，自动搜索、下载网页、提取信息的程序。 网页的URL用以标识和供浏览器访问 网页中存在许多超链接，用于实现向其他网页或网站的跳转。相关联的网页通过超链接形成一个网络,网络爬虫,图的遍历 格尼斯堡七桥 广度优先 北京-天津-石家庄-济南

10、-青岛-上海-沈阳-太原 深度优先 北京-天津-济南-青岛-上海-石家庄-太原-沈阳 Web是一个较大（可能无限）的网，遍历应设定条件,文本分类,关键词 通常，网页可以用关键词标出 关键词权重用于区分网页的相关性 不能用关键词出现的次数表示相关性，而常采用“频率”TF-IDF（即出现次数除以总字数） “停止词”（如的、地、得、是等）不予考虑 通用词（如“应用”）比专用词（如“原子能”）频率高，因此应设置“权重”（需要人为设定） 一般地，如果某关键词出现次数很少，但已经可以决定相关性，则权重应较高。反之，则取较低的权重。,文本分类,新闻分类：将相似的新闻放在一起作为一类，以便编辑使用 通常，新闻

11、分类不使用关键词，而直接使用正文中的实词（不是虚词） 新闻中每个词的重要性不同，但只要出现几个特定的词就可以确定新闻分类,文本分类,新闻分类 将新闻涉及的所有词汇排序构成一个词汇表（巨大！） 把某篇新闻中的词汇统计出TF-IDF（即频率） 把未出现的词汇的TF-IDF标为0 构建一个“向量”，代表这篇新闻 利用余弦定理计算两篇新闻向量的距离（即夹角），用于标识相关性 将相关的新闻归为一类,文本分类,新闻分类 按主题分类：如奥运会、欧洲杯 按词分类：如足球、马拉松 由于计算量巨大，不能直接计算两篇新闻的向量的距离（大矩阵运算）,文本分类,如果新闻词有M个，新闻篇数为N，则A是一MxN的矩阵，其元

12、素为某篇文章中某个词的TF-IDF 利用矩阵的奇异值运算，可将A分解为3个矩阵的积，即A=XBY 这里，把所有新闻词分为若干关键词类，矩阵X的元素为某个新闻词与某个关键词类的相关性。把所有新闻分为若干主题类，矩阵Y的元素为某篇新闻与某个主题类的相关性。B为关键词类和主题词类的关联矩阵，为一对角矩阵这样，要处理的矩阵运算就大大简化了,搜索引擎,搜索引擎的发展 1990年，加拿大麦吉尔大学开发出Archie，实现了对FTP文件的搜索 1993年，斯坦福大学学生开发了Excite系统实现了Web信息检索 1994年，斯坦福大学、美籍华人杨致远和David Filo共同创办了Yahoo！，支持目录搜索。Yahoo！采用手工编录，准确率高，速度快 1994年，WebCrawler面世，支持全文检索 1995年，元搜索引擎出现 1996年，Sohu；1998年，Google；2000年，百度,搜索引擎,搜索引擎数据库 网页的存储：网络爬虫下载的网页，按一定规则存放在数据库中 数据库索引：数据库中存放了万亿以上的网页，要进行快速的查询，就要依靠数据库索引 搜索引擎数据库的索引 一个较简单的方法是采用二进制串索引，对于每一个关键词，如果出现在某个网页中就记为