ооооо, ну если только закодировать командный и матерный :-) тогда вообще никакого дерева не нужно, можно обойтись номерами и уложиться в один байт со служебной информацией.
как там на слово может уходить куда меньше 16 бит, когда 10-16 бит - это только ОДИН указатель в дереве. И еще несколько бит всяка служебная информация :-)
так речь же шла о том, как уместить все это хозяйство в 300 к :-) так вот мое мнение, что без хирургического вмешательства не обойтись.
У Вас есть уверенность, что словарь ВСЕХ псевдооснов Зализняка? У меня есть уверенность, что основ там как-то мало. Возьмем например слово чаинка. В этом файлике нет слов, начинающихся на ч или ча.
Ну и потом, смотрите, в распакованном виде эти словари занимают несколько мегабайт. Если бы их можно было запихнуть в 300кб, это бы означала, что изобретен какой-то супер-пупер алгоритм сжатия, дающий нереально большой коэффициент сжатия.
По поводу дерева букв (trie-дерево). Там в каждую точку ветвления нужно пихать пойнтеры размером 10-16 бит (по одному пойнтеру на каждое поддерево). То есть, скажем, вместо хранения префикса длиной 6-8 символов (30-40 бит) мы храним 10-16 бит (пойнтер). Итого экономия в три раза в самом лучшем случае.
Немного почесав то, что любим чесать, приходим к выводу, что 300 кб - это реально, но только для небольшого словаря, скажем, где тысяч 10 "словооснов" (вместо зализняковских 100-150 тысяч). Фишка в том, что для многих приложений и этого вполне достаточно.
пришлите если не сложно ссылочку. хотелось бы понять, как три тысячи основ формируют порядка 80-100 тысяч русских слов, среди которых куча слов треть-четверть минимум не пересекается по основам. я думаю, что это либо то, что я вам ответели в привате, либо словарь был очень покоцанный. ну скорее всего истина где-то посредине: немножечко и то и другого.
Я, вообще-то собираюсь в ближайшее время (4-5 месяцев) сделать ispell-based библиотеку и выложить ее в свободный доступ. Значит, теперь подробнее, что я имел в виду. Пусть есть какое-то слово .
1) это слово словарное
2) это слово несловарное
Словарный случай решается с помощью генерации (скажем на момент сборки библиотеки всех словоформ) Для испелла это примерно миллион записей - сущие пустяки, можно и нужно грузить в память. В процессе генерации мы считаем статистику изменения окончаний при преобразования исходной формы в разные падежные ("спрягательные") формы. Для длинных слов берем статистику по последним пяти буквам, для слов покороче по трем или четырем. Что считать коротким, длинным и очень длинным слово нужно определять эмпирически или экспериментально. Пусть у нас (хотя в жизни может быть немного по-другому) получилось, что для окончания рнета наиболее вероятная исходная форма получается заменой окончания на рнет.
Таким образом для несловарного слова ИНТЕРНЕТА мы получаем, что наиболее вероятная исходная форма ИНТЕРНЕТ. Для больше достоверности можно брать две наиболее вероятные исходные формы.
Теперь важный момент: наряду со статистикой преобразования от конечной формы к исходной мы считаем и статистику правил генерации конечных форм из исходных. Таким образом, в приведенном выше примере для несловарного слова ИНТЕРНЕТА мы сможет не только выбрать базовую форму, но и сгенерировать другие формы, как то ИНТЕРНЕТУ, ИНТЕРНЕТОМ, и т.д и т.п.
Конечно, данный алгоритм будет делать иногда ошибки. У какого-то монстра, вроде даже у Яндекса, одно время английское слово dos считается производной формой от глагола do :-)
Таки надо ИМХО при такой реализации держать весь словарь в памяти (ну или все слова с частотой появления > 0.0...). Хотя, с другой стороны, сейчас это абсолютно не проблема.
Единственное, что я не понял, как наличие прямого индекса может сократить размер обратного индекса и как на это влияет размер базы?
Поддерживаю,
1) генерите испеллом словоформы
2) по сгенерированным и исходынм словоформам строите автоматический вероятностый анализатор, который, скажем по последним 3-5 буквам определяет наиболее вероятную исходную форму слова.
На эту тему, есть статья "Execution Performance Issues in Full-Text Information Retrieval, Eric. W Brown." Так вот, согласно моему опыту реализации этой идеи, не слишком это здорово. Потому что, например, при конъюнктивных запросах из 2 и более слов первые позиции занимают отнюдь не те страницы, в которых, часто встречаются первое и второе слово запроса, а там, где эти слова располагаются близко.
Если машина однопроцессорная, то это самый быстрый вариант, если есть более одного проца и хочется их все загрузить, то придется делить пул урлов и форкаться.
По поводу хитрых тредовых алгоритмов разделения пула. Я относительно недавно решал похожую задачу выдергивания данных по сети. Правда не страницы, а бинарные объекты из объекто-хранилища. Но специфика распределения длин примерно та же.
Реализовал простейший алгоритм, когда объекты между потоками выбираются случайно. На размахивания руками, что это мол некошерно, привел простое объяснение.
Заключается оно в следующем: Есть, скажем, N объектов и T среднее время скачивания объекта, а D дисперсия. Если мы скачиваем N объектов последовательно, то среднее время скачивания TN, а дисперсия D sqrt N (при достаточно реалистичном предположении о независимости времен скачивания). Итого: чем больше мы скачиваем объектов, тем меньше в процентном отношении время скачивания отличается от среднего!!! спрашивается, ради чего ломать копья, ради двухпроцентного выигрыша во времени? раскидайте N объектов на K очередей случайным образом.
Да и еще важное добавление: в целях не укладывания отдельных сайтов следуюет отслеживать время последнего обращения к сайту, и если, скажем, последний раз страница с сайта выбиралась менее 2-3 секунд назад, то лучше выбрать другую страницу из пула.
немножечко не так, в среднем веб-документе немножечко побольше чистого текста: так где-то около 3-4 килобайт.
