Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Вероятность одинакового CRC32

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки
Страницы: 1 2 3

Открыть новую тему     Написать ответ в эту тему

UncoNNecteD



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Две хэш функции - дело хорошее.  
Вероятность падает во много раз

Цитата:
В такой логике при уменьшении размера этого куска вероятность бы падала и становилась бы минимальной для одного байта.

Нет, до 32 бит - то есть до 4х байт. В принципе - так оно и есть, на 4х байтах данных вероятность совпадения CRC32 минимальна

----------
Мой-борд

Всего записей: 4040 | Зарегистр. 21-03-2002 | Отправлено: 19:10 10-08-2004
daru

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
У меня другой вопрос по CRC.
 
Например, есть некая фамилия, имя и дата рождения. Например, Pupkin Vasisualiy, 03/18/1979. Из этих данных и формируем строку 'PupkinVasisualiy03/18/1979'. Вычисляем
CRC16, получаем четыре цифры, храним их в базе. Теперь, собственно, вопрос. Какова вероятность, что попадется другая фамилия, имя и дата рождения (включая даже "невозможные" в жизни варианты даты рождения 99/99/9999 или такие фамилии/имена как PuPkiNvAsiSuALiY), что мы "нарвемся" на коллизию? Вариантов входных строк - 1 миллион. Есть какая-то формула, по которой можно было бы такую вероятность вычислить? Для строк одинаковой длины? Разной длины с максимальной длиной такой-то? Или, другими словами, нужно число коллизий на 1 миллион входных данных.

Всего записей: 12 | Зарегистр. 22-09-2004 | Отправлено: 17:51 02-12-2004
redp

Full Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
daru
элементарно - 2 в 16 степени
что гораздо меньше чем 1 миллион входных данных

----------
помни - ты с потрохами принадлежишь государству

Всего записей: 514 | Зарегистр. 16-06-2003 | Отправлено: 18:10 02-12-2004
UncoNNecteD



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Вероятность совпадения - у 15% записей.
(1000000/(2^16)=15.258).

----------
Мой-борд

Всего записей: 4040 | Зарегистр. 21-03-2002 | Отправлено: 18:17 02-12-2004
daru

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Как-то подспудно я с этим не согласен. А вдруг все коллизии для данной фамилии pupKINVaSiSualiy03/18/1979 - строки, содержащие невводимые с клавиатуры символы? Другими словами, если формировать по указанным правилам строки, (а особенно меня интересует случай, когда мы не выделываемся в остальных случаях с маленькими/большими буквами, а пишем с большой буквы или вообще все маленькими), то может и не найдется такая фамилия, имя и дата рождения, с которыми мы попали бы в коллизию?

Всего записей: 12 | Зарегистр. 22-09-2004 | Отправлено: 17:22 06-12-2004
UncoNNecteD



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
daru
CRC от этого не зависит.

----------
Мой-борд

Всего записей: 4040 | Зарегистр. 21-03-2002 | Отправлено: 17:57 06-12-2004
ueban



Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Как я понимаю CRC-код это остаток от деления полиномов, где делимое - это данные по которым вычисляется СRC (длинна произвольная), а делитель - полином СRC ( какой то определенный полином с постоянной разрядностью). И если я все правильно понимаю, то количество возможных повторений напрямую зависит от полинома СRC(т.е его разрядности). В принципе если увеличивать ее то можно уменьшить количество повторений(есс-но разрядность полинома СRC должна быть меньше разрядности кодируемых данных).

Всего записей: 12 | Зарегистр. 02-12-2004 | Отправлено: 12:48 08-12-2004
UncoNNecteD



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
ueban
CRC само по себе имеет разрядность. И соответственно количество значений в базисе.
Так что дели на любое число - вариантов больше не станет.

----------
Мой-борд

Всего записей: 4040 | Зарегистр. 21-03-2002 | Отправлено: 12:56 09-12-2004
basilevs

Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
ShIvADeSt писал
>так что ЦРЦ вполне может совпасть и я не вижу причины, почему он не может, а вот хэш >?это совсем другое дело, вот он по своей сути не должен совпадать, так как принцип >формирования хэш (его алгоритм) и само определение хэш-функции исключают эту >возможность.  
 Почему это исключает? Просто вероятность совпадения соотносится как длины
 2**(CRC/YourHash).
 
 А вот идея насчет двух CRC (например 32 и 16 разрядной) -хороша.
 Поскольку фактически мы делим число на два простых делителя (а полиномы
 выбирают именно так) и вероятность совпадения двух остатков существенно ниже.
 А если использовать табличные или иные бысрые методы обсчёта, то скорость
 будет хорошей.
 Могу показать хороший метод для CRC16 на полиноме 0XA001 (код для x86).
 Реализация - моя.
