Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Novice © (2007-05-03 12:08:00)
Для сравнения двух отдельно взятых файлов пользовался такой функцией:

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. Сравнивать нужно много файлов. Строго говоря, нужно найти все дублирующиеся файлы на одном разделе жесткого диска.
Следовательно, я полагаю, что потребуется более быстрый алгоритм, нежели приведенный мною.

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

clickmaker (2007-05-04 11:53:00) [1]

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

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()

Игорь Шевченко (2007-05-04 11:50:00) [2]

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

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

Novice (2007-05-04 08:01:00) [3]
Вопрос в скорости работы. Как я сказал выше, требуется искать дубликаты всех файлов, имеющихся на заданном разделе. Хорошо, если этих файлов там будет сотня-другая. Тогда вполне можно применить алгоритм, приведенный выше. Но если этих файлов будет несколько десятков тысяч... Я так думаю, с текущим алгоритмом это затянется надолго. Возможно ли его как-то оптимизировать?

Reindeer Moss Eater (2007-05-03 12:39:00) [4]
>когда в них различается не более определенного количества байт.

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

Novice (2007-05-03 12:25:00) [5]
>>Сначала надо определиться что считать дублирующимися файлами.
Я так полагаю, что два файла являются практически идентичными, когда в них различается не более определенного количества байт.
К примеру, программа

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

Reindeer Moss Eater (2007-05-03 12:15:00) [6]
В одном файле произведение с битрейтом 256, а в другом то же самое произведение с битрейтом 192.

Reindeer Moss Eater (2007-05-03 12:13:00) [7]
Строго говоря, нужно найти все дублирующиеся файлы на одном разделе жесткого диска.

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

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »