Сравнение файлов

← →
vasIZmax © (2007-09-20 10:33) [0]

Столкнулся с такой задачкой.
В папке порядка 17 000 файлов. Но среди них попадается большое количество дубликатов, т.е. полностью одинаковые, кроме имени. Как можно удалить дубликаты?
Думаю реализовывать так: через findfirst, findnext. Берем первый файл и начинаем сравнивать по-байтово(об этом тож сейчас думаю  как реализовать) его со всеми по очередно. Если полностью схожи, то дубликат удаляем.
Но,имхо, такой метод будет очень долгим? Может по другому как?

← →
MBo © (2007-09-20 10:35) [1]

размеры разные?

← →
clickmaker © (2007-09-20 10:36) [2]

если размеры одинаковые, начинать сравнивать побайтово: читать кусками, потом CompareMem

← →
vasIZmax © (2007-09-20 10:44) [3]

> MBo © (20.09.07 10:35) [1]

если бы  попадаются много (!) одинаковых. При чем размер может быть одинаковый, а содержимое  разное.

> clickmaker © (20.09.07 10:36) [2]

ок, сейчас посмотрю

← →
Sergey13 © (2007-09-20 11:13) [4]

Может подумать вокруг контрольной суммы?

← →
Anatoly Podgoretsky © (2007-09-20 11:44) [5]

> Sergey13 (20.09.2007 11:13:04) [4]

Есть смысл, при данной задаче можно сильно ускориться.

← →
clickmaker © (2007-09-20 11:54) [6]

> [5] Anatoly Podgoretsky © (20.09.07 11:44)

с чего бы?
сравнение первых, скажем, 100 байтов будет медленее расчета CRC?

← →
Jeer © (2007-09-20 11:56) [7]

Sergey13 © (20.09.07 11:13) [4]
Anatoly Podgoretsky © (20.09.07 11:44) [5]

Тоже смысла не вижу, т.к. comparemem вылетит с false на первом же байте.

← →
stanislav © (2007-09-20 13:22) [8]

clickmaker © (20.09.07 11:54) [6]
Рсчет CRC Будет произведен 17 000, а сравнивать побайтово 17000^2!

← →
Плохиш © (2007-09-20 13:26) [9]

> а сравнивать побайтово 17000^2!

Ну если с логикой проблемы, то, да, сравнивайте одни и те же файлы по два раза :-)

← →
Slym © (2007-09-20 13:34) [10]

Я делал такую паделку...
1. Сканил диск в БД, яля кеширование
ShortName|Type|FullPath|Size|CRC
2. Дальше средствами SQL искал жертву аля
2.1. SELECT FullPath GROUP Type,Size,CRC HAVING Count(FullPath)>1
Тут удаление можно на автомате приделать, оставлять только 1 файл
2.2. SELECT FullPath GROUP ShortName HAVING Count(FullPath)>1
этот запрос выводил в Grid с фоном вычисляемыл из CRC
т.е. название одно, а разница содержания сразу бросается в глаза
3. Удаляю жертву, удаляю запись о ней

← →
stanislav © (2007-09-20 13:35) [11]

Плохиш © (20.09.07 13:26) [9]
ок не 17000^2? но больше 17000

← →
Slym © (2007-09-20 13:38) [12]

Повторное сканирование частично берет данные из предыдущего сканирования...
т.е. при совпадении ShortName|Type|FullPath|Size контрольная сумма не пересчитывается

← →
Anatoly Podgoretsky © (2007-09-20 13:39) [13]

> clickmaker (20.09.2007 11:54:06) [6]

> сравнение первых, скажем, 100 байтов будет медленее расчета CRC?

А разница в 101 байте.

← →
Anatoly Podgoretsky © (2007-09-20 13:39) [14]

> Jeer (20.09.2007 11:56:07) [7]

А если на миллионном и таких файлов много?

← →
Slym © (2007-09-20 13:42) [15]

stanislav © (20.09.07 13:35) [11]
площадь половины (по диагонали) квадрата т.е. 17000^2/2

← →
stanislav © (2007-09-20 13:47) [16]

Slym © (20.09.07 13:42) [15]
может меньше т.к. если совпадения будут допустим с 5 файлами они удаляться :-)

← →
Slym © (2007-09-20 13:49) [17]

Для параноиков: можно выычислить различные свертки- CRC,MD5,SHA
если для 2х файлов совпали CRC,MD5,SHA то вероятность что файл одинаковые как предел слева к 1

← →
Jeer © (2007-09-20 14:13) [18]

