Russian Qt Forum

Помогите пожалуйста найти алгоритм поиска дубликатов файлов, для винды.

Если дубликаты точные, то можно предложить нечто подобное:
1. Создаешь QMap <int , QString>. int - Ключ для файла (md5, crc, sha-1, /etc), QString - путь к файлу
2. Рекурсивно сканируешь заданную директорию.
3. При нахождении файла считаем от него ключ, если он уже находится в QMap, то нашли дубликат, иначе заносим ключ в QMap.

Это надо наверное и еще в отдельный поток засунуть.

ну мд5 и ша1 в инт не влезут :) уж лучше ключом делать тоже QString с хекс представлением хеша

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

И всё же сначала нужно отобрать файлы с одинаковым размером.
А то считать хэш всех файлов подряд не есть быстро.

Ну, винда здесь ни причем. :)

1) Получаем и сравниваем canonic path(совпадение пути до файла).
2) Получаем  Размер файлов, если разный, разные файлы.
3) Если имем "hash" для файлов(например мд5), сравниваем, если разный, разные файлы.
4) Сравниваем файлы!
Из этого следует:
- Имеем список файлов.
- Получаем их canonic path, сортируем. Файлы с одинаковым canonic path - разные варианты записи path.
- Получаем список уникальных canonic path
- Получаем размеры файлов, сортируем.
- Для всех уникальных размеров - уникальны и файлы, отбрасываем.
- Для каждого файла с одинаковым размером получаем md5
- Если md5 - различны - различны и файлы, отбрасываем.
- Для одинаковых md5 сравниваем файлы побайтно.

md5 лучше пропустить и сразу сравнивать побайтно.

Нет, смотри:
1) Если файлов c одинаковым размером > 2 = N, то имем N!(факториал) сравнений файлов между собой.
2) Если файлов c одинаковым размером всего 2 и они достаточно большого размера, то при сравнении имеем плохой показатель попеременного чтении файлов с диска.
3) Если файлов c одинаковым размером всего 2 и они маленькие и не дефрагментированные, то если проц не занят(!), то при хорошем алгоритме "hash"(например md5), потери(по сравнению с прямым сравнением) несущественны.
Да (-) возможное повторное побайтное сравнение после идентичного "hash", но это маловероятно(в обычной ситуации, а в специфичных, предметных, требует соответствующих решений)

Маленькое уточнение:
- под "отбрасываем", подразумевается отбрасывание файлов уникальных по сравниваемой характеристике;
- дальнейшее сравнение производиться отдельно с каждым набором файлов с идентичной предыдущей характеристикой.

Можно посмотреть и "под другим углом". Предположим получили 100 файлов размером 1Mb. Давайте сразу сравнивать побайтно:

- загрузили файл №1, загрузили файл №2, сравнили. Не равны. Что делать? Загрузить файл №3, сравнить его с файлом №1? Ну тогда мы файл №2 грузим 99 раз,  файл №3 - 98 раз и.т.д. Быстро это явно не будет, в основном потому что надо все время открывать/закрывать файлы.

С др. стороны сразу молотить мд5 тоже не фонтан - надо прочитать все файлы до упора.

Я бы предложил: после выполнения обязательной сортировки по длине имеем "порции/пачки" файлов которые могут быть одинаковы. Для каждой пачки:

- открыть все файлы и считать первые 1К данных из каждого. Сортировать по этому ключу. Получаем новые "пачки", если размер = 1, дубликата нет, закрыть файл и исключить из рассмотрения

- загружаем следующий 1К данных и т. п.

Если ты заметил, я писал про "hash", а md5 приводил как пример. Можно и использовать  и более дешевые алгоритмы.
Вопрос в том нужно ли это? В типичной ситуации, мы уже на стадии разделения по размеру отсеем 99%(оценка от фонаря).
После "hash" (md5), мы отсеем от оставшихся еще 99,99999% (опять от фонаря).
Можно еще вводить и промежуточные "hash", в том числе и для первых N байт файлов(если файлы в пачке достаточно большие), это задача оптимизации(если требуется).
После всего, сравниваем оставшиеся файлы(в каждой пачке) между собой, но с удалением дубликата из списка  сразу после сравнения, чтоб не получить факториальную зависимость.

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

Что такое "оптимальное побайтовое сравнением"?

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

Я про это писал.

Какие есть функции в QT для генерации хеш? Или надо самому замутить (xor например)

