LINUX.ORG.RU

Поиск в файле / FindPattern();


0

0

Задача следующая: находить произвольную последовательность байт в файле большого объема. Решение придумал , но видимо настолько примитивное, что и результат не устраивает , а именно работает все так медленно , что проще ничего не искать :)

Вот функция, реализующая поиск:

int FindPattern(FILE *dat,unsigned char *p,unsigned long int idx)
{
long int i,j;
unsigned char buf; // для хранения одного байта
// в idx кол-во эл-ов в p[]
i=idx;j=0;
while(!feof(dat) && i!=0) {
fread(&buf,1,1,dat);
if(buf==p[j]) //в p[] нужная хранится последовательность
{
i--;
j++;
}
else {
j=0;
if(i!=idx) fseek(dat,i-idx,SEEK_CUR);
i=idx;
}
}

if(i==0) return 1;
else return 0;
}

Может и коряво написано, но ускорить такой алгоритм уже имхо нельзя. Поэтому помогите плиз, есть где про такого рода задачи почитать или может есть готовые решения в какой-нибудь либе?

Спасибо.

anonymous

Re: Поиск в файле / FindPattern();

Попробуй создать "окно" размером с шаблон и читай в него посимвольно из файла. Сравнение "окна" с шаблоном можно будет делать strcmp.

anonymous ()
Ответ на: Re: Поиск в файле / FindPattern(); от anonymous

Re: Re: Поиск в файле / FindPattern();

Пробовал , еще медленнее работает. :( надо что ли куски совсем большие брать, тоже думал - реализовать самому сложно.

anonymous ()

Re: Поиск в файле / FindPattern();

Быстрее это сделать можно, для этого используются всякие конечные автоматы с модификациями. Так что, попробуй использовать regex & friends.

justme ()
Ответ на: Re: Поиск в файле / FindPattern(); от justme

Re: Re: Поиск в файле / FindPattern();

я бы попробовал если бы знал что такое конечный автомат вместе с его друзьями ;P
Но все равно огромное спасибо.

anonymous ()

Re: Поиск в файле / FindPattern();

Так как раз, чтобы использовать regex что такое конечный автомат знать не нужно.

justme ()

Re: Поиск в файле / FindPattern();

Попробуй действительно использовать регулярные выражения (можно на перле испытать) и сравнить быстродействие с твоей сишной прогой. Возможен еще такой вариант - есть разные библиотеки для работы регулярными выражениями на С/С++, их поюзай. Мне нравится regexx для С++ (в ней реализован перловый regex).
Тот самый anonymous с "окном"

anonymous ()

Re: Поиск в файле / FindPattern();

Еще раз огромное спасибо за помощь , буду разбираться. :)

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.