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

1/30,电 子 商 务,张文新 副教授,电话Email: ,课 程 安 排,2/30,3/30,第8讲,电子商务搜索引擎技术,电子商务搜索引擎技术,搜索引擎的关键技术 网络蜘蛛（Spider,Robot,Crawler） 网页结构化信息抽取 中文分词 搜索结果排序,4/30,电子商务搜索引擎技术,网络蜘蛛（Spider,Robot,Crawler） 对URL链接进行遍历 基本数据结构 一个待扩展的URL表 一个已经访问过的URL地址表,5/30,图：网络蜘蛛基本数据结构图,电子商务搜索引擎技术,网络蜘蛛（Spider,Robot,Crawler） 遍历URL地址 遍历的策略 广度优先 深度优先,6/30,AB,C,D,E,F H,G I,AF G E H I ,电子商务搜索引擎技术,搜索引擎的关键技术 提取文档中的文本内容（网页结构化信息抽取） HTML文件中提取文本 识别网页的编码 STEP-1:从Web服务器返回的content type中提取编码； 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简明的存储了存在于串集合中的所有公共前缀。 假如有这样一个字符串集合Xbear,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(W1S)和P(W2S),电子商务搜索引擎技术,搜索引擎的关键技术 中文分词 统计法：最大概率分词法,24/30,要计算P(W1S)和P(W2S)，先计算： P(WS),假设：每个词之间的概率是上下文无关的，则：,电子商务搜索引擎技术,搜索引擎的关键技术 中文分词 统计法：最大概率分词法,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:按照 计算每个候选词的累积概率，同时比较得到每个候选词的最佳