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

1/30电子商务张文新副教授电话mail:zhangwx@电子商务-A-第08讲-补充共30页，您现在浏览的是第1页!课程安排讲授（36学时，共17讲）第1讲:绪论第10讲:电子商务物流规划技术第2讲:电子商务的概念与结构第11讲:物流信息系统集成技术第3讲:电子商务战略第12讲:物流配送优化调度技术第4讲:电子商务系统设计第13讲:电子商务资金流第5讲:电子商务网站设计第14讲:电子支付技术第6讲:电子商务交易流程第15讲:电子支付平台工具第7讲:电子商务商品展示技术第16讲:电子支付安全技术第8讲:电子商务搜索引擎技术第17讲:电子商务法律法规第9讲:电子商务商品推荐技术考试：最后一次课

2/30电子商务-A-第08讲-补充共30页，您现在浏览的是第2页!3/30第8讲电子商务搜索引擎技术电子商务-A-第08讲-补充共30页，您现在浏览的是第3页!电子商务搜索引擎技术网络蜘蛛（Spider,Robot,Crawler）对URL链接进行遍历基本数据结构一个待扩展的URL表一个已经访问过的URL地址表4/30TODO表Visited表初始URL地址解析URL新解析出的URL图：网络蜘蛛基本数据结构图电子商务-A-第08讲-补充共30页，您现在浏览的是第4页!电子商务搜索引擎技术搜索引擎的关键技术提取文档中的文本内容（网页结构化信息抽取）HTML文件中提取文本识别网页的编码STEP-1:从Web服务器返回的contenttype中提取编码；STEP-2:从网页的Meta信息中识别字符编码；STEP-3:从返回流的二进制格式判断，确定网页语言。对HTML文件进行解析（识别三类节点）RemarkNode（注释）TagNode（标签）TextNode（文本）5/30电子商务-A-第08讲-补充共30页，您现在浏览的是第5页!电子商务搜索引擎技术DOM树6/30<Bodybgcolor=WHITE><Tablewidth=800height=200></Table><IMGsrc=“image.gif”width=800><Tablebgcolor=RED>

······</Table></Body>BODYTableIMGTableBODYbgcolor=WHITEwidth=800width=800图：DOM树电子商务-A-第08讲-补充共30页，您现在浏览的是第6页!电子商务搜索引擎技术HTML文件中提取文本（续）正文提取STEP-1:根据正文特征进行网页去噪正文详细页面的特征：文字较多，有明显段落，标点符号较多，URL较长，链接较少；计算节点的“链接文字比”=“节点下链接数”/“节点下文字数”删除“链接文字比”大于某个阈值的节点；STEP-2:网页链接中锚点文本（网页标题）与网页正文关系分析STEP-3:自动模板7/30电子商务-A-第08讲-补充共30页，您现在浏览的是第7页!电子商务搜索引擎技术中文分词机械法：最大匹配法8/30例：“东北京西”匹配算法数字搜索树Trie(三叉搜索树)电子商务-A-第08讲-补充共30页，您现在浏览的是第8页!电子商务搜索引擎技术Trie树Trie树，又称字典树，单词查找树。它来源于retrieval（检索）中取中间四个字符构成；用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。9/30电子商务-A-第08讲-补充共30页，您现在浏览的是第9页!电子商务搜索引擎技术标准Trie树的查找对于英文单词的查找，我们完全可以在内部结点中建立26个元素组成的指针数组。查找过程：假如我们要在上面那棵Trie中查找字符串bull(b-u-l-l)。

(1)在root结点中查找第('b'-'a'=1)号子指针，发现该指针不为空，则定位到第1号子结点处——b结点。

(2)在b结点中查找第('u'-'a'=20)号子指针，发现该指针不为空，则定位到第20号子结点处——u结点。

(3)...一直查找到叶子结点出现特殊字符'$'位置，表示找到了bull字符串如果在查找过程中终止于内部结点，则表示没有找到待查找字符串。

10/30电子商务-A-第08讲-补充共30页，您现在浏览的是第10页!电子商务搜索引擎技术中文词语的标准Trie树特点：由于中文词语很少操作4个字的，因此Trie树的高度不长。查找的时间主要耗费在内部结点指针的查找。将指向字的指针按照字的Unicode码值排序，然后加载进内存以后通过二分查找能够提高效率。11/30电子商务-A-第08讲-补充共30页，您现在浏览的是第11页!电子商务搜索引擎技术搜索引擎的关键技术中文分词两类方法：“机械匹配法”和“统计法”机械法：最大匹配法统计法：最大概率分词法一个待切分的汉字串可能包含多种分词结果将其中概率最大的那个作为该字符串的分词结果12/30电子商务-A-第08讲-补充共30页，您现在浏览的是第12页!电子商务搜索引擎技术搜索引擎的关键技术中文分词统计法：最大概率分词法13/30有意见分岐W1:有/意见/分歧W2:有意/见/分歧S:有意见分歧分别计算：P(W1∣S)和P(W2∣S)电子商务-A-第08讲-补充共30页，您现在浏览的是第13页!电子商务搜索引擎技术搜索引擎的关键技术中文分词统计法：最大概率分词法14/30有意见分岐P(W)=P(W1，W2,···，Wi)≈P(W1)×P(W2)×···×P(Wi)P(Wi)=Wi在语料库中出现的次数n语料库中的总词数N电子商务-A-第08讲-补充共30页，您现在浏览的是第14页!电子商务搜索引擎技术中文分词问题：比较计算出词与词之间组合的概率差异后，对于一个待分词的词串，如何尽快找到最佳的分词路径呢？15/30最佳（概率最大）分词路径“左邻词”：对字串从左到右进行扫描，可以得到W1,W2,…，Wi-1,Wi,…Wn；等若干候选词，如果Wi-1的尾字与Wi

