- 浏览: 16761 次
最新评论
关键字 (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)(mod p)作为x的指纹。
Ip(x)是x的指纹
I(x)是x的编码,就是我们说的原来的字符串
p是一个小于M的素数,M可根据具体需要调整,这里取M=2*n^2
Ip(x)等于I(x)%p
其实就是把所有01串转为一个大数然后mod p 后的结果就是指纹
我的算法如下:用java实现 /** * @param chs : 01串 * @param p :大素数 * @param m :A串的长度 * @return :返回指纹 * 时间复杂度:O(m) */ public static long getFirstFingerprint(char[] chs, long p, int m) { //把01串转为一个大数然后mod p 得出来的就是指纹 BigInteger fingerprint = BigInteger.valueOf(0); BigInteger pow = BigInteger.valueOf(1); BigInteger bp = BigInteger.valueOf(p); //这部分的计算就是转为一个大数 for (int i = m - 1; i >= 0; i--) { if (chs[i] - '0' == 1) { fingerprint = fingerprint.add(pow); } //System.out.println(pow); pow = pow.multiply(BigInteger.valueOf(2)); } //mod p fingerprint = fingerprint.mod(bp); return fingerprint.longValue(); } 首次计算时用上面的算法,再计算第二个时候用下面另外一种方法,主要基于第一种方法的结果计算得到
我的算法实现如下: /** * @param firstFingerprint : 前一个指纹 * @param xj : 前一个01串的第一位 * @param xjm: 前一个01串的后边一个,如1000010, * 前一个01串是100001,那么后边一个就是0了,因此,xjm就是0 * @param p: 大素数 * @param m: A串的长度 * @return 下一串的指纹 * 时间复杂度:O(1) */ public static long getNextFingerprint(long firstFingerprint, int xj, int xjm, long p, int m) { BigInteger bi = BigInteger.valueOf(2); long wp = 0; if (xj != 0) { BigInteger exp = BigInteger.valueOf(m); BigInteger mod = BigInteger.valueOf(p); bi = bi.modPow(exp, mod); wp = bi.longValue(); } long ret = (2 * firstFingerprint - wp + xjm) % p; if (ret < 0) ret += p; return ret; } 另外一个问题是快速求得大素数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写下 public static long getNeighborPrimeFast(long M) { long p = --M; boolean isPrime = false; while(!isPrime) { isPrime = Prime.isPrime((int)p); if (isPrime == false) p = --M; } return p; } //随机产生01串 public static char[] generateCode(int num) { char tmp[] = {'0', '1'}; char[] chs = new char[num]; for (int i = 0; i < num; i++) { chs[i] = tmp[r.nextInt(2)]; } return chs; } public static void main(String[] args) { //A串(01串) 长度为15 随机产生01串(由于是随机产生,太大的话很难与B串匹配) char[] ys = StringMatcher.generateCode(15); //B串(01串) 长度为500000 随机产生01串 char[] xs = StringMatcher.generateCode(500000); int n = xs.length; int m = ys.length; long M = 2 * n * n; long p = StringMatcher.getNeighborPrimeFast(M); long[] fingerPrints = new long[n - m + 1]; long fingerYs; fingerPrints[0] = StringMatcher.getFirstFingerprint(xs, p, m); fingerYs = StringMatcher.getFirstFingerprint(ys, p, m); for (int i = 1; i < fingerPrints.length; i++) { fingerPrints[i] = StringMatcher.getNextFingerprint(fingerPrints[i - 1], xs[i - 1] - '0', xs[i + m - 1] - '0', p, m); } int cnt = 1; for (int i = 0; i < fingerPrints.length; i++) { if (fingerPrints[i] == fingerYs) { System.out.println("count:" + cnt++ + " " + i); } } } 测出结果:与A相同的指纹,准确率(1-1/2^100)
count:1 29747
count:2 50706
count:3 83590
count:4 96803
count:5 103301
count:6 229482
count:7 236235
count:8 246710
count:9 334959
count:10 353036
count:11 363681
count:12 384086
count:13 388068
count:14 417645
count:15 482496
count:16 483673
count:17 487611
count:18 494533
发表评论
-
java 使用正则来过滤字符串中的特殊字符
2012-07-06 09:45 985Pattern pattern1 = Pattern.co ... -
正则表达式(初识笔记)
2012-07-06 09:38 649............................. ... -
ps画个矩形框,如何设置线宽
2012-07-06 09:30 1876i am now in university(HIT@We ... -
父页面iframe自适应子页面高度
2012-07-05 20:45 1363父页面有table,有tr,td。td中有iframe。页 ... -
ADF中组件无法显示问题
2012-07-03 13:44 800在ADF开发过程中,偶尔会遇到一些组件甚至页面无法显示到问 ... -
Flex 4 设置背景图片 Canvas backgroundImage BitmapFill fillMode
2012-07-02 12:45 969Flex 3中Canvas是可以设置backgroundI ... -
Flex中,跨List实现SHIFT多选的例子
2012-07-02 12:45 615最近工作中遇到的问题,客户要求做这么个东西。还是稍微 ... -
Flex中本地图片上传前的预览
2012-07-02 12:45 782height="345" h ... -
Flex Panel 拖动效果例子
2012-07-02 12:45 6232010-08-06 今天在flex下尝试了下panel ... -
Ext 4 概述(六)之Grid
2012-07-01 10:07 568这次升级Ext 4全部 ... -
也谈jQuery之学习
2012-07-01 10:07 671由于之前一直是做 ... -
Firefox/Chrome下flash的wmode参数设为opaque或transparent时输入文本框中无法输入中文汉字的解决方法
2012-07-01 10:07 782这段时间做个项目 ... -
深度剖析WinPcap之(十)――数据包的内核过滤(13)
2012-07-01 10:07 1394数据包到达网络接 ... -
Flash Builder 4-找不到所需的 Adobe Flash Player
2012-07-01 10:07 659比较懒,比较少上csdn的,如果发现留言给我没有回复,望见 ... -
Flex组件:Style的使用
2012-06-30 16:32 699Flex组件:Style的使用 2010 ... -
Flex中Bindable的原理
2012-06-30 16:32 589Flex中Bindable的原理 2011年11月01日 ... -
Flex AIR)创建“不规则形状”的Air透明窗体
2012-06-30 16:32 884Flex AIR)创建“不规则形状”的Air透明窗体 201 ... -
如何在flex当中使用swc
2012-06-30 16:32 763如何在flex当中使用swc 2 ... -
FLEX和Actionscript开发FLASH游戏7-3
2012-06-30 16:32 411FLEX和Actionscript开发FLASH游戏7-3 ...
相关推荐
这是一个C语言程序,利用字符串函数,来对字符串比较大小,比较字符串。
字符串比较处理宏字符串比较处理宏字符串比较处理宏字符串比较处理宏
汇编语言开发,实现两个字符串的输入,然后进行字符串的比较,是否在第二个字符串中还有第一个字符串
使用指针和for循环来比较两个字符串大小 ,字符串即为一个字符数组
《动态规划》之--字符串比较问题(扩展距离),主要思路通过策略和无效性来求解。特点最优子结构性质,重叠子问题。
51单片机串口接收字符串比较
算法提高 字符串比较 时间限制:1.0s 内存限制:512.0MB 独立实现标准字符串库的strcmp函数,即字符串比较函数,从键盘输入两个字符串,
将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。如果按字典顺序此 String 对象在参数字符串之前,则比较结果为一个负整数。如果按字典顺序此 String 对象位于参数字符串之后,则比较结果为一...
字符串比较问题 Description ?问题描述: 对于长度相同的2 个字符串A和B,其距离定义为相应位置字符距离之和。2 个非空格 字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0;空格与其它字符的距 离...
实现3-17字符串比较问题.cpp
字符串大小比较的规则, C、C#、java等高级语言的字符串比较规则
C#字符串删除指定字符串|C#字符串删除子字符串
一个关于字符串匹配的算法,已经经过编译,希望对你有帮助
C++忽略大小写比较字符串的程序 C++忽略大小写比较字符串的程序
oc字符串比较
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
//依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不相等的字符替换为字符'@'后生成的新串输出, //并输出所统计的两个字符串中相等字符的数目。
修改过好几次的程序 挺好的 针对于字符串 在devc++运行成功
字符串比较除了代码中的方法还有哪些方法更好的描述。