问个在缓冲区中查找另一个缓冲区的算法

leiing

我最近做个项目，是从一个大缓冲区中找是否包含一个小缓冲区，现在是循环一遍大缓冲区，先判断第一个字节是否相等，相等再继续判断，代码如下：

1. 
   
2. char *big = {xxx};
   
3. char *small = {xxx};
   
4. int i = 0;
   
5. int b_len = 1000000; //big缓冲区的长度
   
6. int s_len = 100;        //small缓冲区的长度
   
7. 
   
8. for (; i<b_len; i++) {
   
9.     if (big[i] == small[0]) {
   
10.         if (memcmp(&big[i], small, s_len) == 0) {
    
11.             printf("Found");
    
12.             break;
    
13.         }
    
14.     }
    
15. }
    

复制代码

感觉循环一遍效率太低，各位大神是不是有类似查找的更好算法？

现在的杀毒软件的病毒库，也都是几十万的数量。
我也很好奇硬盘扫描时是如何杀毒的？
每个文件都要和几十万病毒码做比较吧，
每个文件至少也几百KB吧，不会每个文件都从第一个字节到最后一个字节循环来判断吧？

狗蛋

hash～～

进一步提示，md5/sha1之类并不是加密算法，而是hash算法

noword2k

缓冲区一直在变，不能用hash吧。

用KMP算法查找，效率比较高。

狗蛋

回复 3# noword2k


    不是让你做hash表，而是用hash算法求出摘要并管理起来，将来搜摘要即可。

比如，子缓冲区1的md5是aabbccddeeff，待测数据的md5也是这个值，那么就可以很安全的认为这两块数据是等同的。



hash并不非要是hash表那一大摞子东西，核心就是一个算特征值然后用特征值直接比较的思想。

hash表是这个思想的一个典型应用：如果我把特征值直接算成地址，那么数据查找不就是O（1）效率了吗？

病毒特征库是另一个应用： 我把特征值用MD5之类算法算出来，那么只要一个执行文件部分内容的MD5（或其他经过优化的摘要算法）和这个特征值相同，我就可以安全的认为抓到了病毒。


再如，推广一点，你想用google搜我这个帖子，不需要你把全部内容默出来。只要记得里面的几个关键字，用google搜之即可。
提取关键字，这显然也是一种摘要算法。

noword2k

回复  noword2k


    不是让你做hash表，而是用hash算法求出摘要并管理起来，将来搜摘要即可。

比如 ...
狗蛋 发表于 2011-09-30 13:01

    假设大缓存区的长度是n，你要计算几次hash值？
LZ只是memcmp，你还要算每段的hash，不是脱裤子放屁——多此一举吗？

狗蛋

回复 5# noword2k


    呵呵，刚开始没仔细看，以为他的大缓冲区也是分块的。

这种情况下，因为一般来说，小块缓冲更新往往会比大块频繁，所以搞个hash可以避免每次小缓冲内容改变都要重新和大缓冲里的每个块比对。

anbutu

Boyer–Moore  比 KMP 更高效一些

noword2k

人不学习就落后啊，敢情还有Boyer–Moore。