автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Эффективно реализуемая на ЭВС модель морфологии флективного естественного языка

Министерство натки и технической политики Российской Федерации

Российская /<адения нале

Всероссийский институт научной и технической информации

РГБ ОД

На пра&ш рукописи

ге/ьбух Александр Феликсович

УДК [801. ТЗ:С81. 3] (043. 3)

ЭФФЕКТИВНО РЕАЛИЗУЕМАЯ НА ЭВМ МОДЕЛЬ МОРФОЛОГИИ ФЛЕКТИВНОГО ЕСТЕСТВЕННОГО ЯЗЫКА

Специальность 05. 13. 17 теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва 1991

Работа выполнена во Всероссийском институте научной технической информации.

Научный руководитель: доктор технических наук, профессор Большаков Игорь Алексеевич

Официальные оппоненты: доктор технических наук, профессор Белоногое Герольд Георгиевич, кандидат технических наук Терещенко Сергей Серее??чч

Ведудая организация: Российский Государственный Гуманитарный Университет.

. Защита состоится ¿& Ж. 1994 года в 10. часов на заседании Специализированного совета ДООЭ. 02.01 во Всероссийском институте научной и технической информации по адресу: 125219, Мэсква, ул. Усиевича, д. 20-а.

С диссертацией можно ознакомиться в библиотеке Всероссийского института научной и технической информации.

Автореферат разослан оЯ

1994 г.

Ученый секретарь Специализированного совета доктор технических наук

Ш'Грива Лидия Андреевна

ОЩ№ ХАРАКТЕРИСТИКА РА9ОТЫ

Актуальность проблемы морфологического анализа и синтеза словоформ определяется тем, что блок морфологического анализа является необходимой частью большинства раСоташда с естественноязыковыми текстами программ самого различного уровня и назначения; большинство факих систем нуждается также в блоке синтеза. Ввиду системного характера задачи и болыюгб объема обрабатываемой информации к морфологическому блоку предъявляются жесткие требования по эффективности и быстродействии.

Задача 8включается в том, чтобы разработать алгоритмы, методы и лингвистические модели, позволяющие автоматически осуществлять точный и полный морфологический анализ и синтез, а такле решать ряд смежных аадач, таких как нормализация слов, обучение пользователя грамматике, обнаружение и исправление грамматических ошибок и опечаток, интерпретация неправильных и незнакомых слов. К разрабатываемым алгоритмам предъявляется ряд более жестких, чем в известных алгоритмах, требований, в том числе - требование предельно высокой скорости работы и малого объема занимаемой оперативной памяти при работе на современных персональных ЭВМ, а также требование полного отделения программ от лингвистической информации в рамках модели, описывающей строение некоторого класса флективных языков.

Целью исследования в настоящей диссертации является разработка принципов, алгоритмов, программ и соответствующих лингвистических моделей, позволяющих создать эффективную по быстродействию и занимаемой оперативной памяти ЭВМ систему автоматического морфологического анализа, синтеза, нормализации слов, обнаружения и исправления ошибок, функционирующую на

современных персональных ЭШ и допускающую встраивание в интегрированные пакеты обработки текстовой информации.

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

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

Мэтоды исследования. Исследование проводилось путем изучения закономерностей морфологического строения флективных языков, в первую очередь - русского; разработки конкретных морфологических таблиц и словаря для русского языка; " изучения

методов представления словаря на устройстве дисковой памяти и алгоритмов доступа к нему; разработки алгоритмов морфологического анализа, синтеза, нормализации слов, обнаружения и исправления овмбок; практической реализации этих алгоритмов на ЭВМ; статистической обработки результатов экспериментов.

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

Основные научные результаты:

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

- Разработана структура словаря, позволяющая достичь предельного быстродействия алгоритма поиска основ слов в словаре, а та№» алгоритьи поиска в таком словаре и алгоритм ¿юрмарова-ния словаря нужной структуры.

- Разработаны и практически ревизованы на ЭГМ быстро-действуйте и экономичные по использованию оперативной нпуятк

алгоритмы морфологического анализа, синтеза, нормализации слов, обнаружения и исправления ошибок.

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

- При участии автора разработан и реализован на ЭВМ интерфейс стандартной библиотеки морфологических процедур.

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

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

