搜索引擎算法研究
搜索引擎算法研究
１．引言
万维网WWW（World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。1998年WWW上拥有约3.5亿个文档[14]，每天增加约1百万的文档[6]，不到9个月的时间文档总数就会翻一番[14]。WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。
传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观性强，费用高，更新速度慢[2]。
最近几年，许多研究者发现，WWW上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1] ，同年J. Kleinberg提出了HITS算法[5]，其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。
文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。第3部分对这些算法做了评价和总结，指出了存在的问题和改进方向。
椭圆曲线密码算法介绍
1，有限域上的椭圆曲线
设K表示一个有限域，E是域K上的椭圆曲线，则E是一个点的集合：
E/K = { ( x, y ) | y2+ a1xy + a3y = x3 + a2x2 + a4x + a6,
a1, a3, a2, a4, a6 x, y K } { O }
其中O表示无穷远点。
在E上定义‘+’运算，P + Q = R，R是过P、Q的直线与曲线的另一交点关于x轴的对称点，当P = Q时R是P点的切线与曲线的另一交点关于 x轴的对称点。这样，( E, + )构成可换群( Abel群)，O是加法单位元(零元)。椭圆曲线离散对数问题ECDLP定义如下：给定定义在K上的 椭圆曲线E，一个n阶的点P E/K，和点Q E/ K，如果存在l，确定整数l, 0 l n - 1, Q = lP。前面已经提到，ECDLP是比 因子分解难得多的问题。
椭圆曲线上的加法: P + Q = R
椭圆曲线上一点的2倍: P + P = R.
2，椭圆曲线上的密码算法
基于该难题，Neal Koblitz[13] 和Victor Miller[14]在1985年分别利用有限域上椭圆曲线的点构成的群实现了离散对 数密码算法，其中被广泛接受的是椭圆曲线上的DSA，称ECDSA。随即展开了椭圆曲线密码学研究，除椭圆曲线外，还有人提出在其它类型的曲线如超椭圆曲 线上实现公钥密码算法。
此后，有人在椭圆曲线上实现了类似ElGamal的加密算法，以及可恢复明文的数字签名方案。除有限域上的椭圆曲线密码算法外，人们还探索了在椭圆曲线上实现RSA算法，如KMOV等，笔者也设计了一种算法(“一种基于Z/nZ上椭圆曲线的公钥密码算法”，王汉强、魏庆福，通信学报，1999，第7期)。
3，椭圆曲线密码算法的发展
由于其自身优点，椭圆曲线密码学一出现便受到关注。现在密码学界普遍认为它将替代RSA成为通用的公钥密码算法，SET ( Secure Electronic Transactions )协议的制定者已把它作为下一代SET协议中缺省的公钥密码算法，目前已成为研究的 热点，是很有前途的研究方向。
产生素数的算法
Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数：（1） 选择一个小于p的随机数a。
（2） 如果 gcd(a,p) <> 1，那么 p 通不过测试，它是合数。
（3） 计算j=a^(p-1)/2 mod p。
（4） 计算雅可比符号J（a,p）。
（5） 如果j<>J（a,p），那么p肯定不是素数。
（6） 如果j=J(a,p),那麽p不是素数的可能性值多是50%
数a被称为一个证据，如果a不能确定p，p肯定不是素数。如果p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值，重复t次这种测试。p通过所有t次测试后，它是合数的可能性不超过1/2^t。
Lehmann
另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法：
（1） 选择一个小于p的随机数a。
（2） 计算a^(p-1)/2 mod p
（3） 如果a^(p-1)/2<>1或-1（mod p），那么p肯定不是素数。
（4） 如果a^(p-1)/2=1或-1（mod p），那麽p不是素数的可能性值多是50%
同样，重复t次，那麽p可能是素数所冒的错误风险不超过1/2^t。
Rabin-Miller
这是个很容易且广泛使用的简单算法，它基于Gary Miller的部分象法，有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
（1） 选择一个小于p的随机数a。
（2） 设j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
（4） 如果j>0且z=1, 那麽p不是素数
（5） 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
（6） 如果j=b 且z<>p-1，不是素数
这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。
实际考虑：
在实际算法，产生素数是很快的。
（1） 产生一个n-位的随机数p
（2） 设高位和低位为1（设高位是为了保证位数，设低位是为了保证位奇数）
（3） 检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快
（4） 对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次 Rabin-Miller测试如果p在其中失败，从新产生p，再测试。
在Sparc II上实现： 2 .8秒产生一个256位的素数
24.0秒产生一个512位的素数
2分钟产生一个768位的素数
5.1分钟产生一个1024位的素数
一个非常简单的私有加密算法（java版）
public class ZYGEncrypt {
private static final byte[] enkeystore = {
0×08, 0×02, 0x0b, 0x0c, 0×01, 0x0a, 0×00, 0x0d, 0×07, 0×03, 0x0e,
0×05, 0x0f, 0×06, 0×04, 0×09
};
private static final byte[] dekeystore = {
0×06, 0×04, 0×01, 0×09, 0x0e, 0x0b, 0x0d, 0×08, 0×00, 0x0f, 0×05,
0×02, 0×03, 0×07, 0x0a, 0x0c
};
public static byte[] encode(byte[] data) {
byte[] result = new byte[data.length];
for (int i = 0; i < data.length; i++) {
result[i] += (enkeystore[(data[i] >>> 4) & 0x0F] << 4);
result[i] += (enkeystore[data[i] & 0x0F]);
}
return result;
}
public static byte[] decode(byte[] data) {
byte[] result = new byte[data.length];
for (int i = 0; i < data.length; i++) {
result[i] += (dekeystore[(data[i] >>> 4) & 0x0F] << 4);
result[i] += (dekeystore[data[i] & 0x0F]);
}
return result;
}
public static void main(String[] args) {
String data = “1″;
byte[] databyte = ZYGEncrypt.encode(data.getBytes());
byte[] resultdata = ZYGEncrypt.decode(databyte);
System.out.println(data);
System.out.println(new String(resultdata));
}
}
Google的搜索算法将做出重大改进
昨日，纽约时报的一篇关于Google的报道在新闻界引起了相当大的震撼，各家网站纷纷转载或者进行扩展评论。
Google正在不断改进它的搜索算法，这将是Yahoo和微软噩梦。过去，Google的搜索结果排名是注重网站的受欢迎程度，这对于大网站非常有利。 未来甚至现在已经开始，Google的搜索结果排名将更注重时效性，即如果你发布的新闻最早的话，尽管你的网站流量很小，但也会排在搜索结果的前面，这就 类似于Google News和Google blogsearch的搜索结果。
估值函数与优化搜索
前面说了最小最大原理，为什么要最小最大原理？为什么要搜索？我们可以更简单的看对弈这件事儿，下棋的时候，从一开始到结束，每当我要走棋时，我会考虑怎么走？有N种可行走法，但只能选一种，换个方式想这问题，人工智能不过是作一种‘选择’，而这里的‘选择’要能促使你最终赢棋！
可以选择的前提是要能分出谁高谁低，哪步着法臭，哪步着法妙，于是就需要要一个估值函数Eval(p),p是局面，也就是由这个评价函数分出哪个局面（或者着法，着法可以看成下一个局面）更好，如果Eval(p1)<Eval(p2)，我们就有理由说，或者大胆地说，p2比p1更好！但是很多时候，你并不能断言，你做的决定是最好的，这在于棋类游戏的复杂程度，像一些高深的棋类游戏，棋的变化非常多非常复杂，那你能完全相信你的估值函数吗？不能，有可能，现在看来一步很臭的棋，在不久的将来将会使局面变得很好，这就是妙手，这是经常出现的。出现这样情况的原因是，我们找到的估值函数都是从一个局面来看的，它是静止的，它看不到未来的变化，所以它是非常粗糙的。而搜索的目的正是为了‘更好的’评价棋局，可以把搜索看成是动态的估值！
如何估值？
这和具体的棋类游戏有关，同时也和你最终打包的程序的棋力有关，估得好，棋力高，这是很显然的。不管什么棋类的估值，它都有一个共同点：
对特定的局面估值要非常准确！特定的局面是那些‘胜负’非常明显的局面，你要为‘胜’打一个最高的分HScore，为‘负’打一个负最高的分-HScore，而‘平局’可以适中给分，可以给一个稍大于0的分，在不能获胜的局面里，会趋向于平局。
然后就是要有前瞻性，从一个局面分析，不搜索也不是不可以看得‘深刻’，也可以说是‘全局观’，估值函数要体现游戏的全局观，它是从整体上把握，从一个点看到了一条线！这样才是好的估值。
好了，下一个话题是‘优化搜索’，哦，这可难了，我现在还看不懂一些高级搜索算法。其实用负极大搜索算法编出来的程序是不能搜的，基本上不能搜。因为搜索量实在太大了！在一些规则简单的棋类游戏中，像黑白棋，平均分支因子都有10左右，直接去搜索，是搜不了几层的，这样的指数效应太明显了！最简单和最基本的优化方法是alpha-beta剪枝！
这是一种纯数学上的方法，是在不对搜索的结果影响的前提下剪枝，它可以使分支因子变为原来的开根号那么大（平均情况）！alpha是一个当前最好的值，如果有更好的(>alpha)将更新它，而beta是一个当前最差的值，如果有更差的(>beta)将马上产生截断（也就是不再搜索，而是直接返回原来的beta）代码如下：
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
{
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft())
{
MakeNextMove();
val = -AlphaBeta(depth – 1, -beta, -alpha); //注意到代入子树搜索的alpha,beta值
UnmakeMove();
if (val >= beta)
{
return beta;
}
if (val > alpha)
{
alpha = val;
}
}
return alpha;
}
它工作的过程，可以拿个简单的例子演示一下看看（一开始搜索时给alpha最小的值，比-HScore还要小，给beta最大的值，比HScore还要大，这很重要，否则会搜索不出胜局和负局，这是很糟的）。实际上，alpha是当前结点的兄弟结点对应的子树中搜索出来的最好值，而beta是父结点当前搜索的最好值的相反数，父结点和子结点的关系是对立的（是属于对弈的两个人，一个人会处理父结点的局面，一个人会处理子结点的局面），所以父结点的最好反过来就成了子结点的最坏，反过来也是一样。另外一种理解方法，是把alpha-beta看成一个窗口(window)，这个窗口的大小表示当前结点值得搜索的子结点的价值取值范围，往里搜索的过程就是缩小窗口的过程。它的全部效率就体现在beta值的截断作用，它的意思是说，我不用知道一步棋有多差，只要知道比前面的更差，当然我就没有任何理由选择走这步棋了！
好的估值+快速的搜索=强力的程序。我有一种想法，是评价估值的准确性的。估值不可能准确，但我想知道它有多准确，或者平均有多准确，怎么描述这里的准确性？比如，考虑一个局面p，如果直接估值（相当于搜索1层）价值是-200，而如果搜索3层，价值升到了100，而搜索5层价值又涨到了400，因为它在不久的将来有非常好的局面出现，那可否设搜索k层的评价（搜索+估值）值是E(k)，那(E(k2)-E(k1))/(k2-k1)在取了所有可行范围的所有值，再取平均，就认为是你的估值函数的准确性，如果它绝对值越高说明越不准确，越低说明越准确，那可否寻求一种自适应的方法（比如遗传算法）使估值函数的准确性值收敛呢？这样会提高棋力吗？我觉得做一个聪明的人工智能程序，不是在于，你一创造它，它就能战胜人类世界冠军，而是刚开始运行只有200分的棋力，而在和高手下了几个月后棋力涨到了2000分，然后是否战胜世界冠军已经不重要了，我觉得这才是人工智能！
关于人工神经网络
今天有看这方面资料，一点点感想。
首先这样的模型，从功能上讲是很强的，人脑有神经元10^11左右个，我们就可以随心所欲的思考。人的视觉，触觉，听觉都是输入，肢体的控制神经，语言中枢神经和口腔发声控制神经都是输出，从本质上讲这样的抽象是根本的，所谓思维就是这个神经网络中的神经元的相互作用的过程。其次，什么是记忆？记忆就是‘反馈神经’，不知道这个名词准确与否。在《数字逻辑》中时序逻辑电路中也是这样的，输出反过来当成输入，构成一个‘反馈线’，反馈线上的电信号就是‘记忆’，简单的触发器就是这样两个反馈线的与非门构成的，触发器就是‘存储器’的基本元件，一个触发器可以记录一bit，内存上的Memory就是这样做的，同样在神经网络中也是这样，我们把回忆拿出来，重新思考，我们把昨天未下完的一盘棋拿出来继续思考，这就是反馈输入嘛。至于有没有硬盘式的存储器，就不清楚了，实际上，如果把我们的神经系统看成‘电系统’，我们什么时候断过电哟，你拿你的脑袋使劲往墙上撞，有可能会断一会电-_-
其次一点，就是怎么‘学习’？总的来讲，分两种，有教师的学习和无教师的学习，有教师的学习就像是一种训练，我想要这组人工神经网络（ANN）的功能是这样的，我就拿一堆的正确的[输入，输出]去训练它，拿输入数据得到真实的输出，再和理论输出比较，拿这个误差去修改‘弧’上的权值，最终使得它满足所有的‘学习资料’，就拿最简单的与逻辑门来说吧，输入神经元x1,x2（0,1），输出y=f(x1*w1+x2*w2-e)，测试数据是：
0,0,0
0,1,0
1,0,0
1,1,1
初使w1,w2,e随机得到，假设是7,4,5吧，第三组数据训练有误差，结果是7-5=2输出是1，于是修正
w1=w1+a(0-1)x1
w2=w2+a(0-1)x2
其中a是(0,1)间的值，表示学习的增益因子，用于控制调整的速度，就取0.5吧，于是修正后的w1=6.5,w2=4，还是不满足，再修正几次，直到w1=4.5,w2=4,e=5就满足了，于是它就会做‘与’运算了。
这里教师的作用就是提供‘正确’的训练数据，这样做学得很快，跟人一样，我们在学校里学习就是这样。另外一种无教师的学习，就会慢很多，会在失败中学习，想起以前英语老师教我们学英语就是要"Make mistakes & try again!"，从错误中学习。而正确与错误与否是外界告诉的，这就是要去尝试，去栽根头，然后再爬起来。
算法驿站 (rickone 的 BLOG)
素数检验法
数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
我们知道,费马小定理是现代素数判定方法的基础,如果该定理的逆命题成立那该多好,只要计算一下ap-a是否能被p整除,能则p是素数,否则p是和数.遗憾的是这只对1<p<341内的数成立,因为2341-2能被合数341整除,即费马小定理的逆命题不成立.前面已经说过像341这样的数叫做伪素数.
ARCL检验法改进了费马检验,它不再受伪素数的愚弄.这种检验法需要相当多的高深的数学知识.现在我还不能提供这个方法的详细情况,以后可能会的.在下面我将要讲的是n-1检验法和n+1检验法.
1.n-1 检验法
如果对于奇数 n,我们已经知道了n-1的素因子分解式,那么如下的n-1检验法将是有效的.在1891年,E.卢卡斯将费马小定理改进成对于检验素数很实用的形式,后来又由克拉奇科和莱默进一步改进:
定理一:设n>1是一个奇数,如果对于n-1的每一个素因子q存在一个整数a使得:
an-1 = 1 (mod n), and
a(n-1)/q ≠ 1 (mod n);
则n是素数.
这个定理的不足之处是需要知道n-1的全部因子,那么能不能不需要如此呢?下面一个定理是泊克林顿(Pocklingdon)在1914年发现的:
泊克林顿定理:设n-1=qkR,这里q是素数,并且R不能被q整除.如果存在一个整数a使得an-1=1并且
gcd(a(n-1)/q-1,n) = 1,则n的每一个素因子q都具有qkr+1的形式.
利用这个定理,我们可以将定理一改进如下:
定理二:假定 n-1 = FR, 这里 F>R, gcd(F,R)=1 并且已知 F的素因子分解.如果对于F的每一个素因子q 都存在一个整数a >1 使得
an-1 = 1 (mod n)
gcd(a(n-1)/q-1,n) = 1;
则 n 是素数. (注意对每一个 q 都可以用不同的 a).
定理二还可以进一步改进如下:如果 F<R, 并且R 的每一个因子都大于sqrt(R/F); 或者 n<2F3, R=rF+s, 0<s<F, 这里 r 是一个奇数或者 s2-4r 不是一个平方数;则 n 是素数.
在我们转向另一种检验法之前,让我们把如下定理二的两种应用记述如下:
佩班(Pepin)检验法(1877): 让 F(n) 第n个费马数 ( F(n) = 22n+1) 并且 n>1.
F(n) 是素数当且仅当
3(F(n)-1)/2 = -1 (mod F(n)).
普罗斯(Proth)定理 (1878): 让 n = h.2k+1且 2k > h. 如果存在一个整数a使得:
a(n-1)/2 = -1 (mod n), 则 n 是素数. (这个定理已经有一个程序,欢迎下载)
定理三 : 让 n = h.qk+1 且 q 是素数 并且 qk > h. 如果存在一个整数a使得 an-1 = 1 (mod n), 并且 gcd(a(n-1)/q-1,n) = 1, 则 n 是素数.
2. n+1 检验法和Lucas-Lehmer检验法
有许多已知的大素数具有形式N-1, 而 N 是很容易分解因数的,为什么这些形式的数能被检验呢?因为对它们可以应用一种类似于费马小定理的有趣定理来对付它们.
假定我们选择两个整数 p 和 q 使得 p2-4q 不是模 n的一个平方剩余, 则多项式 x2-px+q 有两个不同的根, 其中之一是 r = (p+sqrt(p2-4q))/2, 并且很容易推导出 r 的幂具有如下形式:
引理 1: rm = (V(m) + U(m)sqrt(p2-4q))/2
这里 U 和 V 分别定义如下:
U(0) = 0, U(1) = 1, U(m) = pU(m-1) – qU(m-2)
V(0) = 2, V(1) = p, V(m) = pV(m-1) – qV(m-2)
这就是关于 p 和 q的卢卡斯序列. 一个众所周知的特例是令 p=1, q=-1, 则 U(m) 斐波拿契数列.卢卡斯序列有许多特性,使得它们能很快地进行计算(用一种类似于我们在计算 xm 时所用的重复平方的方法):
U(2m) = U(m)V(m)
V(2m) = V(m)2-2qm
现在我们来叙述这种类似于费马小定理的定理:
引理 2: p, q 和 r 同上 (使得 p2-4q 不是模 n的一个平方剩余),
让 2r = a+bsqrt(p2-4q) (mod n) .
如果 n 素数, 则 2rn = a-bsqrt(p2-4q) (mod n).
这样说有点太混乱, 让我们用我们的 U 序列(即sqrt(p2-4q)的系数).
引理 3: (p, q 同上) 如果 n 是素数, 则 U(n+1) = 0 (mod n).
现在我们可以重新叙述一下定理了:
定理 4: 让 n > 1 是一个奇整数. 如果对于 n+1 的每一个素因子 r 都存在相应的素数 p 和 q (这里 p2-4q 不是 n 的平方剩余)使得:
U(n+1) = 0 (mod n),并且
U((n+1)/r) is not 0 (mod n);
则 n 是素数.(确定一个数 d 是否是 modulo n 的一个平方剩余很容易用 Jacobi 符号来决定,这在任何一本数论书中都可以找到.)
一个重要的有趣特例是设S(k) = V(2k+1)/22k
卢卡斯-莱默检验法(1930): 让 M(n) 是第 n 个梅森素数 (即 M(n) = 2n-1). M(n) 是素数当且仅当 S(n-2) = 0 (mod M(n)) 这里 S(0) = 4 并且 S(k+1) = S(k)2-2.
这个检验法计算特别快,因为它不需要做乘法,只要做移位即可.编写程序也很容易.
|
|
·