Алгоритм нечеткого сравнения файлов

← →
Novice (2007-05-03 12:08) [0]

Для сравнения двух отдельно взятых файлов пользовался такой функцией:

function CompareFiles(Filename1,FileName2:string):longint;
{
0 - не найдено отличий,
-1 - ошибка файла 1
-2 - ошибка файла 2
-3 - другие ошибки
}
const
Buf_Size=16384;
var
F1,F2:TFileStream;
i:longint;
Buff1,Buff2:PByteArray;
BytesRead1,BytesRead2:integer;
begin
Result:=0;
try
F1:=TFileStream.Create(FileName1,fmShareDenyNone);
except
Result:=-1;
exit;
end;
try
F2:=TFileStream.Create(FileName2,fmShareDenyNone);
except
Result:=-2;
F1.Free;
exit;
end;
GetMem(Buff1,Buf_Size);
GetMem(Buff2,Buf_Size);
try
if F1.Size> F2.Size then Result:=F2.Size+1
else if F1.SizeF1.Position) and (Result=0) do begin
BytesRead1 :=F1.Read(Buff1^,Buf_Size);
BytesRead2 :=F2.Read(Buff2^,Buf_Size);
if (BytesRead1=BytesRead2) then begin
for i:= 0 to BytesRead1-1 do begin
if Buff1^[i]< > Buff2^[i]
then begin
result:=F1.Position-BytesRead1+i+1;
break;
end;
end;
end else begin
Result:=-3;
break;
end;
end;
end;
except
Result:=-3;
end;
F1.Free;
F2.Free;
FreeMem(Buff1,Buf_Size);
FreeMem(Buff2,Buf_Size);
end;

Недавно возникло две задачи:
1. Взять два разных по размеру файла и определить, что они практически идентичны. К примеру, две версии одного MP3-файла. Только у одного из них заполнены ID3-тэги, а у другого нет. Разница всего лишь в 32-64 байта, в то время как основная масса 3-7 мб одинакова.
2. Сравнивать нужно много файлов. Строго говоря, нужно найти все дублирующиеся файлы на одном разделе жесткого диска.
Следовательно, я полагаю, что потребуется более быстрый алгоритм, нежели приведенный мною.

У кого-нибудь есть соображения по данным вопросам?

← →
Reindeer Moss Eater © (2007-05-03 12:13) [1]

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

Сначала надо определиться что считать дублирующимися файлами.
Например в одном файле трек №1, во втором трек №2.
А в третьем оба трека.

← →
Reindeer Moss Eater © (2007-05-03 12:15) [2]

В одном файле произведение с битрейтом 256, а в другом то же самое произведение с битрейтом 192.

← →
Novice (2007-05-03 12:25) [3]

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

>>Например в одном файле трек №1, во втором трек №2.
>>А в третьем оба трека.
Каждый из этих файлов не имеет дубликатов среди двух оставшихся.

← →
Reindeer Moss Eater © (2007-05-03 12:39) [4]

>когда в них различается не более определенного количества байт.

Ну стало быть ты знаешь как искать дубликаты.
В чем тогда вопрос?

← →
Novice (2007-05-04 08:01) [5]

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

> Возможно ли его как-то оптимизировать?

Возможно. Выбросить и написать заново (как вариант - поискать готовый в интернете)

> Возможно ли его как-то оптимизировать?

1. Memory mapped file
2.
Циклы типа for i:= 0 to BytesRead1-1 do begin
if Buff1^[i]< > Buff2^[i]
then begin
result:=F1.Position-BytesRead1+i+1;
break;
end;
end;
переписать на Asme или юзать CompareMem()

Алгоритм нечеткого сравнения файлов Найти похожие ветки