Дубликаты файлов

[cya-st]

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

[SimpleSunny]

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

[cya-st]

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

[BlackTass]

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

[Пантер]

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

[zenden]

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

[spectre71]

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

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

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

[Пантер]

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

[spectre71]

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

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

[spectre71]

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

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

[Igors]

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

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

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

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

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

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

[spectre71]

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

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

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

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

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

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

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

[Igors]

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

[spectre71]

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

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

[Igors]

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

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