> Anatoly Podgoretsky © (20.09.07 13:39) [14]
>
> > Jeer (20.09.2007 11:56:07) [7]
>
> А если на миллионном и таких файлов много?

А как тебе такая статистика по реальному тесту ?

Время ( *E6 ticks) выполнения операций Comparemem и CRC32 над буферами
в памяти с объемом в Mbyte :
Size___T(Compare)___T(CRC32)

0.04___0.05______0.07
0.256__1.3_______4.5
1______3.6_______18
10_____34________185
100____313_______1870

Как видим, для обоих случаев зависимость линейная, но коэффициент у CompareMem (t = 3.4*Size) лучше, чем у CRC (t = 18.5*Size) более чем в 5 раз.

P.S.
Реализация CRC32 стандартная, через table и asm
P.P.S
Понятно, что можно и CRC16, но возможны уже коллизии при больших size.

← →
Sergey13 © (2007-09-20 14:14) [19]

> [0] vasIZmax © (20.09.07 10:33)

Это одноразовая работа или постоянная?
Если постоянная, то прикрутив к программе БД с запомненными CRC-шками можно достаточно легко автоматизировать процесс на 100%.
Если одноразово - ИМХО пофиг как сравнивать.

← →
Jeer © (2007-09-20 14:18) [20]

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

← →
Sergey13 © (2007-09-20 14:29) [21]

http://www.google.ru/search?hl=ru&q=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA+%D0%B4%D1%83%D0%B1%D0%BB%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D0%B2+%D1%84%D0%B0%D0%B9%D0%BB%D0%BE%D0%B2&lr=

дает дофига ссылок на готовые программы (на всякий случай).

← →
Slym © (2007-09-20 14:29) [22]

Jeer © (20.09.07 14:13) [18]
это для памяти тесты...
а да HDD все по другому...
зависимость считанной с HDD информации (количество обращений к файлам)
(при условии равенства размера файлов)
CRC - n
Compare n^2/2
т.е при наличии 10 файлов равной длинны с отличием в последрем байте
имеем
CRC - 10, Compare - 50, т.е. разница в 5 раз
при 100 файлах - 100 и 5000 разница в 50 раз:)

← →
Jeer © (2007-09-20 14:44) [23]

> Slym © (20.09.07 14:29) [22]

А при чем тут HDD ?
Ситуация аналогична при размещении 17000 буферов в памяти. Стоимость операций compare квадратично, CRC линейна.
Очевидно, что в общем случае CRC выгоднее, но в частных случаях может быть оптимальнее Check_size + Compare .

← →
Anatoly Podgoretsky © (2007-09-20 15:27) [24]

> Jeer (20.09.2007 14:13:18) [18]

Коллизии возможно, но мало вероятны, но если волную коллизии, то применить или CRC64 или MD5, в любом случае это на порядки быстрее сравнения всех файлов одинаковой длины со всеми. За раз посчитали CRC в сортированом списке и разом удалили дубли.

← →
Anatoly Podgoretsky © (2007-09-20 15:28) [25]

> Sergey13 (20.09.2007 14:14:19) [19]

На 17000 файлах и пофиг, дай бог если сравнит за несколько дней и то при условии оптимизировано алгоритма.

← →
Anatoly Podgoretsky © (2007-09-20 15:30) [26]

> Jeer (20.09.2007 14:18:20) [20]

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

> Jeer (20.09.2007 14:44:23) [23]

Автор это легко может проверить, просканировав папку и посчитав процент совпадения длин.

> [25] Anatoly Podgoretsky © (20.09.07 15:28)

Ну и что, что моя программа работает на полчаса дольше? Я ее запущу на полчаса раньше и все.
(с) старый анекдот
8-)

> Anatoly Podgoretsky © (20.09.07 15:30) [26]

> Если же количество файлов одинаковой длины стремится к единице,
> то сравнение будет быстрее.
>

О чем и речь - все определяется статистикой файлов, их длиной и точками несовпадений при одинаковых длинах.
Это может только автор или специально поставленный эксперимент.:)

> Jeer (20.09.2007 16:07:29) [29]

У него для этого есть благоприятные возможности, все 17000 файлов в одной папке, не надо заморачиваться рекурсией, сортировать надеюсь он умеет. Работы минут на 5, максимум 30.

Бум ждать:)

> Jeer (20.09.2007 16:25:31) [31]

И я бы на его месте слабал бы простенькую программку анализа.

> [24] Anatoly Podgoretsky © (20.09.07 15:27)
> Коллизии возможно, но мало вероятны, но если волную коллизии,
> то применить или CRC64 или MD5,