function CRCb(CRC:word;sym:Byte): word;
 asm {DL-sym,AL-loCRC,AH,hiCRC}
XOR DH,DH
XOR AL,DL //sym xor LoCRC
JP @ll1
MOV DH,$C0
XOR AH,$01
 @ll1:
  MOV   DL,AH
  MOV   AH,AL
  XOR   AL,AL
  RCR   AX,1
  XOR   DX,AX
  RCR   AX,1
  XOR   AX,DX
end;
 
 
 

Всего записей: 161 | Зарегистр. 09-12-2004 | Отправлено: 18:42 10-12-2004
whungry

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
basilevs
 
   Следует исходить из ЦЕЛИ создания/выбора алгоритма CRC: обнаружение ошибок/изменений СЛУЧАЙНОГО характера при передаче по каналам (извините за тавтологию) передачи данных. И такие случайные изменения этот алгоритм ловит замечательно. Правда остаётся (как в известной поговорке) тот самый дьявол, что кроется в подробностях. В данном случае - те самые коллизии (совпадающие CRC-суммы от разных проверяемых блоков данных). Для CRC16 - вероятность 2**16.  В случае применения двух разных CRC16 вероятности снова "нарваться" на коллизию будет равна (2**16)*(2**16)=2**32. Чистая математика. Что эквивалентно использованию одной CRC32. Вплоть до времени расчета CRC-сумм, если у вас конечно программы подсчёта CRC правильные (без  наворотов из-за горе-программиста).  
   Как говорил герой одной рекламы: "Отсюда вывод". Будете Вы брать 50 Mbyte, 50 Kbyte, 1 Kbyte, 0.5 Kbyte или 50 byte; из середины, из конца или начала файла (только не из самого начала или конца - чтобы не попасть на стандартный дескриптор полей/файла); будете брать байты подрят, через один или задом наперёд; CRC16 + CRC16 или CRC32; CRC16 + CRC32 или CRC48 - алгоритму ВСЁ РАВНО. Такими трюками вы можете "запутать" только программиста, но не программу(алгоритм). Ей это всё (простите за солдафонство)  - монопенисуально.
 
 
Добавлено:
daru
 
Увы (или наоборот), но алгоритм CRC не является позиционным, то есть при обработке сообщения не учитывается положение содержащихся в нём байт. И также не учитывается положение бит в байте. Поэтому использование определённых правил написания имени и даты приводят лишь к тому, что некоторые биты в идентификаторе будут предопрелены и их значения зафискированы. Это плохо. Но оставшиеся "переменными" биты будут по прежнему влиять и менять итоговое значение CRC. Это хорошо. В итоге - если число "переменных" бит будет больше разрядности CRC, то это полностью компенсирует наличие предопределённых бит, сведёт их влияние практически к нулю. Рассмотрим дату dd/mm/yy. Для каждой цифры мы имеем три "переменных" бита, таких цифр шесть, итого 3*6=18 бит. Для адгоритма CRC16 - этого хватит с головой. Прикинем для CRC32: нужно ещё 14...16 "переменных" бит. Для каждой буквы имеем минимум 4 таких бита (ведь у нас больше 2**4=16 разных букв ?). Значит, если под имя отвести больше 16/4=4 символов, то влияние НЕСЛУЧАЙНОСТИ букв в имени и цифр в дате будет нивелировано. Видите, как просто. Согласитесь, это даже не математика. Это просто арифметика.

Всего записей: 9 | Зарегистр. 11-05-2006 | Отправлено: 15:38 13-05-2006
basilevs

Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
whungry
Совершенно верно. Вывод абсолютно точен. Именно 2**(16+32) и будет вероятность совпадения для двух CRC. При том, что метод CRC16+CRC32 будет быстрее, чем некий
 CRC48. А стандартная CRC  (2**N) есть всего навсего наблюдатель порядка N с компенсационным звеном порядка N. (которое на каждом отсчете высчитывает  воздействие для компенсации возмущения). Можно перейти и к алгебре. А передача данных - всего лишь приложение.

Всего записей: 161 | Зарегистр. 09-12-2004 | Отправлено: 12:30 22-05-2006
whungry

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
basilevs
 
  Простите за цитирование самого себя, но всётаки:
 

Цитата:
 Что эквивалентно использованию одной CRC. Вплоть до времени расчета CRC-сумм, если у вас конечно программы подсчёта CRC правильные (без  наворотов из-за горе-программиста)

 
  Как алгебраически вычисление CRC32+CRC16 быстрее, чем вычисление CRC48 из-за того,что вычисление ОСТАТКА деления на ПОЛИНОМ-48 сложнее и значит дольше.
  А вот алгоритмически такие полиномы реализуются через операции сдвига в регистрах, где на каждую операцию требуется одна ассемблерная команда. Возникает вопрос о том, что операнд должен целиком помещаться в регистре, а 48-битный операнд в i386 "пролетает".
  Но во-вторых, 64-битные процесоры уже вовсю пошли "в народ".
  В-третьих существует ассемблерная инструкция СКВОЗНОГО сдвига ДВУХ регистров.
 
  А во-первых, те программисты, у кого от ума не горе, а только радость, для подсчета
