如今同页排名算法很多，基本上可以分为两类：基于超链接和基于内容。比较成熟的算法主要有、等。
　　本文基于向量空问模型以及信息论，提出一个与文章内容相关的语义相关度算法模型。该模型将文章语义抽象为词频表，并通过机器学习构建词语之间的关联度表，以此词关联度为基础，计算文章之间的相关度。实验结果表明，文中提出的相关度算法可以有效的根据文章之间语义相关度大小来进行排名。关键词：词关联度，语义，相关度，向量模型，信息量，概率模型中图法分类号：3文献标志码：0引言网页排名是搜索中非常重要的一环。现今社会发展的一个重要方面就是信息技术的突匕猛进，伴随而来的是信息容量的爆炸式发展。信息的种类也是纷繁复杂，书籍、论文、博客、论坛等各种应用极大的丰富了现代人的生活。然而，日益成为一个非常有价值的研究问题是，如何高效获取这些有价值的、符合我们需要的信息。解开这个纷繁头绪的，便是搜索引擎，它为我们提供了获取信息的接入点。搜索引擎收集网页的信息，建立索引库，在用户输入查询的关键词时，返回与关键词相关的信息。返回的信息如何能够更好的反映用户的需求，这就涉及到网页排名的问题。现在对网页排名的算法有很多的研究，例如、等等。总的来说，网页排名算法可以分为两类：基于内容和非基于内容的，这两者的主要区别是排名是否能反映网页文章的语义内容。、是根据超链接来排名的，与内容无关；则是对文章内容进行变换，对文章进行空间坐标建模，可以反映文章的内容信息，但是进行变换需要巨大的计算量和计算资源。目前讨论的比较热门的还有语义网，基本思想是建立一个基于内容的、可供机器识别的语义体系：本体。在这个体系中，内容被划分为不同的概念类别，从而确定文章的语义属性。如今比较成熟的本体主要有、知网等。这种模型有一个缺点就是必须人工建立一个本体架构。本文提出一种机器学习的、基于内容的相关度计算方法，据此相关度大小对文章进行排序，其结果可以很好的反映文章的语义内容。1研究的背景网页排序处于搜索引擎的最后处理阶段，通过排名算法将查询得到的信息评分，按照评分结果对其进行排序返回给查询者。是由斯坦福大学的两位教授和提出的，是网页排名的核心算法，其基本的理念是一篇文章被引用的次数越多则表示该文章的关注度越高，排名越靠前。该算法将页面抽象为一个有向图，每篇文章为一个节点，假如有篇文章，则节点数为。文章之间的引用关系构成该有向图的邻接矩阵。节点的所有超链接文章的综总和即为其出度，从节点到节点的概率为1，设第步在的概率为[1，则第+步在节点概率为：¨1+-(，)∈三砉上!』公式～(1)因为节点数有限，从一个节点到另一个节点最多经过个链接，因此迭代一定次数后邻接矩阵就不会再变化或者变成周期变化的，算法此时收敛。该算法的特点是在查询之前就已根据超链接关系算好每个页面的评分，对返回结果进行的排序很快。另外一个基于超链接的算法是。与算法不一样的是，与查询请求有关。与将所有文章作为一个矩阵不同，首先选取与查询请求有关的文章作为一个根集合，再将和根集合中的文章有超链接关系的文章作为扩展集，这样大大减少了计算关注度的矩阵大小。并且还考虑了入度，即被其他文章链接，同时在两个方向上进行关注度计算，并且同时在两个方向上收敛，将两个方向的迭代结果作为关注度。与以上两种算法不同的是，则是完全依据文章内容来计算文章排名的。
　　首先构造一个关键词．文章的矩阵，然后进行分解得到三个矩阵、：=。其中是一个稀疏的对角矩阵，、均为单位阵。这样就把原先的矩阵空间转换成一个相对较小的空间，每篇文章、查询请求均映射到这个空间的一个位置上，然后计算空间距离得到查询请求和文章之间的相关度大小。然而，是一个十分耗时的过程，为此做了很多近似处理。
　　作者简介：张增杰(1984-)，男，河北武安人，硕士，研究方向为语义搜索系统，上海市200433李晓成，男，山西大同人。硕士。研究方向为流媒体算法，上海市200433刘鑫。男。湖北荆州人，硕士，研究方向为语义搜索系统。七海市200433夏勇明：复旦大学通信科学与工程系。实验师。上海．200433钱松荣．男，复旦大学信息科学与工程学院，教授．研究方向为高级网络通信、，上海市,200433?45?'27，．3，2011开发应用截型电脑应用2011年第27卷第3期可以看出，算法考虑了文章本身的一个重要信息：关键词，而不是和文章内容无关系的超链接。在关键词一文章矩阵中，包含了两个重要的统计信息：文章中的词频(列向量)、词语在整个文章库中分布情况(行向量)。这两个统计信息构成了一个向量空间，给了机器分析文章语意的线索。现在反映文章潜在语义最丰要的算法便是向量空间模型。在空间向昔模型中，文章映射到多维欧几里德窄间中，每一维关联到一个关键词。每一维的坐标值由关键词的两个属性决定：词频和反向文章词频，表示为1。即为词语在文章中出现的次数，记为，可以归一化为：公式2(,)=-(，．位吣(2)表示与该词在整个文章库中出现的总次数相比，在文章中出现的概率。反映了一个词在文章库中权重，表示为：=，表示整个文章库，表示包含这个词的文章的集合。从此定义可以看出，在?体系中，认为一个词出现的次数越少，其重要性也就越高。这从一个方面反映了词语的重要性，一些虚词如“的”出现的次数很多，但它对文章的语义贡献不大。本文提出了一种变维的空间向模型，并且在计算距离时，提出了一种根据词语相关度计算文章相关度的算法，而不是简单的计算关键词出现频率的差值。2词关联度的挖掘在语义网中，手工构造了一个本体体系。该体系可以看成是一本包含明确知识概念划分的字典，词语按照自己的语义语境组织起来。
　　在应用中，则可查询这个词典，获得和查询关键词相近的词语，以及其相近程度。但是，手工建立这样一个字典是一个庞大的工程。在信息论中有互信息量的概念：，表示接收机收到信号以后，对收到提供的信息量，即由推导的概率的量化。本文以此为基础，结合．算法，提出一种可以由机器自动学习的词语关联网：词关联表，通过这个表，我们可以查询在文章库中出现的关键词之间的关联程度。对于关键词和，我们记他们各自的词频为，)。其中：公式3=(3)表示在每篇文章中的次数，则是关键词在整个文章库中出现的次数的总和。同时，我们记后验概率：公式4=(4)表示在出现关键词的文章中出现的概率。
　　其中：公式5=回(5)即在出现的文章中出现的次数的总和。
　　越大，表示在出现的文章中，出现的概率越大。我们没有采用(，Ⅵ，即和同时出现的概率，是因为在一篇文章中和出现的次数往往是不同的，即')。我们如果只用和同时出现的文章在整个文章库中概率来计算(，)，则没有考虑和在每篇文章中出现的次数，统计信息不足以反映文章的具体内容。另外，由关键词推导关键词以及由关键词推导关键词的概率往往是不同的，例如推导的概率要大于推导的概率。因此，偏概率比较符合文章中关键词之间的关系。由概率的差异我们已经可以得到词语之间关系的比较，为计算方便，我们就没有再去计算，只以作为我们的统计结果。在词关联度表中，包含文章库中所有出现的关键词之间的偏概率，通过查询词关联度表，即可得到。统计词关联度表的程序流程为：①初始化文章库，取出第一篇文章②对文章进行分词，统计词频，去除无用之词③对于每一个关键词组合进行两步处理：如果词关联表中已存在这一对关键词，则更新每个词的频率，否则插入这一对关键词④如果遍历到文章库中最后一篇文章则结束，否则取出下一篇文章，转到第2关于传奇步?46?3相关度的算法本文的相关度算法基于向量空间，每篇文章由向量表示，并提出了两种计算文章相关度的算法：直接法和扩展法。3．1文章的向量空间文章的语义向景表示为：公式6=-，=，2(6)为文章中关键词出现的频率，即为文章的词频表，表示文章中第个词的词频。一篇文章中包含很多的虚词，如“的”、“了”等，这些词可以看成是没用的词。除去这些虚词，出现次数最多的一组词摹本上可以表达出文章的语义。将文章中的关键词按照频率从大到小排列，并去除虚词，得到精简的词频表：=-[，=，23．2相关度的算法本文提出了两种计算相关度的算法：直接法和扩展法。首先，一个关键词与文章之间的相关度表示为：公式7(，)=。
　　(6)为关键词，文章的词频表，谢为中的第个词频。
　　以公式(7)为基础，本文第一种计算文章之间关联度的算法：直接法，表示为：(，2)=戳斗酝溉啼甄魄融曲=戳(，砭)(7)即1中每个词与2的相关度的加权和，其复杂度为(2)。在一般的计算向量宅间距离的基础卜，本文提出第二种算法：扩展法。与传统的向量空问不同的是，本文的语义向27，03'2011开发应用囊型电脑应甩2011年第27卷第3期量只取出现次数最多的一组词，因此向量长度大大减少。虽然每篇文章精简后的词频表取的长度是一样的，但是每篇文章关键词不一样。应用词关联度表，我们可以由已有的关键词推导出在其他文章中出现而在本篇文热血传奇游戏章中未出现的关键词的概率，这样就可以使两篇文章的词频表具有相同的关键词和维度，即可进行向量空间距离的计算，但是由于词频表很短，可以比传统的向量模型节省更多的空间和时间。假设原来词频表为，扩展出关键词的概率为：词频表扩展的流程为：①给定两个词频表，2．②分别找出两个词频表的差集，③根据公式(9)，由吁展1得到。，毛扩展2得到《。
　　因为在扩展过程中文章的语义向量的长度扩展了，可以看成是一种变维操作其复杂度也为(2)。经过扩展，我们得到维度和关键词都相同的词频表残、砭，则其相关度为(。，)暑弧靓(土?吐(9)4实验结果4．1实验的设计本文实验的文章库共有50篇体育类的文章，有关的五支队伍的新闻，每个队各有篇文章。这些文章中，每篇都有自己的主题，但是不可避免的要牵涉到其他队的一些内容，如球员、球队状态等等。如果我们用关键词搜的话，如搜“詹姆斯”，可能就会搜出火箭队的新闻。这样选择的文章库可以很好的检验相关度算法的区分能力，即把具有相同关键词，但内容语义关系不大的文章区分开。实验主要分为两部分，首先是直接法计算关键词与文章之间的相关度，其次是分别用扩展法和直接法计算文章之间的距离，并加以比较。4．2实验结果对于实验结果，我们只列举出相关度排名在前五位的文章的标题以及相关度分值。关键词和文章之间的相关度：关键词为“詹姆斯”，其与文章库中的文章最相近的5篇为表1所示。?47?擞天埘?交翠之刖的辅天厦文尊相碰詹姆斯早三决定离队乍炬战骑：在幼难遘0．967332壑静剃竞始：勺『幽2需要的究琵什么0．9311762老扳翻怼帅卉耐嬲任一揣离队”臌性，蹭喊0．9135013传帝右时韧带撕裂他奉一提六剜事后0．8366194孵姆斯恐缺惭锦赛奥皑尔仃镬提复：0．8330835嬲跳Ⅱ：俐甜狄妙圆删煳0．403813表格最后一篇文章是有关火箭队的新闻，但是关键词里面有“詹姆斯”，可以看到其排名很低，可见本文的相关度算法有很好的区分度。文章与文章之间距离：基准文章为莫雷竞成姚明伤病推手火箭是在挥霍巨人青春》，采用直接法和扩展法计算相关度，其与文章库中的文章最相近的5篇文章分别如表2、表3所示。爱娌接法文章相天度楚0毫嘘媲明协嘀推火蒲芷棒霍?人菏稃，鬯比渡虫适合火蓊哇三技联姨吲|到艘犍州跳：台叫蹬，久，人恐成换渡仆：、¨球述沦|足绱夸疆如何刖中，以愉鬯纠伦-：乏圯捧火葫确定小筝扭乐透摇畸盼抽个娩晖．7：70．152840．：懈93．1017．36053挺扩胜法文章相父度"廷前凫睡魄咧=锅推火蒲芷：打霍!人厅稃火薪=怂念抽劁|畸笸鹃叻誉也缱收捩强援火蒲勾换．泼仆或禽?小如链剐小“姥拿州突舭擞。
　　扎求：；誉伊火籀敏为媾珥拽内线隋火薪确定小南参扭|乐透摇盼抽?卜个网民认为这样对的姚嘲．287162．=169522．3757120．41772两种算法结果的形式稍有不同，直接法计算的是相近程度，分值越大排名越高；扩展法计算的是距离，分值越小排名越高。
　　从结果可以看出，两种算法都能从50篇不同的文章中找出和火箭队选秀在语义上相近的文章。5分析与总结通过分析排序的结果，我们可以看到，通过词关联表、词频向量以及相关度的算法，不需要借助任何附加的资源，如引用、链接等，即可以得到比较准确的关键词和文章之间以及文章之间的语义相关度。影响算法效果的主要有两个因素：一个是词频表，另一个是分词能力。
　　可以通过完善词频表和提升对文章分词能力这两个方面来改进本文的算法。首先，由于是实验性质，(下转第51页)27,．3。
　　2011开发应用微型电脑应用2011年第27卷第3期复网页数大于文献4中重复网页数的情况下，使用处理的运行时长和需要的存储空间都有了明显的下降。这也证明了此方法的优越性。在实验的三组数据中，第一组网页来源于同一个网站的房屋出售租赁信息，第二组是来源于两个网站的，第三组则是来源于三个网站的房屋出售租赁信息。通过分析，我们可以看到第三组应该存在更多的重复网页，这是因为在不同网站页面间重复发布一样的房屋出售租赁信息的叮能性更大。
　　接下来我们可以分析一下3组数据的运行时间，所谓运行时间是指网页去重过程的运行时间，它不包括网页去杂过程所运行的时间。我们令3组数据的玩家优惠有效网页数目分别为“，2和传，三组数据的运行时间分别为，23通过观察我们可以得到：堕；生堕192岛(12)由此可以得出网页去重的所需时间和网页数目间有着几乎线性的关系。最后分析一下对于存储空间的优化。其中“原始存储空间”是指存储原始的文件所需的空间大小，“存储空间”是指存储所需的空间大小。我们可以计算出这3组实验中的网页的平均大小分别为：3，10和15。采用存储空间大大减少，3组实验中存储空间为1．38。2．69，8．61。这些仅仅占原始存储空间的0．04145％，0．01248％和0．00821％。
　　因为在我们的实验中，所需的存储空间只和网页的数量成正比，所以对于平均网页大小越大的组(第3组)，越是能节省空间。4结论通过实验我们可以看到，利用可以高效地找出数据库巾重复的网页，并且相对于红黑树算法来说，运行速度有了很大的提高，需要的存储空间也大大的减少。这些性能的提高可以使大量的计算工作在内存中完成，提高了算法的高效性。另外也可以充分的应用到搜索引擎网页过滤等方面，为实现更多互联网的应用发展提供帮助和支持。参考文献．1．．：6．：．。1997：393?404．2．．阴．,1970，13(7)：422?426．[31．叨．，2004，(4)：485-509．4刘四维，章轶，夏勇明，钱松荣．基于标记和长句提取的网页去重算法．上海：微型电脑与应用，2009，25(8)：30-32．5王小华，卢小康．基于-的文本去重方法研究叨．杭州：杭州电子科技大学学报，2010，30(2)：61-64．6丁振国，吴宝贵，辛友强．基于的大规膜网页去重策略研究川．北京：现代图书情报技术，2008，24(3)：45?50．(收稿日期：2010-10-08)婷谬谬浔守浔守浔守谬一寻一碍浔婷守浔守移寻一寻移一寻移谚一移碍谚涝谤谚谬磅(上接第47页)文章取得比较少，词语之间的潜在关系挖掘的不够，可以通过训练大量的类别分明的文章来获得更精确的词关联度。其次，对文章分词是一个非常基础的步骤，有一些科技名词、人名、地名等等特殊词的辨别还有待提升，分词好了就能得到更精炼、准确的词频向量。参考文献参考文献1，．：[]．2003．2，．：[]．：．．一．．1998．?5?3,．：，．[]．2009．4：，,．：画．．20085,．．．[]．1990．6,，,，．，,：，．2006．(收稿日期：2010-05-24)基于词关联度的语义相关度算法研究作者：张增杰，李晓城，刘鑫，夏勇明，钱松荣，作者单位：张增杰,刘鑫,钱松荣,,,,,(复旦大学通信科学与工程系,上海,200433)，李晓城,夏勇明(复旦大学信息科学与工程学院,上海市,200433)刊名：微型电脑应用英文刊名：年，卷(期)：2011,27(3)。