Нарезка файла с помощью алгоритма Рабина Карпа

Question

Я написал AC-программу, которая должна разрезать файл на куски с помощью алгоритма Рабина Карпа. Это адаптация программы aC#, которую вы можете найти здесь.

Кажется, работает, но проблема остается. средний размер кусков не то, что ожидается.

Использование заключается в следующем:

Файл rabin Prime WindowSize BoundaryMarker

где:

Рабин - это имя исполняемого файла.

Prime - это высокое простое число. Например, 100007

WindowSize - это размер скользящего окна. По примеру 48

BoundaryMarker - это число битов, равное 0 в отпечатке пальца

Файл - это файл для обработки

если я установлю 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;
}

Answer 1

Выполнение вашего кода с BoundaryMarker = 13 на мегабайте случайных данных дало мне 104 фрагмента при среднем размере фрагмента 10082 байта. Это не слишком далеко от ожидаемого 8192.

Однако меньшие значения BoundaryMarker показывают более заметное смещение; например, установка его на 10 дала мне средний размер порции 3049 байт, что довольно далеко от ожидаемого 1024. А установка BoundaryMarker = 5 дала средний размер порции 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 байтов от предыдущей границы, эффективно объединяя фрагменты короче, чем 2048 байтов, со следующим фрагментом. else if (index - lastIndex >= 65536) Между тем, проверка заставляет искусственную границу фрагмента предотвращать рост фрагментов длиннее 65536 байт.

Если это поведение (которое заставляет все фрагменты иметь длину не менее 2048 и не более 65536 байт) не соответствует вашим требованиям, вы можете просто удалить эти проверки, упростив код до:

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

Действительно, внесение этого изменения приводит к среднему размеру фрагмента, очень близкому к 2ⁿ байтов для BoundaryMarker = n, по крайней мере, для n ≤ 12 или около того.

Для n = 13, по-видимому, наблюдается заметное смещение вниз, которое, как я подозреваю, вызвано тем фактом, что простое число 100007 только примерно в 12,2 раза превышает граничный модуль 2¹³. Поскольку значения сигнатуры более или менее случайным образом распределены по модулю простого числа, то дополнительные 0,2 приводят к тому, что они слегка смещаются в сторону меньших значений (включая ноль) при дальнейшем уменьшении по модулю 2¹³.

Это смещение можно легко исправить, используя большее простое число, например, 2³¹-1 = 2147483647. Действительно, переключение на это простое число делает средний размер фрагмента намного ближе к 8192.

Answer 2

Вы можете попытаться обновить значение BoundaryMarker, вы можете получить различные длины. Я использовал RB следующим образом: ссылка на github. И я думаю, что длина на самом деле зависит от содержания.