Поиск файлов-дубликатов

[The Nameless One]

Приветствую!

Прошу подсказать несколько пунктов.

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

2. Т.е. нужно создать поиск фалов на диске С, при этом надо запомнить все файлы, которые повторяются, вывести их в списке вместе с их путями и размерами. Поиск только по размерам, названиям и датам изменения/создания. Содержимое не нужно.

3. Поиск надо сделать отдельным тредом. С прогрессбаром и возможность поставить на паузу\продолжить.


Что я имею: из WinApi знаю только создание окна, кнопки, ф-ию обработки сообщений и некоторые моменты из GDI, (HDC контекст графического устройства, рисование простых вещей).

Про работу с файлами  в win32api ещё не, а так же не знаю многопоточность.

Мне реально за день-два написать такую прогу?

Что мне читать?

[Вад]

Для начала, читать тему https://forum.shelek.ru/index.php/topic,21719.0.html
Судя по всему, вы с автором той темы работаете над одной задачей Уж не из одного ли источника вы её получали?

По поводу основной задачи: хэши, хэши и ещё раз хэши.
По поводу "реально ли за день-два" - думаю, реально. Но с учётом незнания многопоточности - менее вероятно. Там всё не сложно, но застрять можно как следует.

Читать MSDN в части UI и работы с файлами. Про хэши уже сказано выше.

P.S. Чуть позже темы солью. Дабы не умножать сущности без необходимости.

[The Nameless One]

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

Спасибо большое!

К вопросу, что такое хеши - это они http://www.firststeps.ru/mfc/msdn/r.php?121 ?

Общий алгоритм для прогона файлов так можно:

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

Следующий проверяемый файл начинает сравниваться только с теми файлами, которые следует за ним. И т.д.

Или очень коряво?

Нужно ли придумывать способ, чтобы проверяемый файл не сравнивался с дублями файла, который уже проверялся, чтобы время не терять?

[Вад]

Да, хотя там принцип иллюстрируется на совсем примитивном варианте реализации. См. родственную тему, там речь шла об md5.

Принцип сравнения не совсем удачен. Особенно если подразумевается сравнение содержимого. Поскольку сложность всё равно остаётся O(N^2 / 2)
Я бы сделал так: считаем хэш для файла и ищем, не попадался ли тот же хэш в упорядоченном списке уже имеющихся хэшей. И если нет - добавляем с сохранением порядка в списке. Так мы не будем даже сравнивать хэши "каждый с каждым" - достаточно будет бинарного поиска.

[sss]

Вад, о! Асимптотическая оценка! Ура! Тогда может быть в качестве упорядоченного списка использовать красно-черное дерево с дополнительным свойством - вызывать исключения во время вставки уже имеющегося элемента. В обработчике исключения и накапливать информацию по совпадениям. Общее время работы O(log n). 

[The Nameless One]

Вад,
Если правильно понял, лучше всего хранить два list - для хешей файлов и для дублей?

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

А если не находится, то текущий хеш заносим в первый list.

Так?

[Вад]

sss, что-то вроде этого. В принципе, достаточно будет использовать стандартный ассоциативный контейнер из STL: оно обычно красно-чёрными деревьями и реализуется, и вставка в тот же set/map возвращает false, если элемент уже существует

The Nameless One, ну дубли в любом случае придётся где-то хранить. Для начала, определимся, что мы для каждого файла имеем пару значений: путь к файлу и значение хэш-функции.
Сначала нам нужно обеспечить хранение хэшей эталонных файлов (т.е. файлов, которые в момент добавления не являлись чьими-то дубликатами), чтобы при появлении дубликата — или потенциального дубликата, если хэш-функция допускает коллизии, — можно было сразу увидеть, что такое значение уже было.

Предположим пока, что хэш-функция не имеет коллизий, то есть, одинаковый хэш всегда означает одинаковое содержимое файлов. Тогда для хранения списка "эталонов" удобно использовать std::map или его аналоги. Используем хэш в качестве ключа и путь к файлу в качестве значения.

И далее, новый вычисленный хэш пытаемся поместить или ищем в контейнере. В общем, проверяем, уникален ли новый файл. Если уникален - он должен быть добавлен к уникальным. Если не уникален, и нам нужна в дальнейшем вся информация о дубликатах, то нам надо записать его куда-то ещё.

