Алгоритм перевода существительных в им падеж, ед число
До чего я сам додумался:
Нужно хранить словарь существительных и соответствующие окончания для всех склонений. Но не уверен, что это лучшее решение.
Возникает 2 проблемы:
1) что делать с существительными, которые меняют корень при склонении (заяц- заЙца)
2) как учитывать суффиксы?
Если есть относительно простые решения этих проблем, то буду рад выслушать возможные алгоритмы их решения. Но, в крайнем случае, думаю, можно будет списать их на допущения.
Заранее благодарен.
http://xpoint.ru/know-how/VebAlgoritmyi/RabotaSTekstami/RabotaSRusskoyMorfologieyPriPomoschiSlovaryaIspell?3
(там же можно взять и словарь).
Если можно обойтись простеньким алгоритмом, способным работать и без словаря, то Вам подойдет алгоритм Snowball, описанный здесь:
http://snowball.tartarus.org/algorithms/russian/stemmer.html.
Учитывая, что эта задача для первого курса, предлагаю самый простой способ. Надо хранить не окончания, а слова целиком. У каждого существительного имеется не более 12 вариантов его употребления (6 падежей, единств. и множ. число). Следовательно, для хранения этих вариантов можно использовать массив из 12 строк. Например, для слова "заяц" этот массив будет выглядеть так: {"заяц", "зайца", "зайцу", "зайца", "зайцем", "зайце", "зайцы", "зайцев", "зайцам", "зайцев", "зайцами", "зайцах"}. Бывают слова, у которых, к примеру, отсутствует форма единственного числа - для них соответствующие элементы массива будут пустыми.
Для хранения всего множества слов можно использовать двумерный массив words[n][12], где n - количество слов.
2) как учитывать суффиксы?
А зачем? Тебе же надо только перевести слово в им.падеж, ед.число. Причем тут суффиксы?
Критерии производительности бывают разные. В одних случаях важны одни критерии, в других - другие. Для данной задачи можно выделить три критерия:
1. Надежность (отсутствие ошибок)
2. Объем памяти, используемый для хранения слов
3. Скорость работы программы
Теперь по порядку:
1. Очевидно, с точки зрения надежности предложенный мной способ является оптимальным, т.к. ошибок тут в принципе быть не может (если, конечно, словарь составлен грамотным человеком :) ).
2. Объем памяти можно оценить так: словарный запас обычного человека составляет около 10000 слов, каждое слово имеет 12 различных форм - всего получается около 120000 слов. Пусть, например, максимальная длина слова - 50 символов (на самом деле меньше, но для простоты пусть будет 50). Тогда весь словарь займет 10000*12*50 = 6000000 байт ~ 6Мб. Согласитесь, для современных компьютеров (с объемом оперативки 256 Мб и более) это не так уж много.
3. Что касается быстродействия, то здесь многое зависит от того, как автор реализует функцию поиска слова в массиве. Можно искать тупым перебором, можно бинарным поиском, а можно и хеш-функции использовать. Тут уж как автору будет угодно.
[QUOTE=Hrew]И потом, у Вас есть или Вы когда нибудь видели уже готовый словарь подобного рода? Или Вы предлагаете его вручную создавать?[/QUOTE]
Да, над словарем автору придется самому потрудиться. Впрочем, я не думаю, что это много времени займет. За год-полтора, наверное, успеет :)
я бы в этом направлении двигался http://algolist.manual.ru/misc/morfo.php
сдесь правда немного но я думаю если порыться в гугле то можно что-то найти
ps если уж состовлять словарь - то словарь исключений
кстати - автору топика эта проблема возникла не просто так а в рамках какого-то курса
так что лучше обратиться к материалам по курсу или другим "бумажным носителям"
ээ нет - это все не внушет энтузиазма
я бы в этом направлении двигался http://algolist.manual.ru/misc/morfo.php
Не вижу значительной разницы между смыслом приведенных по этому адресу алгоритмами и алгоритма Snowball - так или иначе все они занимаются отделением от основной части слова суффиксов и окончаний. Да, указанный мною алгорит стемминга не позволяет учитывать исключения, но и реализовывать словарь исключений - это утопия, по крайней мере если Вы не собираетесь писать что-нибудь серьезное.
Вообще многое зависит от того, на чем автор собирается алгоритм реализовывать. Например, для Perl есть уже готовый модуль:
http://search.cpan.org/~algdr/Lingua-Stem-Ru-0.01/Ru.pm#___top
А вот в этом архиве есть даже исходники на Си. Остается только разобраться с тем, что там написано и перевести на нужный язык.
http://linguist.nm.ru/stemka/stemka.tar.gz
P.S. Vitalii, а Вы вообще с нами или нет?
Решил использовать ispell. Оставлю правила перевода только для существительных и буду сверять переведенное в нормальную форму по этим правилам слово с содержанием словаря слов. Думаю этого будет достаточно.
Еще раз всем спасибо.