c - 使用 rabin karp 算法对文件进行切片

Question

我写了一个 c 程序，它应该用 Rabin Karp algorithm 将文件分成 block 。 .这是对 c# 程序的改编，您可以找到 Here .

似乎可以，但问题依然存在。平均 block 大小不是预期的大小。

用法如下:

rabin Prime WindowSize BoundaryMarker 文件

哪里:

Rabin 是可执行文件的名称。

质数是一个高质数。比如100007

WindowSize 是滚动窗口的大小。比如48

BoundaryMarker是指纹中设置为0的位数

File是要处理的文件

如果我将 BoundaryMarker 设置为 13，我预计平均 block 大小为 8K。 事实上，它们都不是 8K 左右。

我很难弄清楚我的程序出了什么问题？ 你能帮帮我吗？

谢谢

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>

unsigned char* buffer;
int windowSize;
int writePointer = 0;
int readPointer = 0;
int dataSize = 0;

unsigned char PushChar(unsigned char c)

{ if (++writePointer >= windowSize) writePointer=0;
  buffer[writePointer]=c;
  dataSize++;
  return(c);
}

unsigned char PopChar(void)

{ if (++readPointer >= windowSize) readPointer=0;
  dataSize--;
  return(buffer[readPointer]);
}


int main(int argc, char *argv[])

{ int fd;
  unsigned char c;

  unsigned long Q;
  unsigned long D=256;
  unsigned long pow=1;
  int i,k,boundary,boundaryMarker,index;
  unsigned char s; 

  if (argc != 5) 
  { printf("\nUsage : rabin Prime WindowSize BoundaryMarker File\n\nwhere :\n");
    printf("Prime is a high prime number. For instance 100007\n\n");
    printf("WindowSize is the size of rolling window. For instance 48\n\n");
    printf("BoundaryMarker is the number of bits set to 0 in a fingerprint\n\n");
    printf("File is the file to process\n\n");
    return(1);
  }

  sscanf(argv[1],"%lu",&Q);
  sscanf(argv[2],"%d",&windowSize);
  sscanf(argv[3],"%d",&boundaryMarker);

  for(i=1,boundary=1;i<=boundaryMarker;i++) boundary=boundary*2;
  boundary --;

  //printf("Q = %lu windowSize = %d boundary = %d\n",Q,windowSize,boundary);

  if ((buffer=(unsigned char*) malloc (sizeof(unsigned char)*windowSize))==NULL) return(1);

  for (k=1; k < windowSize; k++) pow=(pow*D)%Q;
  //printf("pow value %lu\n",pow);

  unsigned long sig=0;
  int lastIndex=0;

  if ((fd=open(argv[4],O_RDONLY))<0) exit(1);

  for (i=0; i <windowSize; i++)
  { read(fd,&c,1);
    PushChar(c);
    sig=(sig*D + (unsigned long)c) %Q;
  }

  //printf("sig value = %lu\n",sig);

  index=0; lastIndex=0;

  while (read(fd,&c,1))
  { 
    s=PopChar();
    //printf("sig = ( %lu + %lu - %lu * %lu %% %lu ) %lu",sig,Q,pow,(unsigned long) s,Q,Q);
    sig = (sig + Q - pow*(unsigned long)s%Q)%Q;
    //printf(" = %lu\n",sig);
    s=PushChar(c);
    //printf("sig2 = ( %lu * %lu + %lu ) %% %lu",sig,D,(unsigned long) s,Q);
    sig = (sig*D + (unsigned long)s)%Q;
    //printf(" = %lu\n",sig);
    index++;
    if ((sig & boundary )==0)
       { if (index - lastIndex >= 2048)
         { printf("sig & boundary = %lu & %lu Index=%d chunk size=%d\n",sig,boundary,index,index-lastIndex);
           lastIndex=index;
     }
       }
    else if (index -lastIndex >=65536)
            { printf("sig & boundary = %lu & %lu Index=%d chunk size=%d\n",sig,boundary,index,index-lastIndex);
              lastIndex=index;
            }
  }
  printf("Index=%d chunk size=%d\n",index,index-lastIndex);

  close(fd);
  return 1;
}

Answer 1

在 BoundaryMarker = 13 的情况下，在 1 兆字节的随机数据上运行您的代码，得到 104 个 block ，平均 block 大小为 10082 字节。这与预期的 8192 相差不远。

但是，较小的 BoundaryMarker 值显示出更明显的偏差；例如，将其设置为 10，得到的平均 block 大小为 3049 字节，与预期的 1024 字节相去甚远。设置 BoundaryMarker = 5 得到的平均 block 大小为 2077 字节，甚至接近预期大小为 32 字节。

仔细查看您的代码，造成这种偏差的明显原因是以下代码(为清楚起见重新格式化):

if ((sig & boundary ) == 0)
{ if (index - lastIndex >= 2048)
  { printf("sig & boundary = %lu & %lu Index=%d chunk size=%d\n",sig,boundary,index,index-lastIndex);
    lastIndex=index;
  }
}
else if (index - lastIndex >= 65536)
{ printf("sig & boundary = %lu & %lu Index=%d chunk size=%d\n",sig,boundary,index,index-lastIndex);
  lastIndex=index;
}

if (index - lastIndex >= 2048) 抑制距离前一个边界小于 2048 字节的 block 边界，有效地将小于 2048 字节的 block 与后面的 block 合并。同时，else if (index - lastIndex >= 65536) 检查强制一个人工 block 边界以防止任何 block 增长超过 65536 字节。

如果此行为(强制所有 block 的长度至少为 2048 字节且最多为 65536 字节)不是您想要的，您可以简单地删除这些检查，将代码简化为:

if ((sig & boundary ) == 0)
{ printf("sig & boundary = %lu & %lu Index=%d chunk size=%d\n",sig,boundary,index,index-lastIndex);
  lastIndex=index;
}

事实上，对于 BoundaryMarker = n，进行此更改会产生非常接近 2ⁿ 字节的平均 block 大小，至少对于 n ≤ 12 左右。

对于 n = 13，似乎确实存在明显的向下偏差，我怀疑这是由于素数 100007 仅是边界模数 2 的 12.2 倍左右¹³ 。由于签名值或多或少以素数为模随机分布，因此当进一步减少模 2¹³ 时，额外的 0.2 会导致它们稍微偏向较小的值(包括零)。

这种偏差可以通过使用更大的素数轻松解决，例如 2³¹−1 = 2147483647。实际上，切换到这个素数会使平均 block 大小更接近 8192。