Реализация результатов работы. На основании разработанных алгоритмов, программ, лингвистического обеспечения и словаря создана стандартная библиотека процедур морфологического анализа, синтеза, нормализации слов, обнаружения и исправления ошибок. Имеется опыт интеграции данной библиотеки в реализованную на персональной ЭВМ информационно-поисковую систему DS-SIMPLE, практически эксплуатируемую с 1992 года 'Получен также опыт реализации разработанного алгоритма исправления опечаток в системе грамматической проверки текста, основанной на иной морфологической модели.

Апробация работа Основные научные результаты работы представлялись на конкурс работ молодых ученых ВНТЩентра (1990; III место), докладывались автором на IV Всесоюзной школе-семинаре при Институте кибернетики АН УССР, конференции

"Программное обвопочопко новой информационной технологии", III

Мэждународной конференции "Программное обеспечение ЭВМ", 1-й Ежегодной Всесоюзной конференции SUUG, конференции "Испольэо-вание программных средств ГОВЫ для автоматизации учрежденческой деятельности", Кйвдународном форуме "Тех-Екс'ЭР - обмен технологиями" (Болгария), на научно-технических семинарах сектора ПО баз знаний отдела автоматизации информационных процессов ВНГИЦентра и отдела ОТОИ ВИНИТИ.

публикации. Ш теме диссертации опубликовано И работ -три статьи, тезисы докладов, технические отчета

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и десяти приложений.

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

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

Третья глава является центральной в работе. В ней излагается разработанная автором язьково-независимая в некотором классе естественных языков формальная лингвистическая модель морфологического строения естественного языка, а также структура разработанной автором морфологической системы, основанной на данной модели. Приводятся алгоритмы морфологического анали-

ва, синтеза, нормалиаации слов, обнаружения, объяснения и исправления ошибок. ,

В четвертой главе отдельно рассматривается разработанный автором алгоритм исправления опечаток, примененный, в частности, в описываемой морфологической системе. Показывается, что по эффективности данный алгоритм превосходит применяемые в настоящее время. Приводится несколько вариантов алгоритма.

Общий объем работы - 220 страниц, основной текст - 200 страниц. Список литературы включает 171 название. В работе имеется 1 таблица и 9 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В диссертации выбран следующий порядок изложения материала по главам.

Во введении обосновывается актуальность выбранной темы, определяете*! предмет, цель и методы исследования; раскрывается научная новизна и практическая значимость работы: формулируются основные научные результаты исследования; описывается структура диссертации и дается краткая характеристика ее основных разделов.

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

Морфологической подсистемой называется комплекс программных средств, осуществляющие морфологические операции над

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

Как в тексте, так и в информационных системах собственно слово, или лексема, и его морфологическая форма играют принципиально различную роль. Любые свойства понятия привязаны, как правило, к лексеме: так, с лексемой МОЛОТОК может быть связано свойство мужского рода, количество единиц на складе, цена, номера документов, содержащих определенную информацию, и т. д. С морфологической же формой, или набором грамматических характеристик, связана информация принципиально иного сорта: например, творительный падеж определяет роль непрямого дополнения в предложении. Поэтому при обработке текста принципиальное значение имеет задача разделения двух указанных сущностей и их раздельной обработки. Однако в языках флективного типа обе указанные сущности выражаются, как правило, одной буквенной цепочкой, называемой словоформой, ср.: молотком.

Морфологическим анализом называется сопоставление словоформе выражаемой ею лексемы, с одной стороны, и набора грамматических характеристик, с другой стороны. Например, молпткпм --> (1) ЮЛОТОК, (2) творительный падеж единственного числа. Нормализацией слова называется сопоставление словоформе номера

юкоомы, об арго для вое* словоформ данной лекоемы, либо стандартизированной словарной формы, например: молотком —> молоток, ножницами —> ножницы, рам — > рад.

Шрфологичеоким синтевом, называется обратное сопоставление, то есть нахождение словоформы по заданным лексеме и грамматическим характеристикам, например: ШЛОТОК, творительный падеж единственного числа --> тлотюм.

Грамматической проверкой называется установление наличия в языке данной словоформы, включая проверку возможности выбора дачных грамматических характеристик и правильности построения словоформы. Например, следующие словоформы ошибочны: *ножни-цзй, *хочут, *сдовво. Интерпретацией ошибочного слова называется решение задачи морфологического анализа даже для ошибочной словоформы: *ножяишй —> НОЖНИЦЫ, творительный падеж единственного числа. Объяснением ошибки называется установление природы ошибки или правила, запрещающего построение данной словоформы, например: "у лексемы НОЖНИЦЫ отсутствуют формы единственного числа". Исправлением ошибки называется установление правильного написания слова, например: *хочут --> хотят, *словво —> слово. Опечаткой называется грамматически немотивированная ошибка, например: +словво, ьпрогрмма.