CRC-XX используют табличные подстановки, где на ОДИН входной байт последовательности данных выполняется XX/8 подстановок по XX/8 таблицам соответственно (для CRC32 - по одному байту из 4 таблиц).
  Получаем, что для CRC32+CRC16 нужно (32/8)+(16/8)=4+2=6 операций, а для CRC48 потребуется уже (48/8)=6 операций. Почувствуйте разницу.
 
  И снова арифметика рулит!
  А "залезать" в алгебру - дык, мы ведь Академиев имени ФСФ не кончали.
  В-прочем, если интересно, читай P.S.
 
  P.S.  Данную тему в своё время пришлось осваивать методом "научного" тыка (ну не было у меня программисткого образования за иключением одного семетра языка FORTRAN). И даже, не смотря на в целом о-о-очень приличное образование, курса "Теория чисел" у нас не было (самому не понятно почему). Жутко комплексуя, полез я в книги, чтобы самообразованием это как-то поправить. Так вот, оказалось, что всякие университетские курсы и учебники замечательно подходят для .... доказательства теорем. А для понимания МЕХАНИКИ процесса - совсем наоборот. Мой практический опыт программирования оказался нагляднее и понятнее. И читая про знакомые вещи часто ловил себя на мысли "Экак батенька у Вас всё запуще.. то есть запутано!"
Не берусь распространять этот подход на всё программисткое образование, но определённый компромис между теорией и практикой наобходим - это точно. Причём именно компромисс, в смысле его определения - "то, с чем согласны все, но что не устраивает никого".
 
  P.S.S А может пора закрыть ветку - два года никто не интересовался вопросом (я сам - исключение: сначала запостил, потом на дату посмотрел) ?
 

Всего записей: 9 | Зарегистр. 11-05-2006 | Отправлено: 19:45 14-08-2006
SERGE_BLIZNUK

Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
но алгоритм CRC не является позиционным, то есть при обработке сообщения не учитывается положение содержащихся в нём байт

или я вас не понял, или вы глупость изволить говорить...
 
байты:
  ABCD
crc32:DB1720A5
 
байты:
  BACD
crc32:CBE43112

Всего записей: 2005 | Зарегистр. 12-09-2002 | Отправлено: 20:51 14-08-2006
begem0t



Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
чтото мне подсказывает, что если и будет в коллекции дубль какогонибудь фильма, то это не приведет к ядерной катострофе, такчто для указанной цели тема сделаных постов не стоит

Всего записей: 901 | Зарегистр. 06-01-2003 | Отправлено: 08:58 15-08-2006
HANDLE

BANNED
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
А чем md5 не устраивает?
 
md5 - время - размер - файл
 
A15AD4ADC2419CD17CFBDACE7F64044E  12.50 s  509411328 b for Terminator 3 (hobbit edition).avi
7CFF6AB689F5EB253B99B954BB4A71E5  33.11 s 1469149184 b for Бой с тенью.(Россия).avi
BF796534364C476AD9D728737B4AC463  16.52 s  721246208 b for Достучаться до небес.avi
B105603CC672F5BADDE0E0CC0EE76D8B  16.84 s  734447616 b for Игры мотыльков.avi
4FE73D33710298D7C5D5AB5DEF201004  13.86 s  604792320 b for Один в темноте (Alone in the dark).avi
A646A5A83B978E7C878306F9B4F4F28F  16.38 s  714821632 b for Электра.avi
F89BE64B9212ADD14D50781CB0B7EEC6  33.43 s 1506340864 b for Пираты Карибского моря.avi
C5077C9980D06DF2A384D4B6E846FF1E  16.14 s  730875904 b for СФЕРА.avi
01F2DAF81DAFC2CF289F14211FBB5DE9  15.62 s  706471936 b for Ночной дозор.avi
1A26D117095514C13DAC5A4729B3199C  14.96 s  712239104 b for 40 дней, 40 ночей.avi
6740533BD0EC5A321D50A09E5E62F3E7  14.84 s  706191360 b for 50 Первых поцелуев.avi
B92A9BAE6474C457012A461C13862201  13.82 s  685217792 b for Мартовские коты (Tom cats).avi
FCD8FB77275177857FCEC276D1B207BF  16.29 s  780216320 b for Мимино.avi
6621701EB621C39612D2495864BC6CFD  15.02 s  715808768 b for Одиночество крови.avi
329042B71F645A116814E05C1BC7C293  18.53 s  882573312 b for Паспорт.avi
72EDC1771CC39A388028C215E5773EE6  20.71 s  986814464 b for Приключение итальянцев в России.avi
70B399CDDB1A42014A50ADEE0BF2501A  14.88 s  708194304 b for Свадьба.avi
DBAAAC4B2DC21B0B8A76E9F972C949BA  26.58 s 1265868800 b for Служебный роман.avi
4F694A374974B154100073AC5631EA1D  15.41 s  733796352 b for Troi2.cd1.avi
137FA36068CC23D07190DB25F1C218F6  15.59 s  733863936 b for Troi2.cd2.avi
7BFA92206D73B633793901E70E1D5303  15.38 s  732409856 b for Spider-Man2_CD1.avi
A03D922F1615F088211128051ABC7D78  15.43 s  735313920 b for Spider-Man2_CD2.avi

Всего записей: 364 | Зарегистр. 25-02-2006 | Отправлено: 11:29 15-08-2006
SPlyer



Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Никто не знает, какой алгоритм используют в пиринговых сетях ? Просто md5 от файла?

Всего записей: 240 | Зарегистр. 06-06-2004 | Отправлено: 12:41 15-08-2006
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
basilevs
Простите за мою неопытность, а можно поподробнее про вероятность и степень двойки?
Эта вероятность того, что текущий CRC совпадает с CRC пакета данных, или это вероятность того что такой CRC может быть у такого пакета данных?
 
Честно говоря я не понимаю некоторых технических тонкостей. А именно как можно говорить о вероятности при приёме двухбайтового CRC отвечающего за двухбайтовую посылку? Например если я буду просто удваивать данные, то вполне понятно, что 0x0123h соответствует именно $0123, а не $1230. Таким образом вероятность попадания искажающего сигнала на двухбайтный CRC одновременно c попаданием искажения на двухбайтную посылку идущую перед CRC не такая же, как если бы посылка была двухкилобайтной?
Если так то знание аббревиатуры CRC не спасает вероятность в случае с короткими посылками или при переходе в аналоговую форму происходит расширение двух байт и сужение CRC соответствующим уровню модуляции/демодуляции? Думаю что мои домыслы слабо понятны, а вопрос тем не менее понятен.

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 11:41 29-08-2006
basilevs

Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Pinocchio
Вообще не понял вопроса. Введение CRCm есть внесение некоторой избыточности в передаваемой информации. Для пакета длиной в N-байт избыточность можно оценить
 как (N+lb(m))/N. (для CRC16 = (N+2)/N)
 При искажении в посылке произвольного количества бит вероятность совпадения CRC
 в точности равна обраному от числа возможных значений, принимаемых CRC16. (т.е. =1/2**16)
Другое дело, что для стандартных CRC16  ($A001 и $1021) искажающий сигнал, сохраняющий целостность посылки, должен представлять собой суперпозицию из набора единичных возмущений и их следов.
 
Подводя итог, скажу, чудес не бывает, только повышение избыточности сигнала до приемлемого соотношения сигнал/шум.

Всего записей: 161 | Зарегистр. 09-12-2004 | Отправлено: 20:45 29-08-2006
TP09H

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
По моему,нет алгоритма для создания строки,однозначно идентифицирующей данные,так как кол-во однозначно идентифицирующих комбинаций не будет>2^<длина данных в битах>

Всего записей: 18 | Зарегистр. 19-09-2006 | Отправлено: 13:28 21-10-2006
basilevs

Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Думал, что тема заглохла.

Цитата:
По моему,нет алгоритма для создания строки,однозначно идентифицирующей данные,так как кол-во однозначно идентифицирующих комбинаций не будет>2^<длина данных в битах>

Еще раз повторю, что избыточность - вот ключевое слово. Если исходная комбинация -избыточна - возможно сжатие без потерь. Все сигнатуры - всего навсего есть способы сжатия с потерями. И дают возможность сравнивать два комбинации с некоторой вероятностью, которую можно оценить как P=1/2^^LenghtSignature в пределе.
 
 

Всего записей: 161 | Зарегистр. 09-12-2004 | Отправлено: 16:12 21-10-2006
Открыть новую тему     Написать ответ в эту тему

Страницы: 1 2 3

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Вероятность одинакового CRC32

Имя:
Пароль:
Сообщение

Для вставки имени, кликните на нем.

Опции сообщенияДобавить свою подпись
Подписаться на получение ответов по e-mail
Добавить тему в личные закладки
Разрешить смайлики?
Запретить коды


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.Board
© Ru.Board 2000-2018

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru