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

От Eugene Grosbein (2:5006/1) к Alexander Gusak

Reply-To: eugen@grosbein.pp.ru

02 сен 2009, среда, в 15:12 KRAT, Alexander Gusak написал(а):

 AM>> Понимаешь, математика так не работает. Это не юриспруденция, где может

 AM>> открыться какое-то новое видиние. В математике, если хотя бы одним

 AM>> методом что-то доказано, приведён хотя бы один контрпример показывающий

 AM>> невозможность

 AM>> чего-то -- то всё, дело можно закрывать,

 AG> Чего доказано-то? В реале доказано, что PFH существуют для любого

 AG> множества,

 AG> вопрос только в размере, занимаемом описанием функции и нужными ей

 AG> данными,

 AG> причем теоретически обосновано и соотношение между числом элементов

 AG> множества

 AG> и количеством бит в функции. Есть научная литература по этому вопросу,

 AG> есть

 AG> стандартные библиотеки генерации таких функций -

 AG> http://cmph.sourceforge.net/

 AG> например:

 AG> The CMPH Library encapsulates the newest and more efficient algorithms in

 AG> an

 AG> easy-to-use, production-quality, fast API. The library was designed to

 AG> work

 AG> with big entries that cannot fit in the main memory. It has been used

 AG> successfully for constructing minimal perfect hash functions for sets with

 AG> more than 100 million of keys, and we intend to expand this number to the

 AG> order of billion of keys.

 AG> То есть существует что-то похожее на то, что хотел автор, и куда его можно

 AG> направить копать. Чего еще надо-то?

Hадо ещё конструктивности. Теория алгоритмов выросла на конструктивных

доказательствах и отказе от использования аксиобы выбора.

У AAP множество заранее неизвестно, то есть совсем неизвестно

(приблизительный средний размер файла и компрессия bzip2 ничего не дают).

Существует конструктивное доказательство, когда PFH строится для

произвольного множества, а не по нему? :-)

Eugene

--

За то, что сердце в человеке

Hе вечно будет трепетать

--- slrn/0.9.8.1 (FreeBSD)

 * Origin: Svyaz Service JSC (2:5006/1@fidonet)

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

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

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