的首字邻接，就称Wi-1为Wi

的左邻词。“最佳左邻词”：如果某个候选词Wi有若干个左邻词Wj,Wk,…等

，其中累计概率最大的候选词称为Wi的最佳左邻词。有意见分岐P’(Wi)=P’(Wi-1)×P(Wi)电子商务-A-第08讲-补充共30页，您现在浏览的是第15页!电子商务搜索引擎技术中文分词进一步深入探讨的问题：新词如何发现？词库如何补充？词性如何区分并标注？16/30电子商务-A-第08讲-补充共30页，您现在浏览的是第16页!电子商务搜索引擎技术搜索引擎的关键技术网络蜘蛛（Spider,Robot,Crawler）网页结构化信息抽取中文分词搜索结果排序17/30电子商务-A-第08讲-补充共30页，您现在浏览的是第17页!电子商务搜索引擎技术网络蜘蛛（Spider,Robot,Crawler）遍历URL地址遍历的策略广度优先深度优先18/30ABCDGEFHIA→B,C,D,E,F→H,G→IA→F→GE→H→I······电子商务-A-第08讲-补充共30页，您现在浏览的是第18页!电子商务搜索引擎技术提取文档中的文本内容（网页结构化信息抽取）HTML文件中提取文本（续）结构化信息提取DOM（文档对象模型）结构HTML扫描器例如：<imgwidth=“”;height=“”;src=“123.jpg”>Node.getAttributes().getNamedItem(“src”)参考NekoHTML（/）网页去噪网页结构相似度计算19/30电子商务-A-第08讲-补充共30页，您现在浏览的是第19页!电子商务搜索引擎技术提取文档中的文本内容（网页结构化信息抽取）HTML文件中提取文本（续）网页结构相似度计算自动提取结构化信息的关键是：“从同样类型的实例中发现编码模板”。计算两个网页的结构相似度方法一：从HTML编码字符串检测重复模式，检测方法有：字符串编辑距离和树编辑距离20/30请参阅相关文献及编程资源电子商务-A-第08讲-补充共30页，您现在浏览的是第20页!电子商务搜索引擎技术搜索引擎的关键技术中文分词两类方法：“机械匹配法”和“统计法”机械法：最大匹配法利用正向或反向或双向最大匹配的方法来分词；借助标准的词典搜索词典统计法：最大概率分词法一个待切分的汉字串可能包含多种分词结果将其中概率最大的那个作为该字符串的分词结果21/30电子商务-A-第08讲-补充共30页，您现在浏览的是第21页!电子商务搜索引擎技术数字搜索树22/30例：“东北京西”搜索最大高度是词典中最长词的长度；每个节点都需要消耗很多内存；东西方北红京盟西电子商务-A-第08讲-补充共30页，您现在浏览的是第22页!电子商务搜索引擎技术Trie树23/30标准Trie树的结构：所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了存在于串集合中的所有公共前缀。假如有这样一个字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的标准Trie树如下图：电子商务-A-第08讲-补充共30页，您现在浏览的是第23页!电子商务搜索引擎技术中文词语的标准Trie树由于中文的字远比英文的26个字母多的多。因此对于trie树的内部结点，不可能用一个26的数组来存储指针。如果每个结点都开辟几万个中国字的指针空间。不仅内存消耗过大，就连磁盘也消耗很大。一般可以采取这样种措施：(1)以词语中相同的个字为根组成一棵树。这样的话，一个中文词汇的集合就可以构成一片Trie森林。这篇森林都存储在磁盘上。森林的root中的字和root所在磁盘的位置都记录在一张以Unicode码值排序的有序字表中。字表可以存放在内存里。

(2)内部结点的指针用可变长数组存储。

24/30电子商务-A-第08讲-补充共30页，您现在浏览的是第24页!电子商务搜索引擎技术中文词语的标准Trie树标准Trie树的应用和优缺点(1)全字匹配：确定待查字串是否与集合的一个单词完全匹配。(2)前缀匹配：查找集合中以匹配字为前缀的所有串。25/30电子商务-A-第08讲-补充共30页，您现在浏览的是第25页!电子商务搜索引擎技术搜索引擎的关键技术中文分词统计法：最大概率分词法26/30有意见分岐（1）有/意见/分歧（2）有意/见/分歧电子商务-A-第08讲-补充共30页，您现在浏览的是第26页!电子商务搜索引擎技术搜索引擎的关键技术中文分词统计法：最大概率分词法27/30有意见分岐要计算P(W1∣S)和P(W2∣S)，先计算：P(W∣S)P(W∣S)=P(S∣W)×P(W)P(S)假设：每个词之间的概率是上下文无关的，则：≈P(W)P(W∣S)=P(S∣W)×P(W)P(S)电子商务-A-第08讲-补充共30页，您现在浏览的是第27页!电子商务搜索引擎技术搜索引擎的关键技术中文分词统计法：最大概率分词法28/30有意见分岐表：词语概率表词语概率······有0.0180有意0.0005意见0.0010见0.0002分歧0.0001······P(W1)=P(有)×P(意见)