Rabin Karp アルゴリズムを使用して、ファイルをチャンクにスライスすることになっている ac プログラムを作成しました。これは、ここにある ac# プログラムを改造したものです。
動作しているように見えますが、問題が残ります。平均チャンク サイズが期待どおりではありません。
使用方法は次のとおりです。
Rabin Prime WindowSize BoundaryMarker ファイル
どこ :
Rabin は実行可能ファイルの名前です。
プライムは高い素数です。たとえば、100007
WindowSize は、ローリング ウィンドウのサイズです。たとえば 48
BoundaryMarker は、フィンガープリントで 0 に設定されたビット数です。
File は処理するファイルです
BoundaryMarker を 13 に設定すると、平均チャンク サイズは 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;
}