Russian Qt Forum
Ноябрь 23, 2024, 05:52 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Дубликаты файлов
Страниц: [1] 2 3   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Дубликаты файлов  (Прочитано 22565 раз)
cya-st
Гость
« : Август 31, 2009, 12:26 »
Помогите пожалуйста найти алгоритм поиска дубликатов файлов, для винды.
Записан
SimpleSunny
Гость
« Ответ #1 : Август 31, 2009, 15:12 »
Если дубликаты точные, то можно предложить нечто подобное:
1. Создаешь QMap <int , QString>. int - Ключ для файла (md5, crc, sha-1, /etc), QString - путь к файлу
2. Рекурсивно сканируешь заданную директорию.
3. При нахождении файла считаем от него ключ, если он уже находится в QMap, то нашли дубликат, иначе заносим ключ в QMap.
Записан
cya-st
Гость
« Ответ #2 : Август 31, 2009, 16:59 »
Это надо наверное и еще в отдельный поток засунуть.
Записан
BlackTass
Гость
« Ответ #3 : Август 31, 2009, 17:14 »
ну мд5 и ша1 в инт не влезут Улыбающийся уж лучше ключом делать тоже QString с хекс представлением хеша
Записан
Пантер
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 5876


Жаждущий знаний


Просмотр профиля WWW
« Ответ #4 : Август 31, 2009, 17:59 »
Лучше первоначально создать мультимап с размером файла, а потом уже считать хэш для файлов с одинаковыми размерами, это намного быстрее будет.
Записан
1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
zenden
Гость
« Ответ #5 : Август 31, 2009, 18:01 »
И всё же сначала нужно отобрать файлы с одинаковым размером.
А то считать хэш всех файлов подряд не есть быстро.
Записан
spectre71
Гость
« Ответ #6 : Сентябрь 03, 2009, 17:11 »
Цитата: cya-st от Август 31, 2009,  12:26
Помогите пожалуйста найти алгоритм поиска дубликатов файлов, для винды.
Ну, винда здесь ни причем. Улыбающийся

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

Сообщений: 5876


Жаждущий знаний


Просмотр профиля WWW
« Ответ #7 : Сентябрь 03, 2009, 17:24 »
md5 лучше пропустить и сразу сравнивать побайтно.
Записан
1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
spectre71
Гость
« Ответ #8 : Сентябрь 03, 2009, 18:11 »
Цитата: panter_dsd от Сентябрь 03, 2009,  17:24
md5 лучше пропустить и сразу сравнивать побайтно.
Нет, смотри:
1) Если файлов c одинаковым размером > 2 = N, то имем N!(факториал) сравнений файлов между собой.
2) Если файлов c одинаковым размером всего 2 и они достаточно большого размера, то при сравнении имеем плохой показатель попеременного чтении файлов с диска.
3) Если файлов c одинаковым размером всего 2 и они маленькие и не дефрагментированные, то если проц не занят(!), то при хорошем алгоритме "hash"(например md5), потери(по сравнению с прямым сравнением) несущественны.
Да (-) возможное повторное побайтное сравнение после идентичного "hash", но это маловероятно(в обычной ситуации, а в специфичных, предметных, требует соответствующих решений)
Записан
spectre71
Гость
« Ответ #9 : Сентябрь 03, 2009, 18:33 »
Цитата: Spectre от Сентябрь 03, 2009,  17:11
1) Получаем и сравниваем canonic path(совпадение пути до файла).
2) Получаем  Размер файлов, если разный, разные файлы.
3) Если имем "hash" для файлов(например мд5), сравниваем, если разный, разные файлы.
4) Сравниваем файлы!
Из этого следует:
- Имеем список файлов.
- Получаем их canonic path, сортируем. Файлы с одинаковым canonic path - разные варианты записи path.
- Получаем список уникальных canonic path
- Получаем размеры файлов, сортируем.
- Для всех уникальных размеров - уникальны и файлы, отбрасываем.
- Для каждого файла с одинаковым размером получаем md5
- Если md5 - различны - различны и файлы, отбрасываем.
- Для одинаковых md5 сравниваем файлы побайтно.

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

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Сентябрь 03, 2009, 21:30 »
Можно посмотреть и "под другим углом". Предположим получили 100 файлов размером 1Mb. Давайте сразу сравнивать побайтно:

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

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

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

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

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



Записан
spectre71
Гость
« Ответ #11 : Сентябрь 03, 2009, 22:29 »
Цитата: Igors от Сентябрь 03, 2009,  21:30
Можно посмотреть и "под другим углом". Предположим получили 100 файлов размером 1Mb. Давайте сразу сравнивать побайтно:

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

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

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

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

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Сентябрь 04, 2009, 13:40 »
По-моему лучше сразу заниматься "оптимальным побайтовым сравнением", чем сделать его абы как и пытаться затем оптимизировать с помощью нескольких дополнительных проверок. Ведь они добавят кода и возможных багов а побайтового сравнения все равно не избежать.
Записан
spectre71
Гость
« Ответ #13 : Сентябрь 05, 2009, 08:42 »
Цитата: Igors от Сентябрь 04, 2009,  13:40
По-моему лучше сразу заниматься "оптимальным побайтовым сравнением", чем сделать его абы как и пытаться затем оптимизировать с помощью нескольких дополнительных проверок. Ведь они добавят кода и возможных багов а побайтового сравнения все равно не избежать.
Что такое "оптимальное побайтовое сравнением"?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Сентябрь 05, 2009, 14:55 »
Цитата: Spectre от Сентябрь 05, 2009,  08:42
Что такое "оптимальное побайтовое сравнением"?
Есть N файлов одинакового размера. Для каждого нужно получить условный ID  так чтобы файлы у которых все байты совпадают имели тот же ID. Алгоритм должен работать для любого N и учитывать ограничение на число одновременно открытых файлов.
Записан
Страниц: [1] 2 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.066 секунд. Запросов: 22.