Total Commander :: Уникальность crc32 для файлов

through

[^/[Print]\]
Goto page Previous 1, 2 :| |:
Total Commander -> Программное обеспечение

#16: Author: Volniy, Location: Местный

Posted: Sat Jun 13, 2009 07:06
—
Хорошее решение - доверить все это дело Тотал Командеру. Вроде неплохо это у него получается Wink

Кстати, только что подсмотрел, как это реализовано у Гислера. По крайней мере у него каждый файл, подозреваемый в том, что тот является одним из дубликатов в группе, считывается только один раз.

#17: Author: Tol!k, Location: Арзамас

Posted: Sun Jun 14, 2009 21:57
—

Batya wrote:

Есть идеи алгоритма?

Если файлы разного размера — они не равны.
Если 2 файла одного размера — сравниваем по содержимому.
Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.

Volniy wrote:

Кстати, только что подсмотрел, как это реализовано у Гислера.

Где (или как)? Тоже любопытно.

#18: Author: CaptainFlint, Location: Москва

Posted: Sun Jun 14, 2009 23:23
—

Tol!k wrote:

Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.

Любой хэш, какой бы быстрый он ни был, требует полного считывания всего содержимого файла. И плюс сравнение по содержимому выполнит полное считывание. Да ещё, не исключено, что не единожды (если файлов несколько). Мне кажется, надо использовать что-то более хитрое. Например, так:
1. Получили полный список файлов.
2. Разбили на группы с одинаковым размером.
3. Внутри каждой группы считываем по блоку длиной N из каждого файла, сравниваем эти блоки попарно.
4. По результатам сравнения разбиваем файлы из текущей группы на подгруппы, внутри которых содержимое всех считанных к данному моменту блоков у всех файлов идентичное.
5. Повторяем шаги 3-4, пока файлы не будут считаны и сравнены полностью.
6. Полученный набор подгрупп и представляет собой разбиение всех файлов на одинаковые по содержимому, причём каждый из файлов в процессе работы был полностью прочитан ровно один раз.

#19: Author: Volniy, Location: Местный

Posted: Mon Jun 15, 2009 01:16
—
Tol!k, никакого реверсинга, упаси бог! Просто подсунул Тоталу определенный набор файлов и проследил его файловые операции при поиске дубликатов Filemon-ом. Интересовал единственный вопрос: бывают ли повторные чтения содержимого одного и того-же файла. Сие в эскпериментах замечено не было.

#20: Author: Lazy Crazy,

Posted: Mon Jun 15, 2009 14:44
—
Изначально Batya упоминал, что всё это нужно для топика "автоматическое удаление файлов по датам создания", который начинал Neo233 с проблемой идентификации ‘картинок с Web-камеры’ в ‘кэше Internet Explorer`a’. А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…

#21: Author: Batya, Location: Москва, Россия

Posted: Mon Jun 15, 2009 16:05
—
CaptainFlint
Отличная мысль. Надо подумать, можно ли это сделать через vbs.

Lazy Crazy wrote:

А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…

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

#22: Author: Моторокер, Location: г. Пермь (читается Перьмь)

Posted: Tue Jun 16, 2009 19:22
—

Batya wrote:

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

Если уж файл читаем, почему бы не считать параллельно его сумму? Операции с файлами намного медленней операций в оперативке.

Можно хранить кол-во считанного и нерассчитанную до конца сумму.

#23: Author: alexanderwdark, Location: Россия

Posted: Sun Aug 23, 2009 03:57
—
Любой хэш по определению не уникален. Нельзя однозначно представить большой объем информации гораздо меньшим. Криптографически стойкий хэш только тем и отличается, что довольно сложно найти коллизии, т.е. такие совпадения исходных данных, при которых значения хэша одинаковы.

Длина самой хэш суммы здесь только косвенно влияет на надежность и стойкость. Есть определенный минимум, конечно. Скажем, 80-128 бит. Короче - сликом мало вариантов.

Но, сам алгоритм подсчета может быть уязвим для совпадений / коллизий. Сейчас на конкурсе SHA3 уже тьма новых, хороших на первый взгляд, хэшей были отсеяны - хотя и давали на выходе 512 и выше бит (64 байта). Приничой были именно коллизии, а у кого и возможность частично предсказать исходную информацию на основе хэша.

MD5 уже давно сломали, SHA1 так же не надежен. От SHA2 уже отказываются. Скоро уже будет известен SHA3, финалистов уже совсем не много осталось.

Уже можно выделить отличные алгоритмы: Keccak и Skein. Что особенно у них интересно - они гибкие, длина хэша может быть любой, не фиксирована до типовых 128, 256, 384, 512 бит.

Последний заточен под 64-битные системы, поэтому на 32-разрядных ОС довольно медлителен. Keccak в этом плане интереснее, если победит, у нас будет отличный алгоритм для самых различных целей.

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

Хотя и сейчас есть способ: считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.

#24: Author: Mite,

Posted: Wed Oct 28, 2009 02:58
—
CRC32 не уникален для файлов разного размера - это было замечено на практике. Причем если для файлов одного размера вероятность совпадения хэша при различном содержимом файлов достаточно мала, то в группе файлов отличающихся по размеру вероятность встретить файлы с одинаковым CRC32 (и естественно различным содержимым) - велика. (Это было замечено при сравнении большого количества фото и видео файлов снятых с помощью камеры мобильного телефона).

#25: Author: alexanderwdark, Location: Россия

Posted: Wed Oct 28, 2009 09:11
—

Mite wrote:

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

Вполне, поскольку сумма - циклическая. Ее есть смысл проверять, если размер файла идентичен.

#26: Author: Mite,

Posted: Wed Oct 28, 2009 09:54
—

Batya wrote:

Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?

Если судить только по совпадению crc32, не сравнивая никакие другие параметры файлов, то этого недостаточно! Необходим хотя бы еще один параметр: или размер, или

alexanderwdark wrote:

считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.

#27: Author: basileus,

Posted: Tue Dec 08, 2009 02:59
—
Вставлю лыко в строку.
Любой ХЭШ есть сжатие с потерями.
Представляется наиболее разумным следуюющий подход:
Выбираем некую константу, для размера блока, меньшую сегмента памяти.
Скажем, 4 килобайта.
Все файлы, требующие сравнения, длина которых меньше этого блока,
просто сравниваются друг с другом. (строим дерево, для ускорения сравнения, представляя данные как очень длинное число)
Файлы большей длины обсчитываем быстрой CRC(иной хэш), разбивая на блоки такой длины, чтобы в общая длина всех CRC блоков + CRC всего файла занимали этот блок.
Далее - аналогично маленьким файлам.
Но, еще с одной итерацией.
Если, по Дирихле, в узел дерева (ящик Дирихле), попадёт более одного элемента - проводим полное сравнение файлов.
Чем больше длина блока -тем лучше работает метод.
Расход памяти на посроение деревьев и выделение блоков может быть значительным.
Возможно, имеет делать предварительное построение еще одного дерева по длинам файлов и запускать этот алогритм для каждого узла отдельно.

Total Commander -> Программное обеспечение

output generated using printer-friendly topic mod. All times are GMT + 4 Hours

Goto page Previous 1, 2 :| |: Page 2 of 2