Re: Посоветовать хэш
От Alexander Gusak (2:5020/175.2) к Eugene Grosbein
В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)
From: "Alexander Gusak" <agusak@skengstroy.ru>
Wed Sep 02 2009 22:05, Eugene Grosbein wrote to Alexander Gusak:
AG>> То есть существует что-то похожее на то, что хотел автор, и куда его
AG>> можно направить копать. Чего еще надо-то?
EG> Hадо ещё конструктивности. Теория алгоритмов выросла на конструктивных
EG> доказательствах и отказе от использования аксиобы выбора.
EG> У AAP множество заранее неизвестно, то есть совсем неизвестно
EG> (приблизительный средний размер файла и компрессия bzip2 ничего не дают).
EG> Существует конструктивное доказательство, когда PFH строится для
EG> произвольного множества, а не по нему? :-)
Hасчет доказательства не знаю, искать лень. Hо раз в описаниях алгоритмов
ничего не говорится о требуемых данных, кроме их количества и размера, наверно
они соответствуют?
Hасколько я понял, активная возня вокруг этой темы идет в связи с бурлением в
поисковых системах, где надо индексируемые страницы как-то идентифицировать.
Поэтому для проверки алгоритмов просто берется база URLов типа гуглевской, по
ней делается произвольная выборка в миллиард ссылок, и с них вытаскивается
первые 64 байт содержимого по данному адресу - это и есть множество. Думаю,
произвольностью оно мало уступает заданному.
First, the algorithm is linear on the size of keys to construct a MPHF, which
is optimal. For instance, for a collection of 1 billion URLs collected from
the web, each one 64 characters long on average, the time to construct a MPHF
using a 2.4 gigahertz PC with 500 megabytes of available main memory is
approximately 3 hours.
The description of a MPHF takes a constant number of bits for each key, which
is optimal. For the collection of 1 billion URLs, it needs 8.1 bits for each
key, while the theoretical lower bound is ~1.4427 bits per key.
Коли есть теоретический предел, должна быть и теория.
С уважением
Александр Гусак
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Ответы на это письмо:
From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку
From: Username
Или коротким