Re: Посоветовать хэш

От Alexander Gusak (2:5020/175.2) к Alex Mizrahi

From: "Alexander Gusak" <agusak@skengstroy.ru>

Tue Sep 01 2009 17:49, Alex Mizrahi wrote to Alexander Gusak:

 AM>>> Хэш-функция ДЛЯ МHОЖЕСТВА S. Очевидно это подразумевает что множество

 AM>>> S известно.

 AG>> Вовсе неочевидно. Это подразумевает, что известны _некие

 AG>> характеристики_ множества S, достаточные для реализации.

 AM> Hе некие характеристики, а само множество. В каком виде оно

 AM> известно -- это дело десятое. Разумеется, не обязательно иметь

 AM> его в виде списка файлов на винте, достаточно будет знать _некие

 AM> характеристики_ этих файлов -- типа, поле A ограничено значениями 7-11,

В данном случае, мы некоторые вполне достаточные характеристики и будем знать.

 AM> Совершенно очевидно, что произвольные бинари пожатые bzip'ом (именно о

 AM> таком контенте говорит паразит) не могут иметь никаких закономерностей.

Однако известно (со слов автора), что файлы не совсем произвольные, а с

размером в пределах 10К. Это уже никак не произвольное, а конечное и

определенное, хотя и достаточно большое множество. Мы же в задаче имеем дело с

его опять же конечным, хотя и тоже немалым, подмножеством.

 AG>> Ты пропустил начало. А в начале я предложил заложиться на три порядка

 AG>> от ожидаемого количества файлов, с тем чтобы зафиксировать одну из

 AG>> характеристик множества.

 AM> Ты не понимаешь... Когда ты делаешь хэш таким чтобы он работал на будущих

 AM> файлах, тебе нужно заложить не на количество будущих файлов, а на

 AM> количество ПОТЕHЦИАЛЬHЫХ будущих файлов, т.к. нужно будет определить

 AM> ЛЮБОЙ потенциально возможный файл. А количество этих потенциальных файлов

 AM> велико.

Здесь приходится только довериться автору, что уж совсем произвольные файлы в

задаче появиться не могут - пусть даже бзипом жатые, но какого-то

предсказуемого размера.

 AG>> Да, мощность должна быть ограничена.

 AM> Hу, положим, мощность всегда ограничена, но тут надо чтобы она была

 AM> ограничена какими-то вменяемыми пределами.

Hу, мы же сейчас не можем сказать, вменяемые это пределы или нет. Это уже от

ТЭО и доступных ресурсов зависит.

 AG>> Для совсем произвольного контента конечно. А для контента, о котором мы

 AG>> делаем эти предположения, достаточно взять хэш на 81921 бит, нет?

 AM> Хэш на 812921 бит -- это сам файл. Да, такой вариант предлагали, бери

 AM> хэш функцию f(x) = x, она является perfect hash для любого множества,

 AM> правда, радости не приносит.

Хэш в данном случае может быть более удобен по сравнению с самим содержимым

файлов не только размером. Может быть, по этой функции окажется быстрее поиск,

или просто даст возможность например на удаленном АРМ проверять возможность

добавления файла в базу, не имея доступа к самим данным - по соображениям

конфиденциальности скажем. Варианты есть, это уже дело хозяйское зачем оно

именно так понадобилось.

С уважением

Александр Гусак

--- ifmail v.2.15dev5

 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким