如何高效地进行远程大规模字符串比较问题

关键字（keywords）：大规模字符串匹配远程比较快速

随着互联网的快速发展，信息量成爆炸趋势，大规模的文本处理已经成为一个挑战，今天这里我想解决一个海量数据中会经常遇到的一个问题，就是如何在两台主机之间进行高效地大规模字符串比较问题，如果给定100MB字符串A和1GB字符串B分别在远程在两台主机上，那我想比较A是否是B的字串？

怎么办呢？很明显，我们用一般的算法是无法解决这个问题的。因为如果是一般的算法，肯定是先传送这两个字符串到同一台机子上，然后再用KMP等算法进行字符串比较，我想大家都知道其实这样是非常耗时的，我下面给出了我的解法，使用的算法是随机算法，解决的大致如下：

先将A字符串转为01串，转换后，设01串的长度为lenA，然后计算该字符串的指纹，指纹是一个整数，在这里的指纹即能唯一表示A的字符串，如同每一个人的都有自己的手指指纹一样，是唯一的。

同样将B串转为10串，转换后，假设01串的长度为lenB，那么它的指纹个数为（lenB-lenA+1）

如下图所示：

从上图中，可以看到，B串共有n个指纹。

那么怎么计算这个指纹呢？

一般计算指纹如下：令I(x)是x的编码，去Ip(x)=I(x)(modp)作为x的指纹。

Ip(x)是x的指纹

I(x)是x的编码，就是我们说的原来的字符串

p是一个小于M的素数，M可根据具体需要调整，这里取M=2*n^2

Ip(x)等于I(x)%p

其实就是把所有01串转为一个大数然后modp后的结果就是指纹

我的算法如下：用java实现/***@paramchs:01串*@paramp：大素数*@paramm：A串的长度*@return：返回指纹*时间复杂度：O(m)*/publicstaticlonggetFirstFingerprint(char[]chs,longp,intm){//把01串转为一个大数然后modp得出来的就是指纹BigIntegerfingerprint=BigInteger.valueOf(0);BigIntegerpow=BigInteger.valueOf(1);BigIntegerbp=BigInteger.valueOf(p);//这部分的计算就是转为一个大数for(inti=m-1;i>=0;i--){if(chs[i]-'0'==1){fingerprint=fingerprint.add(pow);}//System.out.println(pow);pow=pow.multiply(BigInteger.valueOf(2));}//modpfingerprint=fingerprint.mod(bp);returnfingerprint.longValue();}首次计算时用上面的算法，再计算第二个时候用下面另外一种方法，主要基于第一种方法的结果计算得到

我的算法实现如下：/***@paramfirstFingerprint:前一个指纹*@paramxj：前一个01串的第一位*@paramxjm:前一个01串的后边一个，如1000010，*前一个01串是100001，那么后边一个就是0了，因此，xjm就是0*@paramp:大素数*@paramm:A串的长度*@return下一串的指纹*时间复杂度:O(1)*/publicstaticlonggetNextFingerprint(longfirstFingerprint,intxj,intxjm,longp,intm){BigIntegerbi=BigInteger.valueOf(2);longwp=0;if(xj!=0){BigIntegerexp=BigInteger.valueOf(m);BigIntegermod=BigInteger.valueOf(p);bi=bi.modPow(exp,mod);wp=bi.longValue();}longret=(2*firstFingerprint-wp+xjm)%p;if(ret<0)ret+=p;returnret;}另外一个问题是快速求得大素数p，p是小于M，但与M（M=2n^2）相近的素数，这里我用了Miller-Rabin的一个改进算法

时间复杂度为O(k*(log(n))^3)，n是M的值，k与素数的误判率有关，误判率为1/2^k，如果k取100，基本上就已经不可能出现错误了

我将抽取时间写另外一篇blog是关于大素数高效判断的方法，也是随机算法。

至此，问题也就解决了，其他的只需要把主程序写一下就行了，我的主程序如下：

这里假设两个串都在一台机器上，传输被忽略了，如要模拟，其实只须传输一个指纹到另一台主机就行了//获得M相邻的素数p//这里的算法我会在下一次blog写下publicstaticlonggetNeighborPrimeFast(longM){longp=--M;booleanisPrime=false;while(!isPrime){isPrime=Prime.isPrime((int)p);if(isPrime==false)p=--M;}returnp;}//随机产生01串publicstaticchar[]generateCode(intnum){chartmp[]={'0','1'};char[]chs=newchar[num];for(inti=0;i<num;i++){chs[i]=tmp[r.nextInt(2)];}returnchs;}publicstaticvoidmain(String[]args){//A串（01串）长度为15随机产生01串（由于是随机产生，太大的话很难与B串匹配）char[]ys=StringMatcher.generateCode(15);//B串（01串）长度为500000随机产生01串char[]xs=StringMatcher.generateCode(500000);intn=xs.length;intm=ys.length;longM=2*n*n;longp=StringMatcher.getNeighborPrimeFast(M);long[]fingerPrints=newlong[n-m+1];longfingerYs;fingerPrints[0]=StringMatcher.getFirstFingerprint(xs,p,m);fingerYs=StringMatcher.getFirstFingerprint(ys,p,m);for(inti=1;i<fingerPrints.length;i++){fingerPrints[i]=StringMatcher.getNextFingerprint(fingerPrints[i-1],xs[i-1]-'0',xs[i+m-1]-'0',p,m);}intcnt=1;for(inti=0;i<fingerPrints.length;i++){if(fingerPrints[i]==fingerYs){System.out.println("count:"+cnt+++""+i);}}}测出结果：与A相同的指纹，准确率(1-1/2^100)

count:129747

count:250706

count:383590

count:496803

count:5103301

count:6229482

count:7236235

count:8246710

count:9334959

count:10353036

count:11363681

count:12384086

count:13388068

count:14417645

count:15482496

count:16483673

count:17487611

count:18494533