Я исхожу из предположения, что от списка дубликатов чаще всего будет требоваться получить список дубликатов для заданного файла. Поэтому дубликаты можно тоже организовать в какой-нибудь ассоциативный контейнер типа multimap. Или, скажем, set. Но это так, на усмотрение.


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

P.S. Надеюсь, я не ввёл в заблуждение, когда использовал термин "список". Потому что я имел в виду абстрактный список, а не какой-то конкретный контейнер (скажем, std::list и вовсе плохо подходит для данной задачи: бинарный поиск в нём, вообще говоря, невозможен)

[Антон (LogRus)]

Тогда может быть в качестве упорядоченного списка использовать красно-черное дерево

std::set или std::map как раз чёрно-красное

[The Nameless One]

Спасибо большое!
Если не против - буду задавать вопросы по ходу дел )

[sss]

Ну рад за std::set и std::map... Не знал.

Вад, я бы так поступил. В качестве ключей дерева - md5. Дополнительные данные элемента дерева - простой список. При вставке элемента - если md5 совпал добавляем полное имя в список этого элемента. После перечисления всех файлов удаляем элементы с глубиной списков равной 1 и мы до конца работаем с одним деревом...

P.S.: Надеюсь изменить методы вставки легко в std::set и std::map

[The Nameless One]

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

[sss]

Эх The Nameless One, тебе предлагают лучшее решение. Максимальное... Ну тогда в качестве ключей используй, например, простые строки - имя + размер + дата создания + последнее изменение. Например "text.txt\12321\01012009\18092009".   "\" - разделяет порций данных, позволяя не иметь дополнительных структур. В качестве метода сравнения примени алгоритм КМП.  Щас опять наверное запинают...

[Вад]

sss, согласен, это один из хороших вариантов

The Nameless One, разумеется, если размер файла не сходится, то даже хэш считать не надо, чтобы сказать, что он будет разный
Тогда нужно просто переформулировать задачу: что является уникальным ключом, позволяющим выявлять дубликаты.

[Алексей++]

тогда в качестве ключей используй, например, простые строки - имя + размер + дата создания + последнее изменение.

добавлю, имея опыт наступания на текстовые грабли, связанныес форматированием текста, строку формировать надо в одной единственной функции (входны параметры передаём, строку получаем). И нигде иначе и никак иначе , этим гарантируется одинаковая строка для одинаковых входных данных

[The Nameless One]

Спасибо.
Я понимаю, но для лучшего решения у меня нет сейчас времени. Я двигался в другую сторону - из WinApi мне нужно было только пустое окно, а дальше графические штучки.
Теперь срочно возникла такая задача, мне полтора  дня сроку.
Для меня сейчас проблема всё - создание GUI, списков с файлами, поиск файлов и т.д. Я о всем этим сталкиваюсь впервые, и вряд ли я за такой короткий срок все сделаю.
Поэтому выделить время для понимания и написании Md5 просто нет.  Тем более что это не требуется.

Поиск файлов, как понял, надо реализовывыать функциями
FindFirstFile
и
FindNextFile
?

[Алексей++]

да, FindFirstFile возвращает хендл (если хоть один файл нашёлся, это и есть первый файл)

далее в цикле используется FindNextFile (хендл в качестве параметра) , пока будет возвращаться 1

пример из мсдн

Код:

#define _WIN32_WINNT 0x0400

#include <windows.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
  WIN32_FIND_DATA FindFileData;
  HANDLE hFind;

  printf ("Target file is %s.\n", argv[1]);
  hFind = FindFirstFile(argv[1], &FindFileData);
  if (hFind == INVALID_HANDLE_VALUE)
  {
    printf ("Invalid File Handle. GetLastError reports %d\n", GetLastError ());
    return (0);
  }
  else
  {
    printf ("The first file found is %s\n", FindFileData.cFileName);
    FindClose(hFind);
    return (1);
  }
}

собственно, не забыть про FindClose(hFind);
 )

[sss]

The Nameless One, полтора дня сроку? А поиск в подкаталогах то же надо реализовать и нет наработок? Ну тогда удачи.

[The Nameless One]

Алексей1153++, спасибо!
sss, да - поиск по всему диску С. Никаких наработок в этой области нет.
За пожелание удачи - спасибо.


Вопросы по организаторской части.