Приближенным морфологическим анализом и синтезом называется решение соответствующих задач для словоформ, образованных от лексем, отсутствующих в словаре системы, например: диет-рибыегорат --> ДИСТРИБЬЮТОР (?), творительный падеж множественного числа, (?); вопросительный знак здесь обозначает предположительность результата . Данная задача решается путем решения задачи приближенного определения морфологических признаков лексекы, то есть соответствующих ей правил образования морфологических форм.

Указанные аадачм не являются тривиальными ввиду большого разнообразия словоизменительных классов во флективном языке и сложности формальных правил преобразования буквенного состава слова при образовании его форм. Ср.: при анализе: бруском —> брусок, дне кем, буйком, партком, босиком, незнаком; при синте-эе: СТОЛ —> столы, стулья, сны, сыновья, небеса, стога, круги, лотки, потоки, Д5ти. Шстроение списка всех словоформ языка в явном виде не приводит к эффективному решению задач морфологической .обработки текста, хотя бы ввиду недопустимого замедления выборки информации из столь большого массива.

В функции универсальной морфологической системы входит автоматическое решение перечисленных выше задач. Поскольку мор'фологической обработке подвергается каждое слово текста в отдельности, основным техническим требованием к практически эксплуатируемой системе является требование высокого быстродействия. Кроме того, к универсальной системе предъявляется ряд дополнительных требований, таких, как требование последовательной обработки текста, учет переносов слов, обработка сложных слов и терминов, содержащих специальные символы, например: тридцатидвухразрядный, ОБ/2 2.1. В работе показано, что указанные задачи также не являются тривиальными.

.Инструментальной называется система, допускающая встраивание в произвольную прикладную систему, нуждающуюся в морфологической обработке текста, и работу под ее управлением. Совместимость морфологической подсистемы с использующей ее прикладной программой накладывает на нее дополнительно ряд технических требований, в частности, требование минимизации объема используемой оперативной памяти ЭВМ; требование неизменности

номеров, наэначаемых системой лексемам, при пополнении и изменении словаря; отделение лингвистической информации от программ и алгоритмов.

В области морфологической обработки текстов на естественном русском языке рядом исследователей достигнуты значительные .результаты. Крупные практически эксплуатируемые системы созданы, в частности, научными коллективами под руководством Г. Г. Велоногова, И. А. Большакова, КХ Д. Апресяна, М. Г. Мальковско-го, О. С. Кулагиной, С. А. Старостина. Значительные результаты достигнуты и зарубежными исследователями, например, К. Коскен-ниеми.

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

Цри разработке подобной системы необходим комплексный учет всей совокупности предъявляемых к ней требований. Так, требования высокого быстродействия и небольшого объема занимаемой оперативной памяти являются противоречивыми при использовании крупного морфологического словаря. Учет предъявляемых требований в их совокупности является определяющим фактором при разработке всех компонент системы, от лингвистической модели до структуры внутреннего представленя морфологического словаря. Особое внимание, однако, уделяется наиболее важным и ресурсоемким задачам, в первую очередь - задачам морфологического анализа и исправления опечаток.

12

Во второй главе излагается способ организации внутреннего представления расположенного на дисковом накопителе морфологического словаря, обеспечивающий минимально возможное количест-

I

во обращений к дисковому устройству на одно анализируемое слово, а именно - одно обращение на слово.

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

Рассматривается суффиксальное словоизменение, то есть тип словоизменения, при котором словоформы языка строятся из словарной основы и приписанного к ней справа и только справа набора суффиксов, например: чит-акщишюя, где чит- - основа, -а-щ-ими-ся - тема + суффикс + окончание +' частица. Чередования букв сводятся к включению в словарь различных основ одной лексемы. Словарь включает только основы лексем вместе с приписанной к ним грамматической и иной информацией. Предполагается, что словарь упорядочен по алфавиту.

Задача морфологического анализа, таким образом, сводится к отысканию в словаре всех начальных подцепочек предъявленной цепочки. Так, для слова отними необходимо проверить гипотетические основы отними-, отним-, отни-, отн-'. Проблема заключается в том, что алфавитное место этих цепочек отзывается в

разных блоках словаря, что приводит к необходимости считывания в оперативную память с дискового накопителя нескольких блоков.

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

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

