Как лучше реализовать поиск в файле?

[tar_tre]

Задача:
есть 2 бинарных файла. предполагается, что в каждом существует одна и та же последовательность байт, только по разному смещению. нужно найти смещение в каждом файле и длину наибольшей последовательности.
Вопрос:
Какими средствами лучше организовать такой поиск? Нет ли стандартных команд, позволяющих сделать это?

[Protopopulus]

существует одна и та же последовательность байт, только по разному смещению. нужно найти смещение в каждом файле и длину наибольшей последовательности.

А теперь для тех кто в танке

[tar_tre]

А теперь для тех кто в танке

всё очень просто.есть 2 файла с одинаковыми данными и разными заголовками. визуально определить, где кончается заголовок и начинаются данные сложно. нужна программа, которая сопоставит эти файлы и даст ответ:
к примеру,
в первом файле данные начинаются с позиции 1846
во втором файле данные начинаются с позиции 1684
длина данных 1034756343 байт
(длина тоже важна, т.к. окончания у файлов тоже разные)
просто нужно найти наибольшую общую последовательность байт

[Protopopulus]

Возможно множество совпадающих байт... Так что задачка не из легких, имхо.

[tar_tre]

Возможно множество совпадающих байт...

маленькие последовательности (менее 1кб) можно изначально не принимать во внимание. файлы то большие (4,5 М), и данные занимают бОльшую часть.

[Lion-Simba]

Собираем песочницу:

Код: [Выделить]

simba@dahari:~$ mkdir fs
simba@dahari:~$ cd fs
simba@dahari:~/fs$ cat /dev/random | head -c 20 > chunk1
simba@dahari:~/fs$ cat /dev/random | head -c 100 > chunk2
simba@dahari:~/fs$ cat /dev/random | head -c 200 > chunk3
simba@dahari:~/fs$ cat chunk1 chunk2 > data1
simba@dahari:~/fs$ cat chunk1 chunk3 > data2
simba@dahari:~/fs$ cat /dev/random | head -c 30 > header1
simba@dahari:~/fs$ cat /dev/random | head -c 40 > header2
simba@dahari:~/fs$ cat header1 data1 > file1
simba@dahari:~/fs$ cat header2 data2 > file2
simba@dahari:~/fs$ ls -l
итого 36
-rw-r--r-- 1 simba simba  20 2009-07-19 11:55 chunk1
-rw-r--r-- 1 simba simba 100 2009-07-19 11:57 chunk2
-rw-r--r-- 1 simba simba 200 2009-07-19 11:58 chunk3
-rw-r--r-- 1 simba simba 120 2009-07-19 11:58 data1
-rw-r--r-- 1 simba simba 220 2009-07-19 11:58 data2
-rw-r--r-- 1 simba simba 150 2009-07-19 12:00 file1
-rw-r--r-- 1 simba simba 260 2009-07-19 12:00 file2
-rw-r--r-- 1 simba simba  30 2009-07-19 11:59 header1
-rw-r--r-- 1 simba simba  40 2009-07-19 11:59 header2

Решаем задачу:

Код: [Выделить]

simba@dahari:~/fs$ grep -o -b "`cat chunk1`" file1|grep -o -P -e "^[0-9]+"
31
simba@dahari:~/fs$ grep -o -b "`cat chunk1`" file2|grep -o -P -e "^[0-9]+"
41
Ну а длину данных вычислить элементарно: размер файла минус смещение.
Пользователь решил продолжить мысль 19 Июля 2009, 09:17:19:Аха! А вот теперь я понял условие задачи.
Будем думать дальше.

[Protopopulus]

Аха! А вот теперь я понял условие задачи.

Я сначала примерно о том же подумал

[Lion-Simba]

А вот нагуглил: http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C

[tar_tre]

А вот нагуглил: http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C

Алгоритм Машека и Патерсона отличная вещь. Хорошее время покажет на длинных файлах. Только я долго врубаться в него буду. Попробую, для начала, решить свою задачу дедовским методом. Мне ведь всего-то 1 раз надо программу использовать.
Пользователь решил продолжить мысль 19 Июля 2009, 18:35:49:Придумал довольно быстрое решение:
У меня частный случай, поэтому крутые алгоритмы можно и не применять.
Возьму из средины 2-го файла паттерн, размером 1 кб (такого размера должно быть достаточно, т.к. вероятность, что встретятся 2 абсолютно одинаковых паттерна длиной 1кб в одном файле в моём случае очень мала).
Узнаю где этот паттерн в файле 1. По теории, он тоже должен быть близко к средине 1-го файла.
Таким образом я узнаю смещение этого паттерна в обоих файлах.
От этого смещения пойду к началу и концу файлов, сравнивая их между собой побайтно.
Таким образом узнаю смещения и длину общей последовательности байт в обоих фалах.ъ
Начал делать, но дело встало сравнении. Функция index() возвращает -1. Посмотрите, что не так. Может я недопонимаю что-то?

Код: [Выделить]

#!/usr/bin/perl
my $FileName1 = "file1";
my $FileName2 = "file2";
binmode STDOUT;

open(DAT1, $FileName1);
open(DAT2, $FileName2);
binmode DAT1;
binmode DAT2;
while (read(DAT1, $buf1, 1024)){
$f1.= $buf1;
}   
print STDOUT length($f1) . " bytes read from: " . $FileName1 . "\n";

while (read(DAT2, $buf2, 1024)){
$f2.= $buf2;
}   
print STDOUT length($f2) . " bytes read from: " . $FileName2 . "\n";

$l2 = length($f2);
$i = int($l2 / 2)-512;
$j = int($l2 / 2)+512;
$st = substr($f2,$i,$j);
print STDOUT index($f1,$st). " " . $i . " " . $j;


Код: [Выделить]

ls -l
итого 11700
-rw------- 1 pars pars       2 2009-07-19 17:55 1
-rw-r--r-- 1 pars pars 3971150 2009-06-03 23:37 body  -тело
-rw-r--r-- 1 pars pars    2512 2009-06-28 11:57 end1  -окончания
-rw-r--r-- 1 pars pars    8540 2009-06-28 11:57 end2
-rw-r--r-- 1 pars pars 3974920 2009-07-19 14:14 file1  готовые файлы с разными заголовками и окончаниями
-rw-r--r-- 1 pars pars 3980867 2009-07-19 14:16 file2
-rw-r--r-- 1 pars pars    1258 2009-06-28 11:57 head1  -заголовки
-rw-r--r-- 1 pars pars    1177 2009-06-28 11:57 head2

[unimix]

просто нужно найти наибольшую общую последовательность байт

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

Хотя, может я не совсем понял решаемую задачу для этого частного случая.

[tar_tre]

просто нужно найти наибольшую общую последовательность байт

 Насколько я понял, сложнее перебрать все варианты совпадений если не известна необходимая последовательность.

Хотя, может я не совсем понял решаемую задачу для этого частного случая.

ты всё правильно понял. решая "влоб" эту задачу, при файлах в 10Мб, можно ждать вечность. но особенность этого случая в том, что данные (т.е. последовательность) занимают примерно 95% от всего файла. поэтому, куда не ткни пальцем, с вероятностью 95% попадёшь в участок последовательности. а если метиться в середину файла, то 100%. следовательно можно из средины "вырезать" образец, который потом сравнивать с другим файлом. отсюда и привязка к смещению.