Index of /RWWW

 Name                    Last modified       Size  Description

 Parent Directory        11-Jun-2007 04:16      -  
 bldidx.rwww             26-Jan-2005 22:20     2k  
 fwais.tgz               26-Jan-2005 22:20   744k  
 indexsite.sh            26-Jan-2005 22:20     1k  
 libwww.tgz              26-Jan-2005 22:20    90k  
 rustem.html             19-Feb-2008 02:11    23k  
 rwais.tgz               26-Jan-2005 22:20   209k  
 steal.tgz               26-Jan-2005 22:20     5k  
 var-wais.tar.gz         26-Jan-2005 22:20     6k  
 wais-www-cfg.tgz        26-Jan-2005 22:20     9k  
 wais-www.tgz            26-Jan-2005 22:20    18k  
 ww-retrieve             26-Jan-2005 22:20     1k  
 ww-retrieve-h           26-Jan-2005 22:20     1k  
 ww-search               26-Jan-2005 22:20     1k  

Рустем - программа для выделения неизменяемой части из слова.

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

Не будучи при этом ни в самой малой мере специалистом в лингвистике, я нуждался в серьезной помощи со стороны людей, профессионально занимающихся этой и смежными проблемами. К сожалению, большая часть бесед с лингвистами, которых я смог найти, была не слишком продуктивной, однако помощь Г.С.Цейтина и В.М.Андрющенко была существенной, и их консультации позволили мне найти отправную точку моей работы и сделать первые шаги; по предложению Андрющенко я обратился к сотруднице Машинного Фонда Русского Языка Жанне Григорьевне Аношкиной, разработки которой стали основой для алгоритмов, использованных в моей программе. (Любопытной и поучительной подробностью моих исканий явилось то, что дважды в их ходе мне предлагали отыскать некую Машкович из МФРЯ, у которой "лет шесть назад" были статьи по интересующей меня теме, да я все никак не мог собраться навести справки - так вот, Жанна Григорьевна Аношкина это та Машкович и есть).
То, о чем мне рассказывала Аношкина, представляло собой программу лемматизации и морфологического анализа слов русского языка, среди прочих слов способную обрабатывать незнакомые ей (то есть отсутствующие в словаре) слова. Ключевой (по крайней мере, для меня) чертой программы было наличие в ней двух одинаково устроенных словарей - отсортированных словарей условных окончаний и условных основ (условных потому, что часть основы, изменяющаяся от формы к форме, была перенесена в окончание), записанных справа налево. Сначала по словарю окончаний отыскивались все отделяемые от слова части, потом для каждой из оставшихся после отделения частей в словаре основ отыскивались полные совпадения. Для полных совпадений проверялись на пересечения множества парадигм, прицепленные к условному окончанию и к условной основе (был также перенумерованный словарь парадигм со ссылками на него из двух первых словарей по номеру), и кандидаты с пересекающимися множествами считались правильными ответами.
В случае же, если полного совпадения основы найдено не было, поиск повторялся уже с учетом частичных совпадений и с выбором в качестве лучшего варианта с наибольшей суммарной длиной окончания и совпавшей части основы; при этом морфологический анализ производился так же, как для соответствующего слова из словаря. Такой подход давал вполне достоверные результаты и был положен, с рядом изменений, в основу моей программы.
Среди других особенностей программы Жанны Григорьевны, важных для меня, было наличие

• словаря имен, содержащего распространенные собственные имена,
• словаря служебных слов (союзов, предогов, междометий, числительных и вводных слов).

При том, что описанная программа уже очень близко подводила к решению стоящей передо мной задачи, использовать ее в неизмененном виде было невозможно или, по крайней мере, неразумно. Для такой точки зрения было неколько причин, среди которых основными были следующие:

• Программа была довольно медленной, а ее словарь - слишком большим. Проблема состояла не в ограничениях на оперативную или вторичную память, а в большом объеме избыточных для решения моей задачи данных, от которых предстояло избавиться.
• Доступ к словарям был организован так, что поиск полных совпадений был быстрым, а частичных - медленным. Кроме того, поиск окончаний был попросту неэффективным: словари хранились в виде индексно-последовательных файлов - структуры, далекой от оптимальной в такой задаче.
• Передо мной стояла задача не правильного морфологического анализа, а возможно более однообразного и последовательного сведения слов к условным основам, а значит, я мог вообще исключить словарь парадигм при работе программы и использовать его только при создании словаря.
• Словарь имен, использовавшийся в системе для анализа имен собственных, представлял собой нестойкие данные, нуждающиеся в пополнении. Я же принял решение создать систему, в пополнении не нуждающуюся.

