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

я оплачу ваши знания, и может быть но их основе произойдет прорыв в микропроцессорной технике? Назовите вашу цену

При чем здесь микропроцессорная техника?

Задача умять словарь в 300kb оперативной памяти,

причем насколько я помню что написано у Yandex это

для одного пользователя на локальной машине.

Такую задачу я решил и могу объяснить как.

Чем больше будет с Вашей стороны тем

лучше будет с моей, предлагайте в приват, ...

Как я понял, нужен пример эффективного алгоритма, который использует кодированные (сжатые) данные, лежащие в оперативной памяти.

Могу привести в качестве иллюстрации свою давнюю реализацию игрока в одну игру для двух человек (Реверси). В памяти я хранил сжатые сценарии (насчитанные на тренировках или в процессе текущей партии), разворачивая на лету только те, которые мне нужны в данный момент. За игру обрабатывалось не более 15 процентов всех сценариев, поэтому это был вполне эффективный подход (т.к. декомпрессия была очень быстрой).

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

Так что не вижу проблемы. Бывают ситуации, когда в оперативной памяти совершенно нормально хранятся сжатые данные. Это не всегда имеет смысл, но для словарных задач, мне кажется, что это весьма распространённый подход. Во всяком случае, в те времена, когда 2 Мб оперативки были пределом мечтаний :) А ради 4 Мб можно было даже жениться :)

Я это делал на ЕС-1841 у которой

было 640kb оперативной памяти, ...

Круто! А я ЕСы потрогать не успел... :( Руки коротки были.

Начинал с Электроники-УКНЦ с 64К - тоже большая радость :)

(трудный день пятница - на оффтоп в серьёзных темах тянет. прошу простить)

а теперь пробуем применить это все на поисковый сервер, а не на локального пользователя, пусть даже это крупный сервер с распределением запросов на разные машины, какие процессорные ресурсы вам понадобятся для обеспечения декомпрессии при каждом запросе?

как вы собираетесь найти соответствия поисковому запросу в словаре кроме как развернув его весь?

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

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

выставляйте вашу модель на обсуждение либо покажите практичускую ее реализацию и мы обсудим ее стоимость

я готов легально купить технологию которая меня интересует, не вижу смысла прятаться в приват

Ладно, пробуем сначала простую задачу: пусть есть словарь вообще всех слов. На вход поступает слово, а надо понять, есть ли оно в словаре. От полученного на вход слова вычисляем несколько разных хэш-функций (дурной пример: пусть функция одна - остаток от деления на 256 суммы номеров букв слова). После этого имеет смысл распаковывать только ту часть словаря, для которой этот остаток такой же, причём длина слова тоже должна быть такой же.

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

Короче, мысль в том, что задача решаемая, но чтобы её ъорошо решить надо приложить много усилий.

Я в своё время писал поиск по сайту, используя самописную "добывалку" корней слов где-то строк на 30. Работала вполне хорошо. Иногда приходилось просматривать первую тысячу популярных запросов к машине, чтобы внести новые исключения в алгоритм. Это я к тому, что можно и что-то корявое, но сносно работающее сделать на 30 строках. А уж в 300 Кб можно и получше что-то было сделать. Тем более, у них команда не самоучек, и не из одного человека.

Это было практически без задержек для пользователя

даже на ЕС-1841 с тактовой частотой 4.5 MHz а насколько

быстро получится на современных гигагерцах с Pentium

распараллеливанием при компиляции оптимизирующим

компилятором надо пробовать, ...

Разворачивать словарь можно по разному, ...

Как я уже писал один пользователь на одной машине, ...

Похоже что Вы не очень внимательны, ...

Размер словаря в студию!!! Потому как задача размещения словаря в памяти в сжатом виде в некотором роде эквивалентна задачи сжатия вообщеи. Итого если достаточно "разнородные" текстовые данные, которые в несжатом виде занимают три Мб сжимаются до 0.3 Мб, то это больше на похоже на прорыв в области сжатия данных, чем в области морфологического разбора. А потом если размер словаря хотя бы сравним с испелловским, тогда было бы интересно узнать алгоритм.

-есть вероятность, что это не про все слова, а только про самые употребительные.