View previous topic :: View next topic |
Author |
Message |
Volniy
Joined: 15 Dec 2004 Posts: 585 Location: Местный
|
(Separately) Posted: Sat Jun 13, 2009 07:06 Post subject: |
|
|
Хорошее решение - доверить все это дело Тотал Командеру. Вроде неплохо это у него получается Кстати, только что подсмотрел, как это реализовано у Гислера. По крайней мере у него каждый файл, подозреваемый в том, что тот является одним из дубликатов в группе, считывается только один раз. |
|
Back to top |
|
|
Tol!k
Joined: 01 Apr 2008 Posts: 1727 Location: Арзамас
|
(Separately) Posted: Sun Jun 14, 2009 21:57 Post subject: |
|
|
Batya wrote: | Есть идеи алгоритма? | Если файлы разного размера — они не равны.
Если 2 файла одного размера — сравниваем по содержимому.
Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.
Volniy wrote: | Кстати, только что подсмотрел, как это реализовано у Гислера. | Где (или как)? Тоже любопытно. |
|
Back to top |
|
|
CaptainFlint
Joined: 14 Dec 2004 Posts: 6151 Location: Москва
|
(Separately) Posted: Sun Jun 14, 2009 23:23 Post subject: |
|
|
Tol!k wrote: | Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому. |
Любой хэш, какой бы быстрый он ни был, требует полного считывания всего содержимого файла. И плюс сравнение по содержимому выполнит полное считывание. Да ещё, не исключено, что не единожды (если файлов несколько). Мне кажется, надо использовать что-то более хитрое. Например, так:
1. Получили полный список файлов.
2. Разбили на группы с одинаковым размером.
3. Внутри каждой группы считываем по блоку длиной N из каждого файла, сравниваем эти блоки попарно.
4. По результатам сравнения разбиваем файлы из текущей группы на подгруппы, внутри которых содержимое всех считанных к данному моменту блоков у всех файлов идентичное.
5. Повторяем шаги 3-4, пока файлы не будут считаны и сравнены полностью.
6. Полученный набор подгрупп и представляет собой разбиение всех файлов на одинаковые по содержимому, причём каждый из файлов в процессе работы был полностью прочитан ровно один раз. _________________ Почему же, ё-моё, ты нигде не пишешь "ё"? |
|
Back to top |
|
|
Volniy
Joined: 15 Dec 2004 Posts: 585 Location: Местный
|
(Separately) Posted: Mon Jun 15, 2009 01:16 Post subject: |
|
|
Tol!k, никакого реверсинга, упаси бог! Просто подсунул Тоталу определенный набор файлов и проследил его файловые операции при поиске дубликатов Filemon-ом. Интересовал единственный вопрос: бывают ли повторные чтения содержимого одного и того-же файла. Сие в эскпериментах замечено не было. |
|
Back to top |
|
|
Lazy Crazy
Joined: 16 Jan 2005 Posts: 400
|
(Separately) Posted: Mon Jun 15, 2009 14:44 Post subject: |
|
|
Изначально Batya упоминал, что всё это нужно для топика "автоматическое удаление файлов по датам создания", который начинал Neo233 с проблемой идентификации ‘картинок с Web-камеры’ в ‘кэше Internet Explorer`a’. А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой… _________________
|
|
Back to top |
|
|
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Mon Jun 15, 2009 16:05 Post subject: |
|
|
CaptainFlint
Отличная мысль. Надо подумать, можно ли это сделать через vbs.
Lazy Crazy wrote: | А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой… | Это верно, но хотелось бы найти оптимальное решение для любого случая. _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
Моторокер
Joined: 06 May 2005 Posts: 1517 Location: г. Пермь (читается Перьмь)
|
(Separately) Posted: Tue Jun 16, 2009 19:22 Post subject: |
|
|
Batya wrote: | при таком подходе надо будет значительное число раз читать одни и те же файлы. (Предположим, что размеры файлов совпадают.) |
Если уж файл читаем, почему бы не считать параллельно его сумму? Операции с файлами намного медленней операций в оперативке.
Можно хранить кол-во считанного и нерассчитанную до конца сумму. _________________ плагины для Total Commander, статьи Graphics Converter; NSCopy; SEO HTML; KillOK; Плагин на Delphi
ПармаСруб - строительство домов и бань в Перми |
|
Back to top |
|
|
alexanderwdark
Joined: 14 Apr 2008 Posts: 304 Location: Россия
|
(Separately) Posted: Sun Aug 23, 2009 03:57 Post subject: |
|
|
Любой хэш по определению не уникален. Нельзя однозначно представить большой объем информации гораздо меньшим. Криптографически стойкий хэш только тем и отличается, что довольно сложно найти коллизии, т.е. такие совпадения исходных данных, при которых значения хэша одинаковы.
Длина самой хэш суммы здесь только косвенно влияет на надежность и стойкость. Есть определенный минимум, конечно. Скажем, 80-128 бит. Короче - сликом мало вариантов.
Но, сам алгоритм подсчета может быть уязвим для совпадений / коллизий. Сейчас на конкурсе SHA3 уже тьма новых, хороших на первый взгляд, хэшей были отсеяны - хотя и давали на выходе 512 и выше бит (64 байта). Приничой были именно коллизии, а у кого и возможность частично предсказать исходную информацию на основе хэша.
MD5 уже давно сломали, SHA1 так же не надежен. От SHA2 уже отказываются. Скоро уже будет известен SHA3, финалистов уже совсем не много осталось.
Уже можно выделить отличные алгоритмы: Keccak и Skein. Что особенно у них интересно - они гибкие, длина хэша может быть любой, не фиксирована до типовых 128, 256, 384, 512 бит.
Последний заточен под 64-битные системы, поэтому на 32-разрядных ОС довольно медлителен. Keccak в этом плане интереснее, если победит, у нас будет отличный алгоритм для самых различных целей.
Впрочем, никто не мешает для TC использовать абсолютно любой алгоритм подсчета хэш суммы файла. Это если по каким либо причинам нужна гарантия подлинности файла (неизменности).
Хотя и сейчас есть способ: считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна. |
|
Back to top |
|
|
Mite
Joined: 26 Oct 2009 Posts: 10
|
(Separately) Posted: Wed Oct 28, 2009 02:58 Post subject: |
|
|
CRC32 не уникален для файлов разного размера - это было замечено на практике. Причем если для файлов одного размера вероятность совпадения хэша при различном содержимом файлов достаточно мала, то в группе файлов отличающихся по размеру вероятность встретить файлы с одинаковым CRC32 (и естественно различным содержимым) - велика. (Это было замечено при сравнении большого количества фото и видео файлов снятых с помощью камеры мобильного телефона). |
|
Back to top |
|
|
alexanderwdark
Joined: 14 Apr 2008 Posts: 304 Location: Россия
|
(Separately) Posted: Wed Oct 28, 2009 09:11 Post subject: |
|
|
Mite wrote: | CRC32 не уникален для файлов разного размера - это было замечено на практике. Причем если для файлов одного размера вероятность совпадения хэша при различном содержимом файлов достаточно мала, то в группе файлов отличающихся по размеру вероятность встретить файлы с одинаковым CRC32 (и естественно различным содержимым) - велика. (Это было замечено при сравнении большого количества фото и видео файлов снятых с помощью камеры мобильного телефона). |
Вполне, поскольку сумма - циклическая. Ее есть смысл проверять, если размер файла идентичен. |
|
Back to top |
|
|
Mite
Joined: 26 Oct 2009 Posts: 10
|
(Separately) Posted: Wed Oct 28, 2009 09:54 Post subject: |
|
|
Batya wrote: | Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов? |
Если судить только по совпадению crc32, не сравнивая никакие другие параметры файлов, то этого недостаточно! Необходим хотя бы еще один параметр: или размер, или alexanderwdark wrote: | считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна. |
|
|
Back to top |
|
|
basileus
Joined: 08 Dec 2009 Posts: 3
|
(Separately) Posted: Tue Dec 08, 2009 02:59 Post subject: |
|
|
Вставлю лыко в строку.
Любой ХЭШ есть сжатие с потерями.
Представляется наиболее разумным следуюющий подход:
Выбираем некую константу, для размера блока, меньшую сегмента памяти.
Скажем, 4 килобайта.
Все файлы, требующие сравнения, длина которых меньше этого блока,
просто сравниваются друг с другом. (строим дерево, для ускорения сравнения, представляя данные как очень длинное число)
Файлы большей длины обсчитываем быстрой CRC(иной хэш), разбивая на блоки такой длины, чтобы в общая длина всех CRC блоков + CRC всего файла занимали этот блок.
Далее - аналогично маленьким файлам.
Но, еще с одной итерацией.
Если, по Дирихле, в узел дерева (ящик Дирихле), попадёт более одного элемента - проводим полное сравнение файлов.
Чем больше длина блока -тем лучше работает метод.
Расход памяти на посроение деревьев и выделение блоков может быть значительным.
Возможно, имеет делать предварительное построение еще одного дерева по длинам файлов и запускать этот алогритм для каждого узла отдельно. |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|