ой, откуда-то появились номера слов, я что-то пропустил. нет, лично я имел в виду следующее. анализатор слов а-ля программка Кевы на linguist.nm.ru. то есть если есть набор словооснов, то нужно его так компактно представить в памяти, чтобы по этому компактному представлению и произвольному входному слову определять может ли это слово быть сгенерировано на основе данных словооснов. как правило приятным побочным эффектом такой проверки может (хотя это не обязательно) могут являться грамматические харак-ки слова: часть речи, род, падеж число, итд.... Но в базовом варианте меня устроит и спеллчекер с компактным представлением словаря. Вот, надеюсь, что понятно изложил свои мысли!
!Иван FXS: - если у нас есть список словоформ - где угодно: хоть в голове, хоть на бумаге, хоть в файле - и мы говорим, что "а" имеет номер 1, то ... вот они, собственно, уже и закодированы все ... однозначно.
Задача, наверное, состоит в том, чтобы написать компактный АЛГОРИТМ, который бы производил ПРЕОБРАЗОВАНИЕ одного в другое ... Чего, кстати, одного - во что другое: слова - в его номер, или номера - в его слово?
Зодчий, но как можно разместить больше даннных в ОЗУ без сжатия? ОЗУ же оно же не резиновое. Процесс "умещения" большего количества данных в ОЗУ и называется сжатием.
Уважаемый Зодчий! Вы очень невнимательно читаете. Изначально был вопрос такой: какой смысл сжимать данные, если и так все хорошо. Я на него ответил, чтобы больше индекса влезало в кеш. При этом если в кеш влезает в три раза больше индекса, то и поисковых машин нужно натурально в три раза меньше. Надеюсь, что я ответил на первый вопрос.
Теперь вопрос следующий: зачем при гиге обрабатываемых данных ставить несколько машин. Отвечаю, потому что если не паковать индекс, то он не влезет в память машины, где оперативной памяти мало. А если индекс не влезет на одну машину, то прощай производительность в несколько запросов в секунду. Ну а вот на вопрос зачем производительность в несколько запросов в секунду я отвечать не буду. Предупреждаю заранее :-)
ЗодчийТеней: а какой смысл при гиге обробатыаемых данных ставит несколько машин? это уже не рентабельно
насчет 40% процентов индекса от общего объема вполне согласен, но я только лиш учусь и тестирую знания полученные в этой области, оптимизацию данных на пзу я пока не ставил как задачу, нет проблем с местом под данные, при доступном объеме в 200Гб и имеющихся 1Гб согласитесь это не проблема, хотя реальный размер текстовых данных всеголиш 42 Мб, сжатие на пзу я всеже использую;-)
Я кажется понимаю о чем идет речь, но название точное забыл, кажется это что-то вроде ppc и связано с цепями Маркова. Помню, что алгоритм очень эффективный, а вот насколько быстро потом можно искать не знаю.
Задача стоит хотя бы просто этот весь массив словоформ закодировать. Ну и естественно иметь возможность чекать если словоформа в словаре.
!Иван FXS: - нечто а-ля Хаффман ... с деталями, зависящими от требуемого ФУНКЦИОНАЛА словаря.
Какой, кстати, функционал-то обсуждаем? Спеллчекинг, например, или пораждение неупоряченного полного массива словоформ, или вычисление уникального порядкового номера (кода, идента) слова в упорядоченном (по алфавиту) полном списке - то ли слов, то ли словоформ?
Это же все разные задачи! И под каждую - оптимален свой метод хранения "словаря".
К вопросу о "целесообразности паковки": хранение словаря в виде список основ + правила пораждения словоформ - это есть, несомненно, паковка словаря (словоформ).
ну почему же загнул. во-первых, размер инвертированного (обратного индекса легко сделать в 40 процентов) во-вторых там не нужно кешировать все достаточно кешировать процентов 60-80. Ну и давайте посчитаем:
350 тыс страниц, каждая в среднем 4 кб чистого текста. Итого гиг с чем-то данных текстовых. 40 процентов - 400 мегабайт ОЗУ. А теперь представьте себе, что вы делаете обратный индекс несжатым получаете его размер в 100-200% размера текста и в гиг оперативки уже не влазите. То есть вместо одной машины придется поставить 3 или 4, чтобы искалось быстро.
Зодчий, ну какая-то безыдейная тема получилась. Понятно, что словарь сейчас паковать смысла нет, а вот, например, инвертированный индекс и, вообще, данные, не влезающие в память, есть. Посмотрите ссылочки на страничке
ЗодчийТеней: но речь то идет именно о сейчас, не о вчера и не о завтра, к тому же вчера считался каждый байт ОЗУ и грузит туда лишние данные было просто глупостью, поэтому даже с оглядкой на вчера я остаюсь при своем мнение, запакованным данным нечего делать в ОЗУ, загрузив туда запакованные данные вам также надо будет загрузить и алгоритм компресии/декомпресии или юзать его с жесткого диска, ваш выигрыш в производительности и в том и в ином случае стремится к нулю
еще раз повторюсь, ПОЖАЛУЙСТА, не можете обосновать свои слова, не бросайтесь ими
Artisan: Почему как ни странно? Если количество информации
одинаковое то и сжимать можно до одинакового размера
с поправкой на особенности алгоритмов, ...
Ну, в общем-то, неважно цифра, как ни странно, получается похожая. Думаю, что с учетом того насколько это было давно точных цифры уже никто не помнит, поэтому +-30-40 процентов вполне допустимые отклонения.
Сейчас смысла в этом нет, а раньше, когда было 640 кб озу был/
ЗодчийТеней: ребята, давайте жить дружно, еще раз повторюсь, в первоначальной постановке вопроса речь шла о загрузке словаря в ОЗУ, я со совей колокольни, не вижу смысла загружать в ОЗУ запакованные данные, и по прежнему думаю что все упирается в алгоритм формирования слов из некоего абстрактного списка основ, то что я вижу на данный момент лишь подтверждает мою уверенность в том что эти данные можно втиснуть в пресловутые 300Кб
да я был немножечко неточен: распакованный вид это все словоформы в однобайтовой кодировке. вот сейчас посмотрел 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 тысяч словоформ.
А что Вы понимаете под н-граммным кодированием?
!Иван FXS: - извините, а что такое "распакованный вид"? Это когда каждый символ занимает 8 бит? Или - как в Юникоде - 16 бит?
А букв в русском алфавите 33, то есть кодируются они 5 (с небольшим хвостиком) битами ...
На самом деле, я думаю, что Artisan так много туману напускает - по поводу кодирования n-грамами (буквеными).
Кстати, еще раз повторюсь буквы в русском языке кодируются где-то четырьмя битами в среднем, если использовать Хаффмана.
Если вы уложили в 300кб набор слов, которые в распакованном виде занимают 4-8 Мб, то вы решили задачу более чем десятикратного сжатия. Вы согласны с этим утвеждением?
И все-таки, не сочтите за настойчивость нельзя ли огласить размер словаря по числу исходных форм.
Artisan: Это совсем разные задачи, ...
Размер сравним, алгоритм бесплатно не раздается, ...
300kb вполне достаточно, ...
ЗодчийТеней: опятьже лиш слова
предлагаю в дальнейшем, в данном топике, не обращать внимания на высказывания пользователя с никнеймом Artisan в связи с его неспособностью обосновать свои ответы
Я бы Вас тоже попросил не хамить Артизану. Все-таки у нас тут научная дискуссия, а не спарринг :)
Размер словаря в студию!!! Потому как задача размещения словаря в памяти в сжатом виде в некотором роде эквивалентна задачи сжатия вообщеи. Итого если достаточно "разнородные" текстовые данные, которые в несжатом виде занимают три Мб сжимаются до 0.3 Мб, то это больше на похоже на прорыв в области сжатия данных, чем в области морфологического разбора. А потом если размер словаря хотя бы сравним с испелловским, тогда было бы интересно узнать алгоритм.
Artisan: При чем здесь микропроцессорная техника?
Задача умять словарь в 300kb оперативной памяти,
причем насколько я помню что написано у Yandex это
для одного пользователя на локальной машине.
Такую задачу я решил и могу объяснить как.
Чем больше будет с Вашей стороны тем
лучше будет с моей, предлагайте в приват, ...
ой, откуда-то появились номера слов, я что-то пропустил. нет, лично я имел в виду следующее. анализатор слов а-ля программка Кевы на linguist.nm.ru. то есть если есть набор словооснов, то нужно его так компактно представить в памяти, чтобы по этому компактному представлению и произвольному входному слову определять может ли это слово быть сгенерировано на основе данных словооснов. как правило приятным побочным эффектом такой проверки может (хотя это не обязательно) могут являться грамматические харак-ки слова: часть речи, род, падеж число, итд.... Но в базовом варианте меня устроит и спеллчекер с компактным представлением словаря. Вот, надеюсь, что понятно изложил свои мысли!
- если у нас есть список словоформ - где угодно: хоть в голове, хоть на бумаге, хоть в файле - и мы говорим, что "а" имеет номер 1, то ... вот они, собственно, уже и закодированы все ... однозначно.
Задача, наверное, состоит в том, чтобы написать компактный АЛГОРИТМ, который бы производил ПРЕОБРАЗОВАНИЕ одного в другое ... Чего, кстати, одного - во что другое: слова - в его номер, или номера - в его слово?
Зодчий, но как можно разместить больше даннных в ОЗУ без сжатия? ОЗУ же оно же не резиновое. Процесс "умещения" большего количества данных в ОЗУ и называется сжатием.
Уважаемый Зодчий! Вы очень невнимательно читаете. Изначально был вопрос такой: какой смысл сжимать данные, если и так все хорошо. Я на него ответил, чтобы больше индекса влезало в кеш. При этом если в кеш влезает в три раза больше индекса, то и поисковых машин нужно натурально в три раза меньше. Надеюсь, что я ответил на первый вопрос.
Теперь вопрос следующий: зачем при гиге обрабатываемых данных ставить несколько машин. Отвечаю, потому что если не паковать индекс, то он не влезет в память машины, где оперативной памяти мало. А если индекс не влезет на одну машину, то прощай производительность в несколько запросов в секунду. Ну а вот на вопрос зачем производительность в несколько запросов в секунду я отвечать не буду. Предупреждаю заранее :-)
а какой смысл при гиге обробатыаемых данных ставит несколько машин? это уже не рентабельно
насчет 40% процентов индекса от общего объема вполне согласен, но я только лиш учусь и тестирую знания полученные в этой области, оптимизацию данных на пзу я пока не ставил как задачу, нет проблем с местом под данные, при доступном объеме в 200Гб и имеющихся 1Гб согласитесь это не проблема, хотя реальный размер текстовых данных всеголиш 42 Мб, сжатие на пзу я всеже использую;-)
Я кажется понимаю о чем идет речь, но название точное забыл, кажется это что-то вроде ppc и связано с цепями Маркова. Помню, что алгоритм очень эффективный, а вот насколько быстро потом можно искать не знаю.
Задача стоит хотя бы просто этот весь массив словоформ закодировать. Ну и естественно иметь возможность чекать если словоформа в словаре.
- нечто а-ля Хаффман ... с деталями, зависящими от требуемого ФУНКЦИОНАЛА словаря.
Какой, кстати, функционал-то обсуждаем? Спеллчекинг, например, или пораждение неупоряченного полного массива словоформ, или вычисление уникального порядкового номера (кода, идента) слова в упорядоченном (по алфавиту) полном списке - то ли слов, то ли словоформ?
Это же все разные задачи! И под каждую - оптимален свой метод хранения "словаря".
К вопросу о "целесообразности паковки": хранение словаря в виде список основ + правила пораждения словоформ - это есть, несомненно, паковка словаря (словоформ).
ну почему же загнул. во-первых, размер инвертированного (обратного индекса легко сделать в 40 процентов) во-вторых там не нужно кешировать все достаточно кешировать процентов 60-80. Ну и давайте посчитаем:
350 тыс страниц, каждая в среднем 4 кб чистого текста. Итого гиг с чем-то данных текстовых. 40 процентов - 400 мегабайт ОЗУ. А теперь представьте себе, что вы делаете обратный индекс несжатым получаете его размер в 100-200% размера текста и в гиг оперативки уже не влазите. То есть вместо одной машины придется поставить 3 или 4, чтобы искалось быстро.
Зодчий, ну какая-то безыдейная тема получилась. Понятно, что словарь сейчас паковать смысла нет, а вот, например, инвертированный индекс и, вообще, данные, не влезающие в память, есть. Посмотрите ссылочки на страничке
http://itman.narod.ru/articles/articles_ir.html#p5
но речь то идет именно о сейчас, не о вчера и не о завтра, к тому же вчера считался каждый байт ОЗУ и грузит туда лишние данные было просто глупостью, поэтому даже с оглядкой на вчера я остаюсь при своем мнение, запакованным данным нечего делать в ОЗУ, загрузив туда запакованные данные вам также надо будет загрузить и алгоритм компресии/декомпресии или юзать его с жесткого диска, ваш выигрыш в производительности и в том и в ином случае стремится к нулю
еще раз повторюсь, ПОЖАЛУЙСТА, не можете обосновать свои слова, не бросайтесь ими
Почему как ни странно? Если количество информации
одинаковое то и сжимать можно до одинакового размера
с поправкой на особенности алгоритмов, ...
Неожиданно большой коэффициент сжатия получается.
Ну, в общем-то, неважно цифра, как ни странно, получается похожая. Думаю, что с учетом того насколько это было давно точных цифры уже никто не помнит, поэтому +-30-40 процентов вполне допустимые отклонения.
Сейчас смысла в этом нет, а раньше, когда было 640 кб озу был/
ребята, давайте жить дружно, еще раз повторюсь, в первоначальной постановке вопроса речь шла о загрузке словаря в ОЗУ, я со совей колокольни, не вижу смысла загружать в ОЗУ запакованные данные, и по прежнему думаю что все упирается в алгоритм формирования слов из некоего абстрактного списка основ, то что я вижу на данный момент лишь подтверждает мою уверенность в том что эти данные можно втиснуть в пресловутые 300Кб
да я был немножечко неточен: распакованный вид это все словоформы в однобайтовой кодировке. вот сейчас посмотрел 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 тысяч словоформ.
А что Вы понимаете под н-граммным кодированием?
- извините, а что такое "распакованный вид"? Это когда каждый символ занимает 8 бит? Или - как в Юникоде - 16 бит?
А букв в русском алфавите 33, то есть кодируются они 5 (с небольшим хвостиком) битами ...
На самом деле, я думаю, что Artisan так много туману напускает - по поводу кодирования n-грамами (буквеными).
Кстати, еще раз повторюсь буквы в русском языке кодируются где-то четырьмя битами в среднем, если использовать Хаффмана.
Если вы уложили в 300кб набор слов, которые в распакованном виде занимают 4-8 Мб, то вы решили задачу более чем десятикратного сжатия. Вы согласны с этим утвеждением?
И все-таки, не сочтите за настойчивость нельзя ли огласить размер словаря по числу исходных форм.
Это совсем разные задачи, ...
Размер сравним, алгоритм бесплатно не раздается, ...
300kb вполне достаточно, ...
опятьже лиш слова
предлагаю в дальнейшем, в данном топике, не обращать внимания на высказывания пользователя с никнеймом Artisan в связи с его неспособностью обосновать свои ответы
Я бы Вас тоже попросил не хамить Артизану. Все-таки у нас тут научная дискуссия, а не спарринг :)
Размер словаря в студию!!! Потому как задача размещения словаря в памяти в сжатом виде в некотором роде эквивалентна задачи сжатия вообщеи. Итого если достаточно "разнородные" текстовые данные, которые в несжатом виде занимают три Мб сжимаются до 0.3 Мб, то это больше на похоже на прорыв в области сжатия данных, чем в области морфологического разбора. А потом если размер словаря хотя бы сравним с испелловским, тогда было бы интересно узнать алгоритм.
При чем здесь микропроцессорная техника?
Задача умять словарь в 300kb оперативной памяти,
причем насколько я помню что написано у Yandex это
для одного пользователя на локальной машине.
Такую задачу я решил и могу объяснить как.
Чем больше будет с Вашей стороны тем
лучше будет с моей, предлагайте в приват, ...