По некотором размышлении я принял решение о ряде принципиальных изменений в алгоритмах. Во-первых, я отказался от поиска полностью совпадающей основы, оставив только поиск частичного совпадения, а вместе с ним и от хранения полного словаря - при создании словаря от основы остается не более заранее заданного числа букв, причем изменением этого числа стало возможно устанавливать соотношение между производительностью и качеством работы алгоритма.
Во-вторых, я несколько сузил число парадигм, воспользовавшись тем, что в моей задаче их единственная роль состоит в установлении связи между основами и окончаниями. Для этого я отсортировал флексии в парадигмах и убрал дубликаты, а для нумерования парадигм стал использовать хэш-таблицу. (В программе Аношкиной сравнивались только последовательные флексии).
В-третьих, при переборе разбиений я стал двигаться от максимального по длине окончания к минимальному, а не наоборот, что позволило мне прерывать поиск в случае, если найдено совпадение предельного числа букв основы.
В-четвертых, я убрал из словаря служебных слов числительные и вводные слова, а оставшуюся часть словаря стал использовать как фильтр в том смысле, что узнанные по этому словарю слова отбрасываются как несмысловые.
В-пятых, наконец, я отказался от использования словаря имен. Тот выигрыш, которые давали выделяемые из него правила, был довольно мал, а накладные расходы от его использования оказывались сравнительно велики.

Устройство программы.

• Переданное программе слово сверяется со словарем служебных слов, организованным как хэш-таблица. Если слово найдено в этом словаре ("фильтре"), то в качестве результата немедленно выдается пустая строка - служебные слова съедаются.
• Слова, успешно преодолевшие фильтр, подвергаются основной обработке. Сначала для слова по словарю условных окончаний составляется список отделяемых окончаний вместе со списками соответсвтующих им парадигм, упорядоченный по длине отделенной части в порядке убывания. Затем, для каждого элемента этого списка производится попытка выделить совпадающий хвост основы по словарю основ, при этом лучший случай определяется по максимуму суммарной длины окончания и совпавшей части основы. Легко видеть, что при таком выборе поиск может быть прекращен досрочно, если найдено сочетание, при котором совпало максимальное хранимое в словаре число букв основы.
  Единственная поправка, которую пришлось ввести, связана с тем, что в имевшемся у меня словаре были элементы, в которых все слово, кроме приставки "НЕ", были отнесено в окончание, поэтому если то, что остается после отделения окончания, оказывается этим сочетанием букв, то такой случай попросту выбрасывается из рассмотрения.
• Если длина кандидата меньше заранее заданного ограничения снизу, то выдается пустая строка, иначе к полученной условной основе применяются эвристики:
  1. выяснилось, что если основа оканчивается на одну из букв из набора "АЕИЙЮЯ", то почти всегда есть слово, в котором после отрезания окончания остается на одну (эту) букву меньше; поэтому, если позволяет ограничение на минимальную длину основы, эта буква удаляется;
  2. если, опять же, позволяют ограничения на минимальную длину, из основы удаляется начальное буквосочетание "НЕ".

Основные затраты процессорного времени и оперативной памяти приходятся на поиск в двух одинаково устроенных словарях - окончаний и основ, и от того, как они устроены, существенно зависит производительность программы и ее связь с размером словарей и плотностью входного потока. На настоящий момент, и, думаю, на довольно протяженное будущее, словари устроены следующим образом:

• Основной словарь, в котором содержатся "слова", длина которых не меньше двух букв, представляет собой массив с числом элементов, равным квадрату числа букв в алфавите. Каждый элемент массива представляет собой список фрагментов "слов" (окончаний или основ) словаря вместе со списком соответствующих парадигм и служебной информацией. Фрагмент представляет собой часть слова, которой оно отличается от предыдущего в списке, а служебная информация - это , собственно, длина совпадающей у этого и предыдущего слова части. Все слова, включаемые в список элемента массива, начинаются с букв, (б1,б2), таких, что б1*"длина алфавита"+б2 есть индекс элемента, а при вставке в список эти буквы из всех слов удаляются.
• Для слов длиной в одну букву, есть аналогично устроенный массив длиной, равной длине алфавита, а для пустых слов - одиночный список. Эти элементы имеют вырожденную структуру, но их специальная обработка не увеличит производительности, а единый подход делает алгоритмы более стройными.
• Оказалось выгодно вычленять список окончаний за одну операцию над словарем, начиная каждый раз поиск с места, следующего за достигнутым. Основы, при этом, ищутся по одной, так как, во-первых, каждый раз надо начинать с другого списка, во-вторых, очень выгодно прекращать поиск досрочно.

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

Впечатление от работы

В настоящее время программа написана на Схеме и откомпилирована транслятором Scheme->C, написанной Joel Bartlett, DEC WRL. Объем таблиц в оперативной памяти составляет 2 Mb, но при этом при необходимости съэкономить память тексты могут быть переписаны так, чтобы хватало 800 Kb оперативной памяти для оптимального словаря. При достаточной памяти на 486DX33 программа обрабатывает слова со скоростью около двухсот слов в секунду.
Оптимальным словарем, при этом, оказался такой, котрый создавался с сохранением 6 букв основы - при меньшем числе больший разброс возникает от преобладающего влияния ошибки приведения к основе, а при большем различаются те тонкости, которыми вполне допустимо пренебречь - при указанной величине же разброс минимальный, то есть из тестовой последовательности (все просклоненные слова из словаря Зализняка) получается список условных основ наименьшей длины. При этом при оставляемой длине слова от 9 и больше результаты практически перестают различаться.
После некоторых эскпериментов минимальная приемлемая длина основы положена равной 3.