Алгоритм не требует никакой лингвистической информации, в частности, информации о системе суффиксов и окончаний данного явыка или о сочетаемости букв в слогах. Данное обстоятельство позволяет считать рассматриваемую задачу как частный случай задачи поиска информации в базе данных, а именно, как задачу нахождения в базе всех 8аписей, ключи которых являются начальными подцепочками предъявленной буквенной цепочки.

Приводятся однопроходные алгоритмы формирования такого словаря из алфавитно упорядоченного набора словарных статей, а также обратного преобразования. Рассматривается также необходимый для решения задачи морфологического синтеза алгоритм нахождения в словаре лексемы по ее номеру, полученному ранее в процессе" морфологического анализа

Показывается, что для решения одной важной частной задачи, относящейся к проблеме поиска ближайшей цепочки и существенно используемой при решении задачи исправления орфографи-

I

чэских ошибок, также достаточно одного обращения к дисковой памяти.

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

Рассматриваются требования, предъявляемые к лингвистической модели, используемой в универсальна 1 морфологической системе, и обосновываются принятые при построении модели конструктивные решения.

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

Словоформы языка в модели образуется путем соединения буквенных цепочек - флексий, или формальных морфов, с каждой из которых связан набор морфологических характеристик. Морфы сочетается в словоформах языка в соответствии с определенными закономерностями. Первый из морфов словоформы, основа, определяет лексему и является специфическим для данной лексемы,

1.0

остальные является стандартными для данного языка. Например, читающийся:

чита- —> лексема-ЧИТАТЬ, часть речи-глагол, -юн- —> залог-действителышй, время-настоящее, -ий- —> падеж-имен., род-мужск., число-единств., -ся --> возвратный.

Соответственно, лингвистическая информация задается для основ - в хранящемся на диске словаре, для остальных морфов -в расположенных в оперативной памяти лингвистических таблицах, фи этом задается информация трех типов.

Во-первых, задается соответствие между морфами и морфологическими характеристиками. Например, падежи некоторого класса существительных выражаются окончаниями -*, -а, -у, -ом, -е. Или: чита---> часть речи - глагол.

Во-вторых, задается соответствие между буквенными вариантами начертания морфов, задаваемое в виде правил вида "после того-то пишется то-то". Например, после основы мужского рода пап- пишутся окончания -а, -ы, -е, -у, -ой (-ою), -е. Или: после -кщ- пишется -ий, -его, ..., -ем, но после -ей- пишется -ый, -ого, ..., -ом чи-та-хщ-ий, чита-ем-ый.

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

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

Вся лингвистическая информация задается в виде таблиц, а указанные выше правила - в виде ссылок на строки таблиц, приписываемых основам, морфам и столбцам таблиц. В модели имеются предопределенные правила разрешения конфликтов при определении элементов словоформы. Например, основа вахн- задает окончание -ый, а суффикс -ейщ- задает окончание -ий. Выбирается наиболее правый управляющий элемент: вахн-ейш-ий. ■

Кроме возможности или невозможности построения определенной формы слова, учитывается также затрудненность, факультативность и другие особенности употребления словоформы. Лингвистическая информация задается в форме, симметричной относительно процессов анализа и синтеза словоформ.

Приводятся алгоритмы морфологического анализа, синтеза, нормализации, интерпретации и исправления некоторых типов грамматически мотивированных орфографических ошибок. Большое внимание уделяется проб.:- правильной обработки переноса слов при анализе текста Учитывается заглавность букв. Приводятся технические приемы сокращения расхода оперативной памяти ЭВМ и времени поиска информации г словаре. Приводятся алгоритмы работы одновременно с несколькими словарями, а также в режиме совместного анализа и синтеза словоформ, например, при нормализации слов или при с'.вгоматичееком переводе.

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

тов процедура исправления опечаток предъявляет наиболее жесткие требования к вычислительной эффективности алгоритма морфологического аналиэа,. а также является наиболее ню дленной частью морфологической системы. Быстродействие существующих методов исправления опечаток Fe является удовлетворительным.

Излагаемый в работе алгоритм минимизирует число обрадений к дисковой памяти в процессе исправления опечаток. Поскольку именно считывание с диска одного блока словаря является наиболее медленной операцией в процессе морфологического анализа, такая минимизация необходима для сокращения времени работы алгоритма в целом.

