有时候有这种需求,需要从一个二进制大文件中查找是否有某种格式的文件，由于大文件是二进制，且非常大，几百M，一般的手工查找方式不太现实了。可以可以通过代码来遍历二进制，查找是否有该文件格式的关键字数据（一般文件头都会有标识，比如dds文件首三个字节是DDS，png、jpg、swf等文件都会有自己的标识头）。

关于搜索算法，我一开始想到的是字符串匹配算法，Google了一下，关于字符串匹配算法有很多种，其中称为Sunday的算法速度非常快，且非常容易理解。关于该算法的具体实现，可以查看本文末尾提供的参考资料，特别是那个PPT，看那个例子非常浅显明了。

字符串匹配算法只能从固定长度内存中匹配，几百M几G的文件不可能一次性全部读取到内存中，所以我使用了分块读取，而在读取下一块文件时，文件指针向后滑动一个窗口，重叠读取，避免这部分内容漏掉匹配。

#include 
#include 

#define TRUNK_SIZE 1024 * 100 //每次读取的块大小

//创建预查表
void preQsBc(unsigned char *pattern, int m, int qsBc[]) {
    int i;
    //qsBc[c]=min{i : 0  < i ≤ m and pattern[m-i]=c} if c occurs in pattern, m+1 otherwise 
    for (i = 0; i < 256; ++i)
        qsBc[i] = m + 1;//预先设置，假如i不在pattern串中，则表格值为m+1
    for (i = 0; i < m; ++i)//目的是设置表格值为i在pattern中，从右开始第一次出现的位置，
        qsBc[pattern[i]] = m - i;//这里循环是从左开始遍历，后边的值会覆盖前面设置的值，所以能达到目的
}

//pattern为要搜索的子串，m为pattern的长度
void fQS(unsigned char *pattern, int m, FILE *fp) {
    if(m >= TRUNK_SIZE) {
        printf("not support:pattern length >= TRUNK_SIZE(%d)", TRUNK_SIZE);
        return;
    }

    //建立预查表
    int qsBc[256];
    preQsBc(pattern, m, qsBc);

    //取得文件尺寸
    int size;
    fseek(fp, 0, SEEK_END);
    size = ftell(fp);
    rewind(fp);

    printf("处理进度:00%%(00)");

    unsigned char *trunk = malloc(TRUNK_SIZE);//分配块内存
    int fpos = 0;//当前文件位置
    int count = 0;//匹配成功个数
    while(size - fpos >= m) {
        printf("\b\b\b\b\b\b\b%02d%%(%02d)",(unsigned)((fpos * 100.0f) / size),count);

        //读取一个块
        int n = (size - fpos) > TRUNK_SIZE ? TRUNK_SIZE : (size - fpos);
        fread(trunk, 1, n, fp);

        //从块中查找匹配
        int jpos = -1;
        int j = 0;
        while (j <= n - m) {
            if (memcmp(pattern, trunk + j, m) == 0) {
                jpos = j;
                ++count;
                //printf("found in position:%d\n",fpos + j);
                //匹配成功，文件位置为：fpos + j

                //TODO:从文件中提取需要的内容

            }
            j += qsBc[trunk[j + m]];
        }

        if(size - fpos == m)break;//刚好到文件结尾，则立即结束查找

        if(jpos >= 0 && jpos == n - m) {//刚好尾部匹配成功，不需要滑动窗口
            fpos += n;
        }else {
            fpos += n - m;//向后滑动一个窗口,以防漏掉
        }
        //printf("fpos=%d\n",fpos);
        fseek(fp,fpos,SEEK_SET);
    }
    printf("\b\b\b\b\b\b\b%02d%%(%02d)",100,count);
    free(trunk);
    trunk = NULL;
}

int main(int argc,char **argv) {
    printf("---by yoyo(http://yoyo.play175.com)----\n",);

    FILE *fp = fopen("E:\\yoyo\\mydocuments\\bigfile.bin","rb");
    if(fp == NULL) {
        perror("open file failed");
        goto exit;
    }

    fQS("DDS",3,fp);

    exit:
    if(fp != NULL) {
        fclose(fp);
        fp = NULL;
    }
    return 0;
}

参考资料：
1)Quick Search Algorithm A very fast substring search algorithm, SUNDAY D.M., Communications of the ACM . 33(8),1990, pp. 132-142.http://alg.csie.ncnu.edu.tw/course/StringMatching/Quick%20Searching.ppt)
2)Quick Search algorithm implement(http://www-igm.univ-mlv.fr/~lecroq/string/node19.html)