AZJIO
Silver Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Andrea
Цитата:| что она выполняет сканирование по содержимому, то это означает, что она ищет совпадения по контрольным суммам? |
Нет, наоборот, по содержимому, значит сравнивает байт в байт.
Skif_off
Цитата:| сравниваются (по частям, вероятно). |
именно так, чтобы память экономить. Хеш тоже так вычисляется, открывается дескриптор хеша и блоками
Цитата:| Гислер писал про ускорение (возможно, BLAKE3) |
Теоретически любой алгоритм хеша требует чтение файла, аналогично сравнение по содержимому тоже требует чтение файла, поэтому проще проверять по содержимому, будет наибольшая скорость. Но хеш в моей проге имеет не только или не просто с потолка взятый, а позволяет проверять по базе. Допустим у вас есть база хешей ваших фотографий, вам в вацап или другой месенджер сбрасывают фотки, которые у вас уже есть. То не нужно считывать их снова, допустим из 2 гигабайта данных получены 100 кб хешей, либо прочитать 2 Гб или 100 Кб, разница есть, 30 секунд или мгновенно? А если больше гигабайта, например музыка, клипы, фильмы? Допустим 200 Гб копируются 4 часа, то есть 4 часа или мгновенно, разница есть?
Цитата:| Сравнивал побайтовое и, кажется, Search_duplicates от AZJIO на очень большом количестве небольших файлов: вторым способом было найдено больше дубликатов. |
Кстати, тут стоит упомянуть ситуацию, когда в одной проге не обрабатываются скрытые файлы. Я ведь тоже сравниваю результаты с другими прогами и по скорости и по числу найденных, и попадал на такую проблему. Было бы интересно посмотреть на коллизии. Просто мне кажется коллизии это нечто нереальное, то есть их надо сгенерировать, это некие 2 бинарные файлы, специально созданные для доказательства, а вот так чтобы два файла с реальными текстами и были одинаковы по MD5 просто интересно посмотреть. И кроме прочего даже проверить жёсткий диск, не всегда удаление дубликата это круто, есть две проги и ей нужны ресурсы, удали из одной и она станет поломанной, то что он есть в другой папке не будешь же потом в 1000 проектах копировать какие-то десятки тысяч файлов, потому что прога их просит все. У меня например куча версий разных справок html, кучи ресурсов у прог и вот пройдись по этому прогой дубликатов, потом за год не восстановишь.
Кстати, версия на PureBasic должны быть быстрей, потому что там есть промежуточный поиск "псевдохеш". Чтобы объяснить как это работает, немного деталей.
1. Прога сканирует папку для поиска файлов
2. Для ускорения поиска мы не получаем хеши всех файлов, сначала получаем размеры файлов или даже при поиске файлов сразу получаем размеры файлов.
3. Попутно создаём карту, это такая таблица, в которой ключ уникален. В качестве ключа используем размер файла, если попадается файл с таким же размером, то в элемент карты допустим 40000 (40кб) добавляем элемент списка с путём. То есть в ячейке 40000 находятся например 10 файлов, все они размером 40 кб.
4. Создаём, тут мы должны были создать карту MD5, но так оно и было, до того, как я попробовал создать псевдо хеш. Я его хотел сделать для больших файлов, но в итоге оказалось что даже использование его для файлов размером 50 кб дало плоды ускорения. Смысл: мы не хешируем файл сразу, потому что это тоже длительная операция чтения и вычисления. А что если я возьму из файла выборочно байт из каждые 100 Мб, например фильм 2 Гб, и я возьму 20 байт и на их основе пойму, что это не одинаковые файлы, зачем мне читать все 2 Гб. По скорости взять 20 точек это равносильно произвести доступ к 20 файлам, естественно это быстрее чем читать 2Гб. Но для оптимизации, если файл маленький, то как в нём прочитать через 100 Мб если он всего 10 Мб и пришла идея разделить размер на 31 и мы получим размер промежутка между которыми брать это байт, то есть если файл 31 кб, то я возьму байт через каждые 1 кб. И я получаю хеш аналогичный MD5 из 32-х байтов, это и есть псевдо хеш. Если он не одинаков, то нет смысла хешировать его с помощью MD5, то есть я сократил число необходимых запросов MD5 и алгоритм заработал существенно быстрее. То есть я брал первый и последний байт и посредине в вычисленных промежутках.
5. В принципе смысл карт повторяется, создал карту псевдохеша, получил в каждый элемент карты одинаковые псевдохеши и далее создал карту MD5 вычислил хеши и получил в каждом элементе одинаковые MD5, естественно внутри карт передаются привязанные пути и далее вывожу это в результаты, то есть в заголовке собственно хеш и привязанные к нему пути, то есть у этих путей к файлам одинаковый хеш.
На счёт коллизий, если это действительно важно, можно переписать прогу в настройках сделать выбор движка, то есть дописать, по крайней мере не в прогу AutoIt3, так как там тесно связано с CSV, а в PureBasic. В AutoIt3 там есть SHA1 (160bit). В PureBasic есть SHA1, SHA2, SHA3, вполне можно любой прикрутить, а также есть функция CompareMemory(), чтобы сравнить 2 участка памяти по указателю, т.е. читать по 2 Мб в память обоих файлов и сравнивать блоки в цикле.
Andrea, Skif_off
Кстати, фича удобная (в контекстном меню списка поиска) - запрет удаления (и уровни очерёдности) в какой то папке, то есть папка как основа, а остальные как места для очистки. Это позволяет не просматривать весь список на предмет правильные ли файлы удаляются. А уровень позволяет задать в каких папках удалять первоочерёдно, а в каких в последнюю очередь. |
Всего записей: 4413 | Зарегистр. 03-05-2006 | Отправлено: 07:12 04-02-2024 | Исправлено: AZJIO, 08:17 04-02-2024 |
|
