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

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

From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

 AM>> Обосновать это очень сложно. Потому что оно выходит прямо из

 AM>> определения. Ты читал вообще статью по ссылке которую привёл? A

 AM>> perfect hash function _for a set S_ is a hash function that

 AM>> maps distinct  elements in S to distinct integers, with no collisions.

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

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

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

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

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

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

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

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

поле Б однозначно определяется полем A и В. Это достаточно чтобы посчитать

мощность и чтобы определить какие элементы включать в хэш.

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

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

 AG>  Ключевым элементом определения является другая его часть, "with no

 AG> collisions".

Ключевым элементом является то, что коллизий не будет на наперёд заданном

множестве.

 AM>> Если оно не известно, то что это будет -- неизвестная хэш-функция для

 AM>> какого-то неизвестного множества?

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

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

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

 AG>  Так что оно уже не совсем неизвестно. Оно уже не просто счетное, оно

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

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

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

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

потенциально возможный файл. А количество этих потенциальных файлов велико.

 AM>> Если хэш имеет конечное количество бит, то мощность множества S

 AM>> ограничена -- например, для 128-битного хэша это будет 2^128

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

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

ограничена

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

 AM>> Т.о. нужно каким-то образом наперёд выбрать из 2^81920 элементов 2^128

 AM>> элементов которые могут потенциально встретиться. Для произвольного

 AM>> контента это, очевидно, невозможно.

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

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

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

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

правда,

радости не приносит.

--- ifmail v.2.15dev5.4

 * Origin: Demos online service (2:5020/400)

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

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

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