n版本 0.9
n采用了 OPIC算法来实现
目前网络上的排序算法都是依托图论来实现对整个互联网页面的排序,起基本的思想有以下几点:将互联网表示为一个图G,用矩阵L来描述,其中L非负,如果在L中的两点(i,j)存在链接,那么L|(i,j)|>0,google直接认为如果存在链接,那么d(i,j)=外链的倒数。
剩下的就是一堆md所谓的数学推导,其实基本上离不开d(i,j)这个鸟概念,对于函数实现主要就是搞搞d(ij)
n 中的 OPIC算法主要就是基于d(i,j)这个概念出发,构建了L矩阵,将整个爬到的网页分为n个节点,每个节点分配一个cash值一个history值,cash值在初始分配的时候被n设置为1,然后在抓取到了网页之后,score=history = sum(links[i].cash),即修改history值为所有其他外链的cash值之和,修改之后,将外链的cash值置为当前score/validLinkNumber,即将其本身的cash再分配给其他的网页,不过原论文里面在这里会将当前页面cash值置零,而n并没有,nutch用了一个score同时充当了history和cash,这样搞下去好像有点诡异,因为在爬行中cash的总数会增多,估了一下大概是2倍的增量关系,增量就会传递错误,但是如果确保爬行的次数和完整性,后面的增加的网页又会将错误降低。就opic算法而言,其最终目的是证明在无限次爬行和等概率redirect情况下,网页的重要性大致等于history除以所有网页的history之和,在nutch中,只要保证被爬行的次数的增多话,其score一定是向上提高的,而且越多次迭代之后,其在整个拓扑中的排序应该是可靠的(只是一种直觉哈,我也给不出完备的数学证明),反正就是一个针对链接的算法。看了nutch的实现,发现工程和论文还是有差别的,一般论文都是数学上异常复杂吹牛逼吹的很圆,而我们如果自己实现论文算法,特别是某些领域,编程时候拍拍脑袋,方向上和论文一致就可以了,很复杂的算法也许可以简单实现,效果也不一定差啊(也没见谁去抱怨怀疑nutch,不过nutch排序算法实现程序确实没有人愿意署名倒是了:)),继续日之~。
贴段代码,这个实现的确很简单,opic算法可以去查看http://www2003.org/cdrom/papers/refereed/p007/p7-abiteboul.html
float adjust = 0.0f;
for (int i = 0; i < inlinked.size(); i++) {
CrawlDatum linked = (CrawlDatum)inlinked.get(i);
adjust += linked.getScore();
}
if (old == null) old = datum;
datum.setScore(old.getScore() + adjust);
分享到:
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...