Хбз, наверное есть?, я пока пользуюсь "openssl".

QCryptographicHash::hash()
qHash()

Я бы посоветовал 3-х уровневый отбор: размер, crc (qChecksum например), полное сравнение.
crc считается существенно быстрее криптографического хеша, но сильнее подвержен коллизиям.
С другой стороны отсеять с его помощью разные файлы проще, чем все их сравнивать. :)

Быстрее ли? При чтении файла частями по 9.24МиБ и расчете MD4/SHA1 хешей загрузка процессора E6550 не превышает 10%, а скорость ограничивается 100МиБ/с. Тут ограничивающим фактором выступает не мощность процессора, а ограничение I/O системы.

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

Впрочем проблема коллизий разрешается довольно просто: хеш нужно считать не от целого файла, а от блоков фиксированного размера. (Это не я придумал - в ed2k/AICH, BitTorrent клиентах это уже есть)

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

По поводу "замутить с xor" - это весьма ненадежно. Например если 2 байта переставлены местами, то xor дает тот же результат. Очень давно (по моему на AutoCAD 10) я видел что-то такое: байт вращается и добавляется к сумме, (сумма % 8) = вращение для следующего байта.

Если же клиент настаивает на "абсолютной точности" то соображения об "отсеивании" мало что дают. Пользователь купил драйв побольше и делает резервные копии раз в неделю. Имеем много одинаковых файлов, очевидно что дополнительные проверки работают в минус. Другой случай - есть много разных файлов одинакового размера. Но тогда побайтовое сравнение (аккуратно сделанное) должно быстро с этим разобраться.   

- это я к примеру сказал

Согласен. Фактически скорость вычисления MD5(openssl) в 2-3 раза быстрее чтения с диска, соответственно для вычисления контрольной суммы не имеет смысла использовать xor или подобные быстрые алгоритмы с высоким уровнем коллизий.
Мы решаем задачу по поиску дубликатов файлов и соответственно должны учесть все проблемы с этим связанные. Если решать задачу универсально, то можно составить такой алгоритм:

0) Имеем(получаем) список файлов(путей)
1) Получаем канонические пути, сортируем и отсеиваем дубликаты
2) Получаем размеры, сортируем и разделяем на пачки с одинаковым размером, отсеиваем уникальные
3) Далее работаем с каждой пачкой в которой файлы имеют одинаковый размер
4) Определяем sparthash и sfullhash, sparthash <= sfullhash, где
    sparthash - размер блока(куска большого файла) для вычисления частичного хеша(например от начала файла)
    sfullhash  - максимального размер файла для вычисления хеша на всем файле
5) Для пачек с размером файлов  > sfullhash, вычисляем hash на размере sparthash, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
6) Далее с каждой пачкой с размером файлов  <= sfullhash и пачек полученных на шаге 5 работаем одинаково
7) Вычисляем hash для каждого файла пачки, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
8.) Теперь имеем пачки с одинаковым hash, с очень очень высокой вероятностью они одинаковы, но мы не можем этого гарантировать! Далее работаем с каждой такой пачкой
9) Делаем побайтное сравнение файлов в пачке, но не каждого с каждым, а последовательно:
    1-й со 2-м, 2-й с 3-м, 3-й с 4-м, ... N-1 c N
10) С очень очень высокой вероятность мы получим, что 1==2==3==4==...==N, и таким образом удостоверимся в идентичности файлов
11) В редких ситуациях будем иметь что то подобное:  1==2<3==4>...<N.
12) Для однознаковых последовательностей, по знакам "<" и ">", например:
     1==2<3==4<...<N. или 1==2>3==4>...>N.
     Все тривиально!
13) Для неоднознаковых, убираем дубликаты, и сортируем. Алгоритм сортировки выбираем с наименьшим кол-вом сравнений элементов, кол-во перемещений роли не играет. Во время сортировки(и до нее - для исходной последовательности) запоминаем отношения сравниваемых файлов между собой(<>=), чтобы не делать повторные сравнения во время сортировки и после нее.
14) Шаг 13 очень маловероятен, но возможен и должен оптимизироваться только по кол-ву попарных сравнений - как можно меньше.

