Поиск общих сигнатур

Привет
задача такая

Есть n-ое количество файлов. Например от 3х до 100.
Нужно в этих файлах найти общие сигнатуры размером от 4х до 12 байт, которые естесна находятся под разными смещениями. Само смешение находить не обязательно. Мне нужно просто знать, есть ли в файлах общие последовательности или нет.

Со школы помню, что полобные задачи как-то решались при помощи разложения данных в м-арные деревья.

Подскажите, как проще решить данную задачу.

PS: Сперва хотел переложить на другого человека. Заплатил. В итоге был реализован поиск "в лоб", что сами понимаете, занимает невероятное количество времени.

 

Неужели никто не в курсе?

 

вообще можно так, если нет существенных ограничений по памяти... утрированно, у вас есть алфавит из 256 символов (1 байт)... вы начинаете анализировать первый файл, составляя деревья до глубины в 12 байт (по условию)... в предельном случае у вас получится 256 деревьев... далее при анализе следующего файла проверяете, нет ли ветки в дереве, если да - выводите, что найдено совпадение (я понял, что ищутся одинаковые последовательности во всех N файлов, а не в определенной паре из N файлов)...

 

можно ещё придумать хеш-функции последовательностей, по которым можно было бы определять подстроки... но это надо думать...

 

Да, именно так. Во всех файлах.
Вместо памяти подумываю использовать временный файл.

 

да не зачем... из первого файла вы формируете описанное выше дерево, и этого достаточно... считываете следующие файлы и проверяете по веткам дерева из первого файла... если последовательности найдены, сохраняете их... можно даже счетчик ввести, мол в скольких файлах какие ветки участвуют...

 

Rel
не забывайте, что необходимо эти деревья дополнять не достающими последовательностями из 2 - (n-1)-го файлов т.к. ТС не пишет, что последовательности задаются только первым файлом и обязаны присутствовать во всех файлах.

 

dyn
Данные текстовые или какие?

 

вот именно, что не нужно... читайте раньше:

то есть последовательности должны быть во всех файлах, а не в определенном количестве файлов из набора... то есть достаточно дерева из первого файла... дополнения последовательностей из последующих файлов в данном алгоритме означает, что такой последовательности не было в первом файле, а следовательно её не требуется учитывать...

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

 

Последовательность должна присутствовать именно во всех файлах.
Файлы бинарные. ЕХЕ и ДЛЛ. Задача: вычленить сигнатуру.

 

пишите очередной фрисорц антивирус?)))

 

Скорее полу ручной онализадор семплов. Как вычлените, поделитесь наработками?)

 

VaZoNeZ
Именно оно! =)
Выложу в проджектс

 

а для чего он нужен? что потом делать с семплами?

 

Отправлять в другой отдел, где это все запихают в базы и зальют как обновление к антивирусу. dyn, так?

 

Наполовину.
Отправлять в другой отдел, где прогерры доработают свой софт так, чтобы этих сигнатур не было.

По поводу дерева. Можно приблизительный алго?
Т.к. при моей реализации 4 гб оперативы не хватает

 

Rel

если так, то в худшем случае у нас будет first_file_size-12 различных последовательностей из 12 байт, first_file_size-11 -"- из 11 байт и т.д. не проще уж тогда загрузить первый файл в память целиком, а уже в нем искать последовательности, на которые будут нарезаны последующие файлы. для ускорения этого процесса можно использовать таблицу смещени для различных байт (такая таблица обойдется в 4 раза больше размера первого файла по памяти вместо 12-ти в случае с деревом только на 12-байтовые последовательности)
a:array [256] of array [] of longword
for i:=low(a[d[0]]) to high(a[d[0]]) do
плюс из этой таблицы можно выбросить все смещения повторяющихся последовательностей.

 

dyn
Берёшь самый короткий файл. Генерируешь файл содержащий все 12-байтные последовательности. Сортируешь этот файл удаляя все дубликаты. Потом берёшь следующий файл, точно так же генерируешь все последовательности и сортируешь их. Ну а далее проходишь по полученным спискам и оставляешь только элементы присутствующие в обоих списках. Или их общий префикс, если он не короче 4х байт. Потом берёшь третий файл и поступаешь с ним точно так же как со вторым. Когда список начнёт помещаться в память, можно добавить к элементам счётчик максимально совпадающей длины префикса, а следующие файлы грузить блоками, сортировать блоки, а потом последовательно проходить по ним и обновлять счётчики. Когда все блоки очередного файла будут обработаны, сжимаешь список удаляя записи для которых совпало менее 4х байт. И приступаешь к следующему файлу. В общем всего придётся сделать не более log2(max(file.size)) проходов по файлам.

 

с деревом интереснее... и мне кажется, что будет быстрее... единственное, что действительно стоит добавить, это формировать дерево не по первому файлу, а по самому короткому:

и удалять ветки, которые не были найдены в последующих файлах:

и если делать на динамических двусвязных списках, то существенного проигрыша по памяти не будет...

 

Black_mirror

Это, на мой взгляд, и есть то самое решение "в лоб".

С деревом тоже может все оказаться не так эффективно, как видится с первого взгляда, хотя проэксперементировать не мешало бы. В любом случае, если размер сигнатур превысит какое-то разумное количество (те оговоренные 12 байт), то имеет смысл смотреть в сторону хранения хешей в узлах дерева, а не самих значений.

Однозначно, тут еще надо задуматься об оптимизации тонких и неочевидных моментов алгоритма (к примеру: отложенное удаление узлов, заранее выделенный пул узлов и т.д.) + оптимизации самого кода.