6

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

Я не прошу предоставить мне кусок готового кода или каким-либо иным способом полностью реализованное задание, буду благодарен за любую полученную ценную информацию относительно данного вопроса.

2
  • 5
    имхо лучше воспользоватся готовым решением, в противном случае попахивает изобретением велосипеда. найдите любую утилиту для командной строки и запускайте ее из своей программы.
    – jmu
    26 авг 2012 в 21:41
  • @jmu, а есть готовое решение, которое ещё и одинаковые папки найдёт?
    – Qwertiy
    1 янв 2016 в 13:27

4 ответа 4

9

Вот решение в-лоб:

  1. Обходим все каталоги рекурсивно, сохраняем (path, filesize) в таблицу базы данных.
  2. Сортируем собранную таблицу по filesize, делаем выборку по всем записям где filesize неуникально.
  3. Для каждой пачки файлов с одинаковым filesize вычисляем хеш, проверяем на равенство.
  4. ???
  5. PROFIT
6
  • сдается мне что читать байты до первого несоответствия быстрее хеша будет, хотя для пачки не знаю как по затратам если она большая
    – aknew
    26 авг 2012 в 20:18
  • Здесь еще нужно глубже понять статистику дубликатов, откуда и почему они берутся, где теоретически могут появится, какой их средний размер, чтобы ускорить первый и второй пункт.
    – igumnov
    26 авг 2012 в 20:22
  • @aknew Не думаю, что так уж много файлов с одинаковым размером, чтобы думать о скорости подсчета хэша. 26 авг 2012 в 20:35
  • ну как бы если файлы большого размера, то это может быть весьма критично, хотя все конечно зависит от задачи
    – aknew
    26 авг 2012 в 20:50
  • 3
    Преимущество хэша в том, что он считается всего один раз. Если им пренебречь и сравнивать файлы напрямую, то получится как раз та самая ситуация, в которой комбинаторика рано или поздно обязательно побеждает человека. Причём в данном случае скорее рано, чем поздно.
    – Shamov
    27 авг 2012 в 4:48
4

fdupes не смотрели? У него есть такой алгоритм и он вроде уже проверен временем

3

Здесь какие-то люди уже 10 лет публикуют такое Windows приложение. Может Вам стоит связаться с ними.

1
  • В Тотал Командере кстати встроенный поиск дубликатов. Очень удобно.
    – ReinRaus
    26 авг 2012 в 21:14
1

Hash для всего файла считать - плохая идея, если есть большие файлы

Я сделал так: Для группы файлов с одинаковым размером делишь на группы по первого очередного байта в файле, для групп размером > 1 читаешь следующий байт и так по рекурсии Естественно, считывание байт должно быть буфферизованно, для каждого файла считываешь блоки в неск. килобайт, пототом оттуда выбираешь побайтно

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.