Здравствуйте, Olegator, Вы писали:

O>А кстати, есть известные примеры коллизий?
Да.
http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html

Здравствуйте, Аноним, Вы писали:
А>А чего не хватает в условиях для того, чтобы признать её формализованной?
Вот это

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

по-прежнему не формализовано. По какому распределению берется вероятность?

Впрочем, не важно. Даже если Вы скажете, например, что распределение здесь равномерное, я помочь все равно не смогу Всего лишь хочу подтолкнуть к мысли, что полного математического описания задачи пока еще нет.

Здравствуйте,

есть желание найти/придумать алгоритм построения контрольной суммы, позволяющий обнаружить незначитильные изменения исходника по некоторому определённому изменению контрольной суммы.
например 32 байта).
Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

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

Возможно, такой алгоритм уже есть? Или есть доказательство, что такого алгоритма построить нельзя?

Здравствуйте, Аноним, Вы писали:

А>Или есть доказательство, что такого алгоритма построить нельзя?
В столь неформальной постановке ни о каком доказательстве не может быть и речи.

Вообще же стоит посмотреть в сторону алгоритмов хеширования CRC, MD5, SHA1 итп.

Здравствуйте, Mab, Вы писали:

Mab>Вообще же стоит посмотреть в сторону алгоритмов хеширования CRC, MD5, SHA1 итп.

Насколько мне известно, MD5 никаких выводов, по сравнению двух контрольных сумм, кроме проверки на идентичность сделать не сможет...

А>например 32 байта).
А>Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

Сорри, часть примера испарилась.

Пример:

Есть последовательность 200 чисел, и есть каким-то образом (каким?) полученная по ним сигнатура, длинной, например 32 байта.
Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).
Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт с достаточно большой степенью вероятности — "похожи" ли исходники — и насколько.

Здравствуйте, Аноним, Вы писали:

А>Насколько мне известно, MD5 никаких выводов, по сравнению двух контрольных сумм, кроме проверки на идентичность сделать не сможет...
В смысле -- кроме проверки на идентичность? Думаете не существует двух различных наборов данных с одинаковым MD5 digest?

Я всего лишь предложил (ввиду отсутствия формализованной постановки задачи) ограничиться эвристическими подходами.

Здравствуйте, Аноним, Вы писали:

Возможно есть смысл поспрашивать у народа, занимающегося теорией кодирования. Может быть какой-то стандартный код с обнаружением ошибок подойдет...

Здравствуйте, Mab, Вы писали:

Mab>В смысле -- кроме проверки на идентичность? Думаете не существует двух различных наборов данных с одинаковым MD5 digest?

конечно, существует

Mab>Я всего лишь предложил (ввиду отсутствия формализованной постановки задачи) ограничиться эвристическими подходами.

А чего не хватает в условиях для того, чтобы признать её формализованной?

Здравствуйте, Mab, Вы писали:

Mab>Возможно есть смысл поспрашивать у народа, занимающегося теорией кодирования. Может быть какой-то стандартный код с обнаружением ошибок подойдет...

Так а теория кодирования — это разве не алгоритмистика ?
А что за эвристические методы вы имели в виду?
А понять что имелось в виду, возможно, поможет пример, который я выше привёл?

Важна небольшая длина сигнатуры (например 32 байта).

Здравствуйте, Аноним, Вы писали:

А>Так а теория кодирования — это разве не алгоритмистика ?
Нет. Это раздел на стыке дискретной математики, алегебры и комбинаторики. Я им не занимаюсь

А>А что за эвристические методы вы имели в виду?
Общеизвестные хеши. Примеры я приводил. Формализованных гарантий, впрочем, никаких не будет.

Здравствуйте, Mab, Вы писали:

Mab>Нет. Это раздел на стыке дискретной математики, алегебры и комбинаторики. Я им не занимаюсь

жаль, значит, вопрос — действительно не к вам

Mab>Я всего лишь предложил (ввиду отсутствия формализованной постановки задачи) ограничиться эвристическими подходами.
А>>А что за эвристические методы вы имели в виду?
Mab>Общеизвестные хеши. Примеры я приводил. Формализованных гарантий, впрочем, никаких не будет.

такой эвристический метод, как md5, здесь, к сожалению, беспомощен.

А>>А чего не хватает в условиях для того, чтобы признать её формализованной?
Mab>Вот это...
Mab>Всего лишь хочу подтолкнуть к мысли, что полного математического описания задачи пока еще нет.

