ой, откуда-то появились номера слов, я что-то пропустил. нет, лично я имел в виду следующее. анализатор слов а-ля программка Кевы на linguist.nm.ru. то есть если есть набор словооснов, то нужно его так компактно представить в памяти, чтобы по этому компактному представлению и произвольному входному слову определять может ли это слово быть сгенерировано на основе данных словооснов. как правило приятным побочным эффектом такой проверки может (хотя это не обязательно) могут являться грамматические харак-ки слова: часть речи, род, падеж число, итд.... Но в базовом варианте меня устроит и спеллчекер с компактным представлением словаря. Вот, надеюсь, что понятно изложил свои мысли!
Зодчий, но как можно разместить больше даннных в ОЗУ без сжатия? ОЗУ же оно же не резиновое. Процесс "умещения" большего количества данных в ОЗУ и называется сжатием.
Уважаемый Зодчий! Вы очень невнимательно читаете. Изначально был вопрос такой: какой смысл сжимать данные, если и так все хорошо. Я на него ответил, чтобы больше индекса влезало в кеш. При этом если в кеш влезает в три раза больше индекса, то и поисковых машин нужно натурально в три раза меньше. Надеюсь, что я ответил на первый вопрос.
Теперь вопрос следующий: зачем при гиге обрабатываемых данных ставить несколько машин. Отвечаю, потому что если не паковать индекс, то он не влезет в память машины, где оперативной памяти мало. А если индекс не влезет на одну машину, то прощай производительность в несколько запросов в секунду. Ну а вот на вопрос зачем производительность в несколько запросов в секунду я отвечать не буду. Предупреждаю заранее :-)
Я кажется понимаю о чем идет речь, но название точное забыл, кажется это что-то вроде ppc и связано с цепями Маркова. Помню, что алгоритм очень эффективный, а вот насколько быстро потом можно искать не знаю.
Задача стоит хотя бы просто этот весь массив словоформ закодировать. Ну и естественно иметь возможность чекать если словоформа в словаре.
ну почему же загнул. во-первых, размер инвертированного (обратного индекса легко сделать в 40 процентов) во-вторых там не нужно кешировать все достаточно кешировать процентов 60-80. Ну и давайте посчитаем:
350 тыс страниц, каждая в среднем 4 кб чистого текста. Итого гиг с чем-то данных текстовых. 40 процентов - 400 мегабайт ОЗУ. А теперь представьте себе, что вы делаете обратный индекс несжатым получаете его размер в 100-200% размера текста и в гиг оперативки уже не влазите. То есть вместо одной машины придется поставить 3 или 4, чтобы искалось быстро.
Зодчий, ну какая-то безыдейная тема получилась. Понятно, что словарь сейчас паковать смысла нет, а вот, например, инвертированный индекс и, вообще, данные, не влезающие в память, есть. Посмотрите ссылочки на страничке
http://itman.narod.ru/articles/articles_ir.html#p5
Неожиданно большой коэффициент сжатия получается.
Ну, в общем-то, неважно цифра, как ни странно, получается похожая. Думаю, что с учетом того насколько это было давно точных цифры уже никто не помнит, поэтому +-30-40 процентов вполне допустимые отклонения.
Сейчас смысла в этом нет, а раньше, когда было 640 кб озу был/
да я был немножечко неточен: распакованный вид это все словоформы в однобайтовой кодировке. вот сейчас посмотрел 8.8 мегабайт. еще раз посчитал количество способов генерации словоформ в russian.aff (для испелл) 26 штук.
Если есть 100 тысяч слов-основ или их аналогов, то в среднем по словам Артизана, приходится 3 байта = 24 бит на одну словооснову вместе со способом генерации конечных словофрм. Последнее сожрет 4-5 бит. Итого на кодирование одной слово-основы можно потратить 21 бит. Словооснова в словаре имеет среднюю длину 8 байт. Если каким-нибудь хаффманом закодировать буквы, то в среднем на букву можно затратить бита 4. При этим если сгруппировать слова по первым 3-4 буквам, на каждое слово мы потратим в среднем 4 x 4 бита на кодирование окончания и еще нужно бит 8 - десять на кодирование смещения (если структура дерево). Итого в 21 бит мы никак не укладываемся, хотя получается что-то близкое к 300 килобайтам. Ну может не 300, но 400-500 возможно. Без экспериментов точно не скажешь. Тем не менее, я думаю, что Яндекса алгоритмы попроще были, но и размер словаря был поменьше 30-50 тысяч словоформ.
А что Вы понимаете под н-граммным кодированием?
Кстати, еще раз повторюсь буквы в русском языке кодируются где-то четырьмя битами в среднем, если использовать Хаффмана.
Если вы уложили в 300кб набор слов, которые в распакованном виде занимают 4-8 Мб, то вы решили задачу более чем десятикратного сжатия. Вы согласны с этим утвеждением?
И все-таки, не сочтите за настойчивость нельзя ли огласить размер словаря по числу исходных форм.
Я бы Вас тоже попросил не хамить Артизану. Все-таки у нас тут научная дискуссия, а не спарринг :)
Размер словаря в студию!!! Потому как задача размещения словаря в памяти в сжатом виде в некотором роде эквивалентна задачи сжатия вообщеи. Итого если достаточно "разнородные" текстовые данные, которые в несжатом виде занимают три Мб сжимаются до 0.3 Мб, то это больше на похоже на прорыв в области сжатия данных, чем в области морфологического разбора. А потом если размер словаря хотя бы сравним с испелловским, тогда было бы интересно узнать алгоритм.
