首页 > 代码库 > Rabin Karp 算法实战

Rabin Karp 算法实战

2024-07-03 19:58:48   218人阅读

关键字

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 暴力哈希吧

 

 

 


联系
我们