Total Commander Forum Index Total Commander
Форум поддержки пользователей Total Commander
Сайты: Все о Total Commander | Totalcmd.net | Ghisler.com | RU.TCKB
 
 RulesRules   SearchSearch   FAQFAQ   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Уникальность crc32 для файлов
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Total Commander Forum Index -> Программное обеспечение printer-friendly view
View previous topic :: View next topic  
Author Message
Volniy



Joined: 15 Dec 2004
Posts: 585
Location: Местный

Post (Separately) Posted: Sat Jun 13, 2009 07:06    Post subject: Reply with quote

Хорошее решение - доверить все это дело Тотал Командеру. Вроде неплохо это у него получается Wink Кстати, только что подсмотрел, как это реализовано у Гислера. По крайней мере у него каждый файл, подозреваемый в том, что тот является одним из дубликатов в группе, считывается только один раз.
Back to top
View user's profile Send private message
Tol!k



Joined: 01 Apr 2008
Posts: 1727
Location: Арзамас

Post (Separately) Posted: Sun Jun 14, 2009 21:57    Post subject: Reply with quote

Batya wrote:
Есть идеи алгоритма?
Если файлы разного размера — они не равны.
Если 2 файла одного размера — сравниваем по содержимому.
Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.
Volniy wrote:
Кстати, только что подсмотрел, как это реализовано у Гислера.
Где (или как)? Тоже любопытно.
Back to top
View user's profile Send private message
CaptainFlint



Joined: 14 Dec 2004
Posts: 6151
Location: Москва

Post (Separately) Posted: Sun Jun 14, 2009 23:23    Post subject: Reply with quote

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

Любой хэш, какой бы быстрый он ни был, требует полного считывания всего содержимого файла. И плюс сравнение по содержимому выполнит полное считывание. Да ещё, не исключено, что не единожды (если файлов несколько). Мне кажется, надо использовать что-то более хитрое. Например, так:
1. Получили полный список файлов.
2. Разбили на группы с одинаковым размером.
3. Внутри каждой группы считываем по блоку длиной N из каждого файла, сравниваем эти блоки попарно.
4. По результатам сравнения разбиваем файлы из текущей группы на подгруппы, внутри которых содержимое всех считанных к данному моменту блоков у всех файлов идентичное.
5. Повторяем шаги 3-4, пока файлы не будут считаны и сравнены полностью.
6. Полученный набор подгрупп и представляет собой разбиение всех файлов на одинаковые по содержимому, причём каждый из файлов в процессе работы был полностью прочитан ровно один раз.
_________________
Почему же, ё-моё, ты нигде не пишешь "ё"?
Back to top
View user's profile Send private message
Volniy



Joined: 15 Dec 2004
Posts: 585
Location: Местный

Post (Separately) Posted: Mon Jun 15, 2009 01:16    Post subject: Reply with quote

Tol!k, никакого реверсинга, упаси бог! Просто подсунул Тоталу определенный набор файлов и проследил его файловые операции при поиске дубликатов Filemon-ом. Интересовал единственный вопрос: бывают ли повторные чтения содержимого одного и того-же файла. Сие в эскпериментах замечено не было.
Back to top
View user's profile Send private message
Lazy Crazy



Joined: 16 Jan 2005
Posts: 400

Post (Separately) Posted: Mon Jun 15, 2009 14:44    Post subject: Reply with quote

Изначально Batya упоминал, что всё это нужно для топика "автоматическое удаление файлов по датам создания", который начинал Neo233 с проблемой идентификации ‘картинок с Web-камеры’ в ‘кэше Internet Explorer`a’. А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…
_________________
Back to top
View user's profile Send private message
Batya



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Mon Jun 15, 2009 16:05    Post subject: Reply with quote

CaptainFlint
Отличная мысль. Надо подумать, можно ли это сделать через vbs.

Lazy Crazy wrote:
А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…
Это верно, но хотелось бы найти оптимальное решение для любого случая.
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
Моторокер



Joined: 06 May 2005
Posts: 1517
Location: г. Пермь (читается Перьмь)

Post (Separately) Posted: Tue Jun 16, 2009 19:22    Post subject: Reply with quote

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

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

Можно хранить кол-во считанного и нерассчитанную до конца сумму.
_________________
плагины для Total Commander, статьи Graphics Converter; NSCopy; SEO HTML; KillOK; Плагин на Delphi
ПармаСруб - строительство домов и бань в Перми
Back to top
View user's profile Send private message
alexanderwdark



Joined: 14 Apr 2008
Posts: 304
Location: Россия

Post (Separately) Posted: Sun Aug 23, 2009 03:57    Post subject: Reply with quote

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

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

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

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

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

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

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

Хотя и сейчас есть способ: считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.
Back to top
View user's profile Send private message
Mite



Joined: 26 Oct 2009
Posts: 10

Post (Separately) Posted: Wed Oct 28, 2009 02:58    Post subject: Reply with quote

CRC32 не уникален для файлов разного размера - это было замечено на практике. Причем если для файлов одного размера вероятность совпадения хэша при различном содержимом файлов достаточно мала, то в группе файлов отличающихся по размеру вероятность встретить файлы с одинаковым CRC32 (и естественно различным содержимым) - велика. (Это было замечено при сравнении большого количества фото и видео файлов снятых с помощью камеры мобильного телефона).
Back to top
View user's profile Send private message
alexanderwdark



Joined: 14 Apr 2008
Posts: 304
Location: Россия

Post (Separately) Posted: Wed Oct 28, 2009 09:11    Post subject: Reply with quote

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


Вполне, поскольку сумма - циклическая. Ее есть смысл проверять, если размер файла идентичен.
Back to top
View user's profile Send private message
Mite



Joined: 26 Oct 2009
Posts: 10

Post (Separately) Posted: Wed Oct 28, 2009 09:54    Post subject: Reply with quote

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

Если судить только по совпадению crc32, не сравнивая никакие другие параметры файлов, то этого недостаточно! Необходим хотя бы еще один параметр: или размер, или
alexanderwdark wrote:
считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.
Back to top
View user's profile Send private message
basileus



Joined: 08 Dec 2009
Posts: 3

Post (Separately) Posted: Tue Dec 08, 2009 02:59    Post subject: Reply with quote

Вставлю лыко в строку.
Любой ХЭШ есть сжатие с потерями.
Представляется наиболее разумным следуюющий подход:
Выбираем некую константу, для размера блока, меньшую сегмента памяти.
Скажем, 4 килобайта.
Все файлы, требующие сравнения, длина которых меньше этого блока,
просто сравниваются друг с другом. (строим дерево, для ускорения сравнения, представляя данные как очень длинное число)
Файлы большей длины обсчитываем быстрой CRC(иной хэш), разбивая на блоки такой длины, чтобы в общая длина всех CRC блоков + CRC всего файла занимали этот блок.
Далее - аналогично маленьким файлам.
Но, еще с одной итерацией.
Если, по Дирихле, в узел дерева (ящик Дирихле), попадёт более одного элемента - проводим полное сравнение файлов.
Чем больше длина блока -тем лучше работает метод.
Расход памяти на посроение деревьев и выделение блоков может быть значительным.
Возможно, имеет делать предварительное построение еще одного дерева по длинам файлов и запускать этот алогритм для каждого узла отдельно.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Total Commander Forum Index -> Программное обеспечение All times are GMT + 4 Hours
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
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