三 搜索引擎的分析系统
1目标工作
信息抽取并结构化网页
网页销重
中文分词
PageRank计算
html语言
用于创建存储在www服务器上的文件并且能由浏览器浏览,简单易用,不需要编译.
瞄文本(anchor text)
关于链接的一段描述,通常以文本或者图片方式存在.指向文本中的某一位置或者其他网页.
eg:<a href = "http://zoujisousuoyinqing.com">走进搜索引擎</a>用来描述一个链接
半结构化数据
html语言的基本特点:标签方式标识网页信息
2 信息抽取及网页信息结构化
对于分析系统来说,基础工作就是分门别类的从半结构化网页中提取有价值的能够代表网页的属性.eg:瞄文本,标题,正文等,并将这些属性结合组成网页对象.
这种处理称为"网页结构化"
2.1 网页结构化的目标
针对搜索的需要,将HTML网页数据按照基本属性抽取,而后打包(wrap)出一个网页对象
1)瞄文本
2)标题(title)<title>网页制作者编写
3)正文标题(content title)<titile>网页编辑者编写
4)正文(content)<div><table><p>等
5)正向链接(link)
一个结构化过程
网页结构化过程
注:这个过程分为两个步骤
1)建立html标签树
2)通过投票方式识别正文的文本块,并按深度优先遍历的规则组织为正文
2.2 建立HTML标签树
基于html标签成对出现的问题,利用栈来进行处理.
从html网页到结构化网页
2.3 投票方式得到正文.
正文比较复杂,没有明显的标签标记正文;正文可能分割在多个html标签中.
三类文本块
1)主题文本块(topic)
2)目录性文本块(hub)
3)图片型文本块(pic)
判断哪个文本块是正文采用"投票算法"计算方法,类似权重问题.
获取文本块之后的工作就是组织文本块了.采用深度遍历标签树的方式进行处理.
网页存储采用结构化方式进行处理.类似文件压缩.分析过程使用标签树(BeautifulSoup...)
3.1 网页查重
重复情况
1)内容和格式完全相同
2)内容相同,格式不同
3)部分重要内容相同并且格式相同
4)部分重要内容相同但是格式不
网页相似的4中形式
基本方案是使用签名值的方式进行判别
3.2 查重实现方法
I-Match算法:假设 最高频,最低频词不能代表文档本质.,所以,去掉最高,最低词频词,然后进行签名处理
Single算法:抽取多个特征词汇,通过比较两个特征词集的相似度来实现文档查重.
Single示例
Single算法结论:
对于长度为L的文档,每隔N个汉字取一个Single这样一共得到L-N+1个Single,可见N的取值对效率和效果影响很大.N取值2-L.
大规模文档查重使维护一个hashtable或者bloom就可以.
Single算法略麻烦:Jaccard系数,用来判断集合的相似度J = (A&B)/(A|B)
然后定义一个标准相似度值eg:0.2判定为相似.
方案比较
I-Match:需要提取分词,并计算词频,提取特征比较复杂,但是是否相似的计算计较简单
Single算法:提取特真简单,但是文档是否相似计算 复杂.
Single算法性能上表现优异,所以广泛使用
总结:网页查重三个步骤:
1)特征抽取
2)相似度计算
3)消重
4 中文分词
1.目前的分词手段依赖字典和统计学方法
2.通过查字典实现分词
三种难以区分类型
1)交集型歧义
"从小学": 从小/学/电脑 从/小学/毕业
2)组合型歧义
"中将" : 美军/中将/竟然... 新建地铁中/将/禁止商业摆摊
3)混合型歧义
"人才能": 人才/能 人/才能 人/才/能
对于字典方式进行分词:
字典采用前缀树或者后缀树的结构存储
注:双圆圈表示一个词尾
前缀树结构的字典组织形式
注:对于后缀树:双圆圈表示一个词头
后缀树的字典组织形式
两种匹配方式
"最大正向匹配法(MM法)"
"逆向最大匹配法(RMM)"
这类分词方法称为贪婪算法:最大匹配最优
贪婪算法导致局部最优
"N-Gram方法":可以满足由于错分词带来的损失.
eg:2-Gram.类似Single方式,获取2步长的所有分词作为索引.
N-方法虽然有效避免错误词典分词导致索引不完整,可能导致过多的关键词成为索引项.不经济
ps:没有一种方式能够解决所有的问题.然,字典分词方式作为主流分词方法解决大部分分词问题.但是字典总是滞后于语言的发展.
所以,如果能够及时,自动的,准确的发现新词,才能最大化字典分词方案.新词发现主要通过统计推断来实现.
基于统计的新词发现
5 PageRank(网页排名)
5.1 基本思想
网页重要性:
1)认可度越高backlink越多
2)反向连接的源网页质量越高,所指向的网页越重要
3)链接数越少的网页越重要
具体实现依赖数学高度.参考
6 分析系统结构图
分析系统主要承担:网页结构化,网页消重,文本分词及pageRank等4项基本任务.
结构图:
分析系统结构图
注解:Page库是通过爬虫下载到的原始网页,分析系统通过以下步骤进行网页分析:
1)结构化过程:建立标签树,并提取有价值的树形,完成从原始网页打包为网页对象的过程
2)网页消重模块
3)文本分词将文本切分为以词汇为单位的集合
4)将分析的结果发往索引模块,进行索引入库
