关键字
Rabin karp 算法, C++, ubuntu 14.04, linux, big integer, gmp
为了计算冗余度， 我写出了如下算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 |
void
HandleAMission(const
char *srcFileName, FILE
*output, int
blockSize, int
samplingRate, int
cacheSize) { const
int MAGICNUM = 33; // hash for more, refer to const
int MAXINTEGER = 4294967295; // biggest unsigned int struct
IP_hdr *ip_hdr; struct
TCP_hdr *tcp_hdr; struct
UDP_hdr *udp_hdr; char
*payLoad; char
src_ip_char[STRSIZE], dst_ip_char[STRSIZE]; int
proto; // udp for 0, tcp for 1 int
payLoadLen; PcapParser pcaparser(srcFileName); // init pcapparser // init FIFOCache FIFOCache fifocache(cacheSize); // statistic unsigned long
totalByte = 0; unsigned long
savingByte = 0; unsigned int
localMax; unsigned int
candiMax; // init big integer mpz_class product(0); // current product of char array of blocksize mpz_class part(1); // used as temp mpz_class head(0); // leftmost for(int
i = 1; i < blockSize; i ++) { head *= MAGICNUM; } while(pcaparser.NextPacket(&ip_hdr, &tcp_hdr, &udp_hdr, proto, &payLoad, payLoadLen) == 0) { if(payLoadLen < 128) continue; // init product for new packet product = 0; totalByte += payLoadLen; // init a key for(int
i = 0; i < blockSize; i ++) { product = product * MAGICNUM + (unsigned int)(payLoad[i]); } // Rabin Karp algorithm for(int
cursor = 1; cursor+samplingRate < payLoadLen; cursor += samplingRate) { for(int
offset = cursor; offset < cursor + samplingRate; offset ++) { product = product - head * (unsigned int)(payLoad[offset-1]); product = product * MAGICNUM; product = product + (unsigned int)(payLoad[offset+blockSize-1]); part = product % MAXINTEGER; candiMax = part.get_ui(); if(candiMax > localMax) { localMax = (unsigned int)candiMax; } } if(fifocache.HasKey(localMax)) { savingByte += blockSize; } else
{ fifocache.AddKey(localMax); } } } printf("Saving byte is %ld byte\n", savingByte); printf("Total byte is %ld\n", totalByte); printf("Redundancy rate is %lf\n", 1.0*savingByte/totalByte);} |
注意, 上面的代码中, Rabin Karp 部分我没有设计成接口, 实际上我写了一个 RabinKarp 类, 但经验告诉我, 处理计算密集型任务时, 不要搞什么花哨的接口, 继承, 重用, 越 dirty（代码都写到一个函数内） 效率越高, 当然即便如此， 我还是设计了个 PcapParse 类用于处理 pcap 文件, 经不住诱惑.
然后我运行了十个 testcase, 结果却不令我满意, 平均 1MB 一秒， 相当于 1GB 要处理 1000s, 对于 T 级别的计算任务来看, 这显然是不可接受的.
我有两条路可以走， 一个是自己设计大整数类， 弃用 gmp big integer， 二是弃用 Rabin Karp, 对输入字符串暴力哈希。
回想自己使用 Rabin Karp 的原因， 是前人的 paper 说 rabin karp 能有效的减少计算时间， 或许 rabin karp 本身足够快， 但因使用 rk 算法引入的 gmp 却太慢， 导致 rk 算法的优势尽失。 我本来就怀疑 gmp 的性能， 而事实的确验证了我的怀疑， gmp 太慢了。
呵， 还是用 murmurhash 暴力哈希吧
Rabin Karp 算法实战,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3719072.html