Размер словаря

при этом я ни за что не поверю, что алгоритм генерации уникальных айди на основе строк настолько важен, что его нельзя рассекретить :-)

да, это один вариант: префиксный код.

второй вариант: префиксное дерево. вот только все-таки по моим подсчетам см. их выше с поправкой, что все-таки средняя длина слова в словаре не 8, а 9 байт, все-таки побольше 300к получается. 400-500.

А вот Артизан утверждает, что есть еще один вариант хранения, и что он как раз влезает в 300 к для 100 тысяч словооснов. Могу с натяжкой поверить, но проверить увы.

любая реализация идеи имеет свою цену, но вот когда человек говорит что я знаю как но никак не может подтвердить свои слова это уже наводит на нехорошие мысли :-(

примерно такую схему я и пытаюсь релизовать сейчас, каждое словоформ апредставлена примерно следующей матрицей {приставка|основа|окончание}, именно такой массив матриц я и хочу получить на выходе после фильтрации запроса через словарь

itman, дело ведь не в средней длине слов, а в средней длине той суффиксной их части, которая меняется при переходе от слова к слову в упорядоченом по алфавиту словаре.

Только за хорошее вознаграждение, ...

Иногда для открытия тайны достаточно одного слова,

поэтому на дешевые разводы типа этого я не ведусь, ...

ох, блин

awk 'BEGIN{p="";s=0;}{m=0;for (i=1;i<=length($1) && i<=length(p) && substr($1, 1, i) == substr(p, 1, i); ++i) m=i;;p=$1;s+=1*sprintf("%d",0.5 + 0.5 + 5/8.0*(length($1) - m));}END{print s/1024}' dict1

297.629

wc  dict1

106242  106241 1138871 dict1

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

Значит поясняю первый 0.5 это для округления, второй это 4 бита на хранение длины, далее длина суфикса из расчета 5 битов на букву.

Если сказали А, то говорите Б, а то мы будем думать, что это и есть дешевый развод. Меня, кстати, безумно радует эта атмосфера секретности. При этом, как показывает опыт, если копнешь поглубже, то все эти так называемые секреты или ошибка эксперимента (то бишь забыли, преувеличили, итд итп), или давно уже опубликовано. Так что, просим аргументы в студию, иначе будем считать, что профессор зачот не сдал :-)

То что можно умять словарь в 300kb как я писал выше

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

Да, но речь шла не просто про умять, а про умять и искать. а префиксные коды искать позволяют только последовательно.

это раз. Наверное, можно туда запихнуть указатели с префиксными метками для бинарного поиска. Получится некий гибрид с деревом. Если много меток вставим раздуется размер, будет 400-500к, если мало будет скорость не очень.

потом Вы так и не обосновали существование надежного способа генерации id (пусть и с дырками) по строковому представлению. это два.

PS: кстати, вот http://company.yandex.ru/articles/article5.html статья Ильи, только я в ней никогда ничего почти не понимал, потому что Илья ее тоже, похоже, писал старательно конспирируясь.

Кстати, после внимательного прочтения статьи, понимаешь, что там поиск не гарантирует стопроцентную точность. отсюда и такой малый размер quad erat demonstrandum.

И это правильно, ...

о, смотрите мой комментарий выше про статью я там поправил. итого 300 кб - это не стопроцентно точный, рандомизированный алгоритм.

- хорошая статья! И очень даже понятная.

Вот как там написано, так и надо делать!

А если отказаться от идеи, что коды должны следовать подряд, то вообще лепота получается: на каждое кодируемое слово требуется только [один бит]*[фактор разреженности хэш-таблицы]

Другое дело, что ОБРАТНАЯ задача (перевод хэш-кода в слово) - компактно, наверное, не реализуема ...

______________

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