согласен :

Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт — насколько похожи исходники. Степень похожести идеальном образом выразило бы стремление к нулю суммы прибавленных к первой последовательности чисел взятых по модулю.

Если так нужна формализованность — возьмём этот идеальный критерий похожести.

Hello Mab, you wrote:

>> Или есть доказательство, что такого алгоритма построить нельзя?
> В столь неформальной постановке ни о каком доказательстве не может быть и речи.

Мне думается, что имелась ввиду "метрика", а не контрольная сумма.

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Аноним, Вы писали:

А>

А>Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт — насколько похожи исходники. Степень похожести идеальном образом выразило бы стремление к нулю суммы прибавленных к первой последовательности чисел взятых по модулю.

Стремиться к нулю может только функция Соответственно встает вопрос о том, что считать переменной в рассматриваемом случае.

Здравствуйте, Slava Antonov, Вы писали:

SA>Мне думается, что имелась ввиду "метрика", а не контрольная сумма.

Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

Здравствуйте, Mab, Вы писали:

А>>

Степень похожести идеальном образом выразило бы стремление к нулю суммы прибавленных к первой последовательности чисел взятых по модулю.

Mab>Стремиться к нулю может только функция Соответственно встает вопрос о том, что считать переменной в рассматриваемом случае.

переменной, очевидно следует считать пары различающихся последовательностей

Здравствуйте, Аноним, Вы писали:

А>переменной, очевидно следует считать пары различающихся последовательностей
И какая же топология вводится на множестве значений переменной...?

Hello Аноним, you wrote:

> Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

--
Всего хорошего, Слава
ICQ: 197577902

Hello Аноним, you wrote:

> Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Slava Antonov, Вы писали:

SA>У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

Конечно!

Метрика, математический термин, обозначающий правило определения того или иного расстояния между любыми двумя точками (элементами) данного множества А.
Метрика, принятое в обиходе название свидетельства о рождении…
Метрика, греч., учение о строении стихотворн. речи, ее ритмики

вы которое имели в виду?..
и в каком контексте?

Здравствуйте, Mab, Вы писали:

Mab>И какая же топология вводится на множестве значений переменной...?

Это зависит от того, что вы под этим понимаете — приведите точное определение со ссылкой на источник.

Хотя, я не вижу в этом особого смысла.
Из примеров вполне понятно, что имелось в виду. И если вы ничем полезным мне помочь не можете (в чём сами и признались) — может займётесь чем-то действительно полезным?..

Здравствуйте, Аноним, Вы писали:

А>Это зависит от того, что вы под этим понимаете — приведите точное определение со ссылкой на источник.
http://en.wikipedia.org/wiki/Topological_space

А>Из примеров вполне понятно, что имелось в виду. И если вы ничем полезным мне помочь не можете (в чём сами и признались) — может займётесь чем-то действительно полезным?..
-1

Честно говоря. я несколько разочарован, т. к. всегда считал, что на профильных форумах РАСД — завсегдатаи первым делом пытаются помочь, а флудом занимаются в специально отведённых для этого форумах...
Или вы просто мимо проходили больше не нашли где опрожниться?

Hello Аноним, you wrote:

>> У метрики есть строгое определение. Под которое md5 имхо явно не подходит.
<skip>

> вы которое имели в виду?..

А вы сами не догадались?

> и в каком контексте?

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

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Slava Antonov, Вы писали:

SA>То что вы хотите: определять близость элементов, что это как не метрика?
Ок, согласен.

SA>Хеши и контрольные суммы метрикой не являются.

Не спорю, но я этого и не утверждал.
Задача заключается в том, чтобы по близости "сигнатур", полученных в результате некоторого преобразования F, сделать вывод о близости исходников.
Итого — нужен способ опредения близости последовательностей (как исходных, так и результирующих).
И нужно само это преобразование F.

Метрику придумать несложно — например можно вычитать последовательности поэлементно друг их друга. И сложить получившиеся разницы.

А вот придумать преобразование F — с этим туже (если это вообще возможно).

А>есть желание найти/придумать алгоритм построения контрольной суммы, позволяющий обнаружить незначитильные изменения исходника по некоторому определённому изменению контрольной суммы.
А>например 32 байта).
А>Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

А>Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт с достаточно большой степенью вероятности — "похожи" ли исходники — и насколько.
Нужно более подробно описать, что вы подразумеваете под похожестью. Если подразумевается, что: на {1,2,3,4,5,6,7,8,9} {1,2,3,4,4,6,7,8,10} похоже, а {999,1,2,3,999,4,5,6,7} не похоже, то можно попробовать такую функцию:

1. Разбиваем строку на N подстрок, где N — размерность контрольного кода в битах (например, как вы выше предлагали 32 бита)
2. Для каждой подстроки суммируем её символы и сравниваем полученную сумму с числом =A*Q, где Q — количество символов в подстроке, A — усреднённый символ алфавита (сумма всех символов алфавита деленная на количество символов алфавита), для произвольных бинарных файлов A=127,5, для чисел от 1 до 10 А=5,5. Если сумма меньше, чем A*Q, то устанавливаем в контрольном коде бит, соответствующий данной подстроке, равным 0 иначе равным 1.
3. При сравнивании контрольных кодов учитываем количество различных бит. Чем меньше различных бит, тем больше "похожи" строки.

Плюсы этого алгоритмы:
1. Чем меньше различных подстрок у сравниваемых строк, тем больше шанс, что строки окажутся похожими.
2. Чем меньше изменения символов, тем больше шанс, что строки окажутся похожими.

Минусы и проблемы этого алгоритма:
1. Проблема пограничных значений: {127,127,127,128,128} окажется не похоже на {127,127,128,128,128}
2. Проблема "разрывного" алфавита: возможно, для решения этой проблемы, алфавит {1,2,3,999} стоит переопределить в {1,2,3,4}, хотя это зависит от задачи, может это наоборот будет плюсом.
3. Если будет много небольших отличий, то строки будут признаны похожими, хотя у них может не быть даже не одного одинакового символа. Будет это минусом или нет, опять же зависит от задачи, нужно подробнее определить, что вы хотите от "похожести"!

Еще один алгоритм придумал, если не усну, щас его напишу...

Если под похожестью подразумевается то, что на {1,2,3} одинаково похожи {2,2,3} и {999,2,3}, а {2,1,3} меньше похоже можно попробовать следующий алгоритм:
1. Разбиваем строку на N подстрок, где N = Nk/M — размерность контрольного кода в битах (например, как вы выше предлагали 32 бита) деленная на размерность хэш-кода, для каждой подстроки. Причем чем больше M, тем точнее результат, но чем меньше Nk/M, тем меньше степеней похожести сможет распознать алгоритм (в вырожденном случае он определит ОДИНАКОВЫ ли строки или нет). Так что придется искать компромиссное значение. Ну и чем больше Nk тем это сделать легче.
2. Для каждой подстроки вычисляем «качественной» хэш-функцией хэш-код и записываем его в соответствующую часть контрольного кода.
3. При сравнивании контрольных кодов учитываем количество отличающихся хэш-кодов подстрок. Чем меньше различающихся хэш-кодов, тем меньше различающихся подстрок, тем больше "похожи" строки.

Минусы и проблемы этого алгоритма:
1. Алгоритм не учитывает степень изменения символов. То есть на {1,2,3,4} ОДИНАКОВО непохожи {1,2,3,5} и {1,2,3,999}
2. Возможность коллизий хэш-функции. Но мне кажется, на практике от этого больших проблем не будет.

Hello Аноним, you wrote:

> Задача заключается в том, чтобы по близости "сигнатур", полученных в результате некоторого преобразования F, сделать вывод о близости исходников.

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

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Аноним, Вы писали:


А>Здравствуйте,

А>есть желание найти/придумать алгоритм построения контрольной суммы, позволяющий обнаружить незначитильные изменения исходника по некоторому определённому изменению контрольной суммы.
А>например 32 байта).
А>Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

А>Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт с достаточно большой степенью вероятности — "похожи" ли исходники — и насколько.

А>Возможно, такой алгоритм уже есть? Или есть доказательство, что такого алгоритма построить нельзя?
возможно я невовремя, но обычно используются алгоритмы сжатия например zip по нему уже очень легко определить схожесть сорцов
З.Ы. только глазами пробежался по постам, может упустил чего , прошу прощения

Здравствуйте, Mab, Вы писали:

Mab>В смысле -- кроме проверки на идентичность? Думаете не существует двух различных наборов данных с одинаковым MD5 digest?

А кстати, есть известные примеры коллизий?