А не проще применить самый быстрый алгоритм (по логике CRC16) и каждое из 65536 ложных срабатываний проверить побайтово?

Значит вот что получилось, делал побайтово:-).

//перемещение файла function MoveFile(const fromdir, files: string): Boolean; var fos: TSHFileOpStruct; begin ZeroMemory(@fos, SizeOf(fos)); with fos do begin wFunc := FO_MOVE; fFlags := FOF_FILESONLY; pFrom := PChar(fromDir + #0); pTo := PChar(files) end; Result := (0 = ShFileOperation(fos)); end; //сравнение function CompareFiles(FirstFile, SecondFile: string): Boolean; var f1, f2: TMemoryStream; begin Result := false; f1 := TMemoryStream.Create; f2 := TMemoryStream.Create; try f1.LoadFromFile(FirstFile); f2.LoadFromFile(SecondFile); if f1.Size = f2.Size then Result := CompareMem(f1.Memory, f2.memory, f2.Size); finally f2.Free; f1.Free; end end; //проверяю, не пуста ли папка function TestSize(path,mask:string):boolean; var rec:tsearchRec; begin FindFirst(Path+mask, faAnyFile, rec); if (rec.name <> "") then result:=true else result:=false; end; //поиск дубликатов procedure SeachDestroy(patch,path2,mask:string); var f1,fmain: TSearchRec; SizeDir:int64; begin if testsize(patch,mask) then begin FindFirst(Patch+mask, faAnyFile, F1); if (F1.name <> "") then begin fmain.Name:=f1.Name; fmain.Size:=f1.Size; while FindNext(F1) = 0 do if (fmain.Size=f1.Size) then begin if CompareFiles(patch+fmain.name,patch+F1.name) then deletefile(patch+f1.Name); end; end; Movefile(patch+fmain.Name, path2); FindClose(F1); SeachDestroy(patch,path2,mask); end; end; //использование procedure TForm1.Button2Click(Sender: TObject); var Path,Path2,mask: string; begin Path := edit1.Text; Path2:= edit2.Text; mask:="*.gif"; SeachDestroy(path,path2,mask); showmessage("All of files are treated"); end;

ЗЫ. вечерком посижу над crc

> vasIZmax (20.09.2007 20:34:34) [34]

> pFrom := PChar(fromDir + #0);
> pTo := PChar(files)

Почему во второй строке нет + #0
Добавь

Да, и в указанном варианте от рекурсии надо уйти.
из procedure SeachDestroy(patch,path2,mask:string); удалить строку SeachDestroy(patch,path2,mask);
и подправить
procedure TForm1.Button2Click(Sender: TObject); var Path,Path2,mask: string; begin Path := edit1.Text; Path2:= edit2.Text; mask:="*.gif"; repeat SeachDestroy(path,path2,mask); until testsize(path,mask)=false end;

иначе переполнение стека при большом количестве файлов

procedure SeachDestroy(patch,path2,mask:string); var f1,fmain: TSearchRec; SizeDir:int64; begin if testsize(patch,mask) then begin FindFirst(Patch+mask, faAnyFile, F1); if (F1.name <> "") then begin fmain.Name:=f1.Name; fmain.Size:=f1.Size; while FindNext(F1) = 0 do if (fmain.Size=f1.Size) then begin if CompareFiles(patch+fmain.name,patch+F1.name) then deletefile(patch+f1.Name); end; end; Movefile(patch+fmain.Name, path2); FindClose(F1); SeachDestroy(patch,path2,mask); end; end;
1. пропускаешь первый файл FindFirst и сразу FindNext (хотя первым идет сам каталог или его парент)
2. patch - обычно path :) хотя может по немецки както
3. в подкаталоги не заходишь? почему? и что за странная рекурсия внутри одного каталога - обычно рекурсия для подкаталогов, а у тебя внутри одной папки :)
нафига 2 FindFirst?
if testsize(patch,mask) then// превращается в FindFirst begin FindFirst(Patch+mask, faAnyFile, F1);
4. если рекурсия для "перемножения" файлов (а оно так и есть) то рекурсия "очень глубокая" получится как правильно заметил vasIZmax © (20.09.07 21:07) [36]
но
repeat
SeachDestroy(path,path2,mask);
until testsize(path,mask)=false
означает "пока все не "загасишь", не возвращайся"?

5. "удаление" файлов в одну папку грозит потерей файлов с одним именем из разных подкаталАгов, останется один последний...

Сравнение файлов Найти похожие ветки