电子商务-A-第08讲-补充.ppt

1 30 电子商务 张文新副教授 电话mail zhangwx 课程安排 2 30 3 30 第8讲 电子商务搜索引擎技术 电子商务搜索引擎技术 搜索引擎的关键技术网络蜘蛛 Spider Robot Crawler 网页结构化信息抽取中文分词搜索结果排序 4 30 电子商务搜索引擎技术 网络蜘蛛 Spider Robot Crawler 对URL链接进行遍历基本数据结构一个待扩展的URL表一个已经访问过的URL地址表 5 30 图 网络蜘蛛基本数据结构图 电子商务搜索引擎技术 网络蜘蛛 Spider Robot Crawler 遍历URL地址遍历的策略广度优先深度优先 6 30 A B C D E F H G I A F GE H I 电子商务搜索引擎技术 搜索引擎的关键技术提取文档中的文本内容 网页结构化信息抽取 HTML文件中提取文本识别网页的编码STEP 1 从Web服务器返回的contenttype中提取编码 STEP 2 从网页的Meta信息中识别字符编码 STEP 3 从返回流的二进制格式判断 确定网页语言 对HTML文件进行解析 识别三类节点 RemarkNode 注释 TagNode 标签 TextNode 文本 7 30 电子商务搜索引擎技术 提取文档中的文本内容 网页结构化信息抽取 HTML文件中提取文本 续 结构化信息提取DOM 文档对象模型 结构HTML扫描器例如 Node getAttributes getNamedItem src 参考NekoHTML 8 30 电子商务搜索引擎技术 DOM树 9 30 电子商务搜索引擎技术 提取文档中的文本内容 网页结构化信息抽取 HTML文件中提取文本 续 网页结构相似度计算自动提取结构化信息的关键是 从同样类型的实例中发现编码模板 计算两个网页的结构相似度方法一 从HTML编码字符串检测重复模式 检测方法有 字符串编辑距离和树编辑距离 10 30 请参阅相关文献及编程资源 电子商务搜索引擎技术 HTML文件中提取文本 续 正文提取STEP 1 根据正文特征进行网页去噪正文详细页面的特征 文字较多 有明显段落 标点符号较多 URL较长 链接较少 计算节点的 链接文字比 节点下链接数 节点下文字数 删除 链接文字比 大于某个阈值的节点 STEP 2 网页链接中锚点文本 网页标题 与网页正文关系分析STEP 3 自动模板 11 30 电子商务搜索引擎技术 搜索引擎的关键技术中文分词两类方法 机械匹配法 和 统计法 机械法 最大匹配法利用正向或反向或双向最大匹配的方法来分词 借助标准的词典搜索词典统计法 最大概率分词法一个待切分的汉字串可能包含多种分词结果将其中概率最大的那个作为该字符串的分词结果 12 30 电子商务搜索引擎技术 中文分词机械法 最大匹配法 13 30 例 东北京西 匹配算法数字搜索树Trie 三叉搜索树 电子商务搜索引擎技术 数字搜索树 14 30 例 东北京西 搜索最大高度是词典中最长词的长度 每个节点都需要消耗很多内存 电子商务搜索引擎技术 Trie树Trie树 又称字典树 单词查找树 它来源于retrieval 检索 中取中间四个字符构成 用于存储大量的字符串以便支持快速模式匹配 主要应用在信息检索领域 15 30 电子商务搜索引擎技术 Trie树 16 30 标准Trie树的结构 所有含有公共前缀的字符串将挂在树中同一个结点下 实际上trie简明的存储了存在于串集合中的所有公共前缀 假如有这样一个字符串集合X bear bell bid bull buy sell stock stop 它的标准Trie树如下图 电子商务搜索引擎技术 标准Trie树的查找对于英文单词的查找 我们完全可以在内部结点中建立26个元素组成的指针数组 查找过程 假如我们要在上面那棵Trie中查找字符串bull b u l l 1 在root结点中查找第 b a 1 号子指针 发现该指针不为空 则定位到第1号子结点处 b结点 2 在b结点中查找第 u a 20 号子指针 发现该指针不为空 则定位到第20号子结点处 u结点 3 一直查找到叶子结点出现特殊字符 位置 表示找到了bull字符串如果在查找过程中终止于内部结点 则表示没有找到待查找字符串 17 30 电子商务搜索引擎技术 中文词语的标准Trie树由于中文的字远比英文的26个字母多的多 因此对于trie树的内部结点 不可能用一个26的数组来存储指针 如果每个结点都开辟几万个中国字的指针空间 不仅内存消耗过大 就连磁盘也消耗很大 一般可以采取这样种措施 1 以词语中相同的第一个字为根组成一棵树 这样的话 一个中文词汇的集合就可以构成一片Trie森林 这篇森林都存储在磁盘上 森林的root中的字和root所在磁盘的位置都记录在一张以Unicode码值排序的有序字表中 字表可以存放在内存里 2 内部结点的指针用可变长数组存储 18 30 电子商务搜索引擎技术 中文词语的标准Trie树特点 由于中文词语很少操作4个字的 因此Trie树的高度不长 查找的时间主要耗费在内部结点指针的查找 将指向字的指针按照字的Unicode码值排序 然后加载进内存以后通过二分查找能够提高效率 19 30 电子商务搜索引擎技术 中文词语的标准Trie树标准Trie树的应用和优缺点 1 全字匹配 确定待查字串是否与集合的一个单词完全匹配 2 前缀匹配 查找集合中以匹配字为前缀的所有串 20 30 电子商务搜索引擎技术 搜索引擎的关键技术中文分词两类方法 机械匹配法 和 统计法 机械法 最大匹配法统计法 最大概率分词法一个待切分的汉字串可能包含多种分词结果将其中概率最大的那个作为该字符串的分词结果 21 30 电子商务搜索引擎技术 搜索引擎的关键技术中文分词统计法 最大概率分词法 22 30 1 有 意见 分歧 2 有意 见 分歧 电子商务搜索引擎技术 搜索引擎的关键技术中文分词统计法 最大概率分词法 23 30 W1 有 意见 分歧 W2 有意 见 分歧 S 有意见分歧 分别计算 P W1 S 和P W2 S 电子商务搜索引擎技术 搜索引擎的关键技术中文分词统计法 最大概率分词法 24 30 要计算P W1 S 和P W2 S 先计算 P W S 假设 每个词之间的概率是上下文无关的 则 电子商务搜索引擎技术 搜索引擎的关键技术中文分词统计法 最大概率分词法 25 30 电子商务搜索引擎技术 搜索引擎的关键技术中文分词统计法 最大概率分词法 26 30 表 词语概率表 可得 P W1 P W2 电子商务搜索引擎技术 中文分词问题 比较计算出词与词之间组合的概率差异后 对于一个待分词的词串 如何尽快找到最佳的分词路径呢 27 30 最佳 概率最大 分词路径 左邻词 对字串从左到右进行扫描 可以得到W1 W2 Wi 1 Wi Wn 等若干候选词 如果Wi 1的尾字与Wi的首字邻接 就称Wi 1为Wi的左邻词 最佳左邻词 如果某个候选词Wi有若干个左邻词Wj Wk 等 其中累计概率最大的候选词称为Wi的最佳左邻词 电子商务搜索引擎技术 中文分词问题 根据以上数学原理 如何开发一个最大概率分词算法呢 28 30 最大概率分词算法描述STEP 1 对一个待分词的字串S 按照从左到右的顺序取出全部候选词W1 W2 Wi Wn STEP 2 到词典中查出每个候选词的概率值P Wi 并记录候选词的全部左邻词 STEP 3 按照计算每个候选词的累积概率 同时比较得到每个候选词的最佳左邻