Поиск решил начать при нажатии на кнопку. Т.е.

Код:

case WM_COMMAND:
if(LOWORD(wparam)==100 && HIWORD(wparam)==BN_CLICKED)
{
//тут будет вызван поиск
}
break;

Если надо, чтобы поиск был в отдельном потоке, то этот код должен вызывать этот поток, так?

Списки для хранения файлов надо создавать глобальными, чтобы поток мог их видеть?

[Вад]

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

[The Nameless One]

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

Этап "освоение GDI" можно считать почти пройденным.

Вопрос в этой части. Создал перо и пару кистей. Больше, думаю, не понадобиться.
Ничего, что DeleteObject(h); Вызываю только перед выходом из приложения, а не каждый раз в обработке сообщения WМ_PAINT?

И ещё, для фона окна в структуре WNDCLASSEX делал так:

wnd.hbrBackground=CreateSolidBrush(...);

Нужно потом удалять и эту кисть: DeleteObject(wnd.hbrBackgroun); ?

И можно запретить пользователю изменять размер окна?

Или только в WM_SIZE всегда присваивать определённые размеры?

Для отображения файлов просто рисую Rectangle() посветлее, дальше думал просто рисовать поверх него DrawText() или TextOut() списки файлов.

Вот только как вертикальную полосу прокрутки прикрутить именно к ректанглу?
И как отсекать текст, который оказывается на границых вверху и внизу, чтобы только половина строки выглядывала, например?

Сорри за такой наплыв вопросов.

[Джон]

The Nameless One, а ведь так не получится. Ты спрашиваешь всякую мелочь, вместо того чтобы почитать учебник.

Ну тогда удачи.

За пожелание удачи - спасибо.

Вобще-то это был сарказм, к которому я могу только присоединиться. Нереально всё это. Если хочешь спихнуть, то найди кто захочет это сделать за деньги, заплати и забудь как о кошмарном сне. ИМХО

[The Nameless One]

Да понял, что сарказм.

За два дня, надеюсь, ничего страшного не произойдёт, помучаюсь - попробую сам.

В принципе, сейчас скоро начну потоки смотреть, попробую запустить поиск файлов и всю логику с ними в отдельном потоке.
Когда будет список, который надо будет показать (если будет) - тогда снова обращусь с такими вопросами - как его показать, полосы прокрутки и т.д. Ну я пошёл.
Попробовать всегда стоит.

[The Nameless One]

Пф...
Беда одна не приходит - дома авария, вода прорвала... кошмар.
--------------------------------------------------------------------------------------------

В общем, прога сканирует все файлы на диске С, вычисляет дубли и выводит их.

Думаю, остались вопросы косметики.  Как и просил - теперь вопросы актуальны те, что я задавал последний раз.

Если не затруднит, попрошу подсказать:

1. "Создал перо и пару кистей. Больше, думаю, не понадобиться.
Ничего, что DeleteObject(h); Вызываю только перед выходом из приложения, а не каждый раз в обработке сообщения WМ_PAINT?
И ещё, для фона окна в структуре WNDCLASSEX делал так:
wnd.hbrBackground=CreateSolidBrush(...);
Нужно потом удалять и эту кисть: DeleteObject(wnd.hbrBackgroun); ?"

2. "И можно запретить пользователю изменять размер окна?

Или только в WM_SIZE всегда присваивать определённые размеры?"

3. "Для отображения файлов просто рисую Rectangle() посветлее, дальше думал просто рисовать поверх него DrawText() или TextOut() списки файлов.

Вот только как вертикальную полосу прокрутки прикрутить именно к ректанглу?
И как отсекать текст, который оказывается на границых вверху и внизу, чтобы только половина строки выглядывала, например? "

Логику со сканом диска С и обработку файлов реализовывают методы  объекта.
Этот же объект создаёт новый тред, в этом треде вызывается метод этого же объекта, который работает с файлами.

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

И ещё нужно сдлелать возможность ставить поиск на паузу, останавливать и продолжать.

В каком потоке это делать - в первичном или втором?

Прошу, если не затруднит, пару подсказок  по всем вопросам.

Времени есть ещё день. В общем, в понедельник утром уже все должно быть готово.

после скана:

[Алексей++]

Код:

Ничего, что DeleteObject(h); Вызываю только перед выходом из приложения, а не каждый раз в обработке сообщения WМ_PAINT?