Минимизируются совместно следулцие четыре показателя: (1) время получения первого варианта исправления; (2) время получения правильного варианта; (3) время получения последнего из найденных вариантов; (4) общее время поиска, то есть время установления того факта, что все варианты найдены исчерпывающа Рассматривается как средние значения, так и медианы соот-ветсвующих распределений. Особенностью алгоритма является получение, как правило, всех вариантов исправления на самой ранней стадии работы алгоритма, составляющей около 2% общего времени работы.

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

Алгоритм основан на принципе обхода "вглубь" дерева, представляющего упорядоченный по алфавиту словарь. Однако в целях минимизации первых трех из указанных выше показателей

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

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

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

Результаты экспериментов показывают, что предложенный метод исправления опечаток выбранного типа по эффективности превосходит известные.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В итоге работы над темой диссертации решена поставленная в начале исследования задача разработки принципов, моделей, методов и алгоритмов, составляющих в совокупности универсальную, языковонеаависимую в некотором классе языков, быстродействующую, экономичную'по расходу оперативной памяти ЭВМ морфологическую систему, удовлетворяющую ряду дополнительных требований.

В процессе исследования получены следующие научные результаты:

1. Разработана модель морфологического строения флективного естественного языка, эффективно реализуемая на современных ЭВМ. Под эффективностью реализации понимается небольшая потребность в оперативной памяти в сочетании с высоким быстродействием. Модель является языково-независимой в некотором классе языков, включающем русский, и отвечает определенной совокупности предъявленных требований.

2. На основании предложенной модели в комплексе и с единых позиций разработаны и программно реализованы высокоэффективные алгоритмы решения задач точного и полного морфологического анализа и синтеза, а также ряда смежных задач, тага<х как нормализация слов, обнаружение, интерпретация и исправление ошибок и опечаток, приближенный анализ новых слов. Указанные алгоритмы и программы в совокупности составляют универсальную инструментальную языковонезависимую в некотором классе языков морфологическую систему.

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

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

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

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

7. Созданы программные средства, реализующие перечисленные выше алгоритмы. Программы составлены в основном на языке Си-н- и содержат более 20 ООО строк исходного текста.

Основные результаты диссертации отражены в следупцих публикациях:

1. Гельбух А. ф. Минимизация количества обращений к диску при словарном морфологическом анализе // НГИ, сер. 2, 1991, К 6.

2. Гельбух А. Ф. Минимизация числа гипотез и обращений к дисковой памяти при словарном исправлении опечаток // НГИ, сер. 2, 1993, N Б, о. 23-30.

3. Гельбух А.Ф. Модель морфологии флективного естественного языка // Материалы III Международной конференции "Программное обеспечение ЭИГ, Тверь, НПО Центрпрограммсистем, 1990. с. 27-31.

4. Гельбух А.Ф. Морфологический анализ/синтез и проверка русских текстов // Тезисы 1-й Ежггодной Всесоюзной конференции SUU3, Мэсква, 1990.

5. Гельбух А. Ф. Црюстая оболочка системы точного морфологического анализа и синтеза текстов на естественном языке // Использование программных средств ПЭВМ для автоматизации учрежденческой деятельности, АН СССР и НТО ЦГЮ, Калинин, 1990.

6. Гельбух А. Ф. Пустая явыково-независишя оболочка системы точного морфологического анализа и синтеза текстов на естественном языке // Международный форум "Тех-Екс'90 - обмен технологиями", Болгария, Пловдив, 1990.

7. Гельбух А.Ф. Эффективно реализуемая модель морфологии флективного языка // НГИ, сер. 2, 1992, N 1.

8. Добрушина Е. Р., Савина Г. Б., Гельбух А. Ф. Разработка программных и лингвистических средств для создания баз знаний

о научных исследованиях и разработках. Отчет ВДГИЦ N 02900 056145. Москва, 1939, 35 с.

9. Добрушина Е. Р., Савина Г. Б., Гельбух А. Ф. Система точного морфологического анализа и синтеза // Программное обеспечение новой информационной технологии, АН СССР и НПО ЦПС, Калинин, 1989.

10. Загацкий Б. А., Перцов а В., Гельбух А. Ф. Лингвистический процессор базы знаний о научных исследованиях и разработках. Отчет ВНТИЦ N 02900 003868, Москва, 1990, 82 с.

11. Загацкий ЕА., Шрцов К В., Гельбух А. Ф. Система син-тшссического анализа фраз русского языка // Международный форум "Тех-Екс'90 - обмен технологиями", Болгария, Пловдив, 1990.