Уточнение к шагу 13.
Имем последовательность типа 1==2<3==4>...<N.
После того как убрали дубликаты - имем 2<4>...<N. - всего M файлов
Заводим таблицу размера M*М.
1) Пописываем в нее уже известные (2<4>...<N) комбинации,
2) Пописываем вычисляемые по известным, например: имеем a<b<с => a<b, a<c, b<c.
Во время сортировки, при сравнении:
3) сперва смотрим в таблице и если есть значение - берем из нее.
4) если нет значения, сравниваем файлы и заносим заначение в таблицу. После чего для нового значения прописываем вычисляемые
 в таблицу, как в пункте 2.

Я бы делал попроще и строил бы данные примерно так

Операторы == и < сравнивают длины и если равны, то буфера чтения. Если произошла ошибка чтения (а она для системных файлов будет) то запоминаем mError, такой файл никому не равен. Если число открытых файлов слишком велико - ничего не попишешь, придется открывать/читать/закрывать (для этого держим mPos)

Алгоритм:

- на каждом шаге имеем имеем сортированный массив CFileInfo. Находим все интервалы (пачки из 2 и более) в которых все файлы (пока) равны. Если файлы полностью прочитаны (полное сравнение достигнуто) присваиваем очередное ID. Иначе добавляем все найденные интервалы в массив интервалов.

- берем первый интервал из массива интервалов. Допустим это файлы [0..10]. Открываем все эти 10 файлов, заполняем буфера. Сортируем пачку из 10 файлов, теперь они могут быть уже не равны. Возвращаемся к началу с той разницей что работаем в интервале  [0..10].

- массив интервалов пуст - все сделано

Не вижу никакого смысла одновременно открывать и сравнивать больше 2-х файлов, это не эффективно. Тем более не имеет смысла держать больше 2-х буферов памяти для чтения файлов, их нужно ровно 2 и создать один раз для всего процесса сравнения.
С обработкой ошибок согласен. Их несколько.
1) Файл невозможно открыть или дочитать до конца
2) Файл был иэменен до открытия.
3) Файл открыт на запись другим процессом или файл изменен после открытия.
В зависимости от условий здачи, необходимо либо считать эти файлы уникальными либо обрабатывать повторно и сравнивать с обработанными.
С 3-м пунктом мне не понятно, есть ли стандартные средства(и желательно в QT) для отслеживания таких ситуаций?

Это мы уже обсуждали
Все соображения об отсеивании бесспорны но нетрудно найти диск на котором 100 (или больше) одинаковых и достаточно больших файлов. И с 2-мя буферами из этой трясины никак не выбраться. Очевидно нужно читать много файлов параллельно и небольшими кусками. Это можно спокойно написать за день. А к тому что Вы предложили - и подступиться страшно  :)

Открытие/закрытие файла быстрее по сравнению с чтением оптимального фрагмента файла(размер внутреннего кеша жесткого диска) даже при условии отсутствия дефрагментации!
Пожалуйста прочитай внимательно то что я писал - 13 пунктов + доплнение. Там нет проблемы с побайтным сравниванием всех комбинаций пар(в этом нет необходимости) файлов в каждой пачке, такая ситуация невероятна(ее можно создать только искусственно, и то, при этом кол-во сравнений не превысит O(N*log(N)))! В типичном случае, который гораздо больше вероятности 0,9999999999 мы для X = 10000000000 файлов в пачке, выполним X побайтных сравнений!

Вот мой вариант (примерно 300 строк). Вполне возможно где-то наврал + нужно добавить индикатор (progress bar).
http://www.2shared.com/file/7661840/6595e4cd/filedupcpp.html (http://www.2shared.com/file/7661840/6595e4cd/filedupcpp.html)(не смог приаттачить здесь).
Если есть желание - делайте Ваш вариант и сравним. А то слово за слово - только людей утомляем  :)

Edit: так и есть, наврал :) В CloseFile нужно добавить mFile->close()

Edit2: Отрихтовал, убрал пару баговhttp://www.2shared.com/file/7672990/fe2c76e9/filedup_fixcpp.html (http://www.2shared.com/file/7672990/fe2c76e9/filedup_fixcpp.html)

Имеем 2 разных файла - 250bytes и 37.6KB
1) 2*2500 =  5000 файлов - 8 секунд
2) 2*5000 = 10000 файлов - 38 секунд
3) 2*10000 = 20000 файлов - 228 секунд

Имеем зависимость С1*O(n*n) + С2*O(n*log(n))  вместо С1*O(n) + С2*O(n*log(n)), где C1 - для чтения файлов, а C2 - для сортировок списков, C2 в типичном случае много меньше C1.