а и не надо в конце каждой отрисовку разрушать кисть. Один раз создал - и пользуйся. Надеюсь, ты не создаёшь кисть в начале каждого WМ_PAINT ? ))

Код:

И ещё, для фона окна в структуре WNDCLASSEX делал так:
wnd.hbrBackground=CreateSolidBrush(...);
Нужно потом удалять и эту кисть: DeleteObject(wnd.hbrBackgroun); ?"

DeleteObject - не помешает. Хотя бы для порядка

Код:

Или только в WM_SIZE всегда присваивать определённые размеры?"

1) можно так. Ещё есть сообщение WM_SIZING , что лучше использовать - щас не помню (вроде ...ING) , поэкспериментируй
2) если окно - диалог, то сделать с "тонкой" рамкой (убрать свойство WS_THICKFRAME)

Код:

Вот только как вертикальную полосу прокрутки прикрутить именно к ректанглу?

создать объект полоски, показать и MoveWindow его к нужному месту жительства на родительском окне.

Код:

И как отсекать текст, который оказывается на границых вверху и внизу, чтобы только половина строки выглядывала, наприме

1) (хуже) рисовать на HDC, созданном в озу, потом копировать (BitBlt) нужный прямоугольник на HDC диалога
2) (красивее) использовать контрол (например static), в котором и рисовать. Контрол сам обрежет ненужное за границами

покажи,место, где и как ты рисуешь текст ?

Код:

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

добавь

Код:

И ещё нужно сдлелать возможность ставить поиск на паузу, останавливать и продолжать.
В каком потоке это делать - в первичном или втором?

сам поиск лучше сделать в дочернем потоке, но передать туда указатель на главный диалог, чтобы:
1) в главном диалоге показать временное окно с кнопкой отмены
2) в главном диалоге отображать индикатор прогресса, значения брать из пеменных-счётчиков, которые заполняются из дочернего потока (сами епременные находятся в главном диалоге)

[Вад]

The Nameless One, мне кажется, что я что-то пропустил, но... У тебя так задача стояла, самому рисовать элементы UI? Не понимаю, за какой надобностью список файлов самодельно-рисованный. Есть же контрол ListView.

Запретить изменять окно можно через стили. Кажется, нужно не использовать стиль WS_SIZEBOX. Но в точности уже не помню - это настраивается через список свойств в редакторе ресурсов VS.

[The Nameless One]

Надеюсь, ты не создаёшь кисть в начале каждого WМ_PAINT ? ))

Нет, конечно. Но каждый раз устанавливаю:

Код:

SelectObject(hdc, pen);
SelectObject(hdc, brush);

Это нормально?

покажи,место, где и как ты рисуешь текст ?

Для удобства создал класс, который создаёт окно на основе структуры WNDCLASSEX, (которая является его членом). У класса есть метод Paint, который вызывается в сообщении WM_PAINT.
В этом методе рисую заголовки "таблицы" DrawEdge, ректангл и т.д.

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

Отображаю найденный текст ещё одной функцией-членом класса Skan, которая вызывается в WM_PAINT:
Вот он:

Код:

void Skan::Show(HDC &hdc)
{
int y=35;
char buf[20];
for(it=dublfiles.begin(); it!=dublfiles.end(); it++)
{
TextOut(hdc, 28, y, (*it)->name, strlen((*it)->name));
TextOut(hdc, 230, y, (*it)->path, strlen((*it)->path));
sprintf(buf, "%d KB", (*it)->size);
TextOut(hdc, 530, y, buf, strlen(buf));
y+=20;
}
}

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

добавь

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

Большое спасибо за помощь!

[The Nameless One]

The Nameless One, мне кажется, что я что-то пропустил, но... У тебя так задача стояла, самому рисовать элементы UI? Не понимаю, за какой надобностью список файлов самодельно-рисованный. Есть же контрол ListView.

Так если б я о нем знал Ну уже сделал и ладно.  Если успею - переделаю.

[Алексей++]

The Nameless One, я сначала не подумал об этом, а Вад правильно говорит - зачем всю эту тряхомундию изобретать, если ListControl и строчки тебе отобразит и полоса прокрутки есть уже Тем более, что цейтнот.

[The Nameless One]

Ок, заюзаю ListControl, спасибо:)