> Смотря что ещё дополнительно известно про содержимое файлов. Одно дело, когда внутри текст в latin1, другое дело, когда набор из /dev/random
Глупости. Какая разница, что там внутри. Есть два подмножества из N членов. Вероятность совпадения определяется одной формулой. Я не помню. То-же самое, если взять два набора цифр от нуля до девяти и подсчитать вероятность того, что они высроены в том-же порядке.
Я так понимаю, что это произведение вероятностей совпадения
i-тых байт соответственно: P{a_i = b_i}.
Поскольку P{a_i = b_i} = P{a_j = b_j}, то вероятность равна
(P{a_i = b_i})^N
P{a_i = b_i} = 256 / (256*256) = /*252^2 - число всевозможных
комбинаций a,b*/
= 1/256
Т.е. ответ (1/256)^N
>Вот и интересно - какова вероятность совпадения двух исходников.
Либо надо попытаться максимально точно описать содержимое файлов, либо тупо посчитать как для "случайного набора буков". Второе проще, но результат будет весьма далёк от правильного, первого значения.
Второй вариант.
Пусть в тексте используется m знаков (сколько их там на самом деле -- посчитаешь). Тогда для данной работы длиной N символов вероятность совпадения с другой работой (такого же размера) равна (1/m)^N.
Ананимус-школьник=тян детектед, про Шеннона слыхом не слыхивал. Двойка.
P.S. Вероятность зависит от языка программирования, стиля писавших исходники, их характеров и много еще. Если оба любители писать строго по книжке, то весьма большая.
> Какая разница, что там внутри. Есть два подмножества из N членов. Вероятность совпадения определяется одной формулой.
Чуваки, вы Шеннона и Котельникова не проходили в школе?
Есть информационная энтропия, которая зависит именно от характера содержимого файла.
Например, какой минимальный размер архива ты получишь, если будешь сжимать файл и почему меньше некоторого размера файл не получится, сколько раз не сжимай результат с прошлого шага? Потому что упрёшься в информационную энтропию.
А энтропия информации = условная вероятность, как тут уже написали. При шифровании энтропия сохраняется, так что нормальная криптография должна "скрывать" характер информации, не позволяющий косвенно оценить энтропию и статистически поломать шифр.
> Вот и интересно - какова вероятность совпадения двух исходников.
читать про трансформации исходного кода, рефакторинг, метапрограммирование, преобразования AST, обфускаторы.
Оценивать "совпадение" надо семантики, а не текста-в-текст буквально. Грубо говоря, если ты переименуешь переменные и навставляешь левых неиспользуемых или промежуточных переменных, всё равно AST у тебя не изменятся и это будут одна и та же программа. Если AST изоморфны, почти то же самое.
"вероятность совпадения двух исходников" в смысле кто у кого спёр легко определяется кто с кем мог контачить, анализом стиля. Был в интернете сайт-программа какого-то препода, которая автоматически определяла плагиат, погугли.
>Вот и интересно - какова вероятность совпадения двух исходников.
как препод я тебе скажу, что из двух курсов обычно бывает процентов 20-30% уникальных работ, они сразу запоминаются, потом у каждого студиозуса если есть что сказать, есть работа, то у него есть свой стиль, который проглядывает между строк. Так что кто у кого спёр сразу видно, всё равно работ-то мало и они все на виду.
>Вероятность зависит от языка программирования, стиля писавших исходники, их характеров и много еще. Если оба любители писать строго по книжке, то весьма большая.
+1, вероятность побайтного совпадения двух хеллоувордов одинакового размера близка к единице.
два произвольных файла из /dev/urandom, как тебе тут уже писали или всё-таки текст?
если текст, то на каком языке? живой естественный язык или формальный язык программирования?
например, в разных языках частоты встречаемости *букв* разные. Если просто составить таблицы частот, а потом симметрично зашифровать (например, одноразовым криптоблокнотом, читай "Криптономикон" Н. Стивенсона, увлекательная байка) -- можно определить язык, на котором текст.
идём дальше. Если у нас текст на каком-то естественном языке, не все *слова* равновероятны. Не все пары букв/слоги равновероятны, и вероятность след. элемента таки зависит от вероятности предыдущего. Грамматика, синтаксис предложения -- разный, и если фиксированный порядок частей предложения, это тоже влияет на частоту.
Возникают "марковские цепочки" вероятностей встречаемости элементов предложения (букв в слогах, слогов в слове, слов в предложении).
Например, как работает бредогенератор текста вроде http://vesna.yandex.ru ? анализирует встречаемость элементов, условную вероятность для разных стилей текста по базе текстов в одном стиле; строит марковские цепочки вероятности, причёсывает синтаксис, (тут уже начинается анализ ЕЯ)
А для авторских работ это в каком-то смысле проще -- у каждого автора вырабатывается свой уникальный стиль который плагиаторы копипастой переработать не в состоянии, так что простой литературоведческий анализ работ автора может сказать, свой он у него или "на основе" другого автора или стянут целиком. Конечно, для нормального анализа должно быть достаточно много материала.
с формальными языками вроде языков программирования в чём-то проще, но в целом так же (в чём-то стиль заметить ещё проще).
В общем, дети, читайте книжки, хотя бы с того же "Код"а Петцольда, курите буквари по радиотехнике, теории информации и криптографии
и нарабатывайте свой язык, пишите материала *много* чтобы ваш плагиат было хотя бы не так заметно :)))