Содержание к диссертации
Введение
Глава 1. Развитие методов анализа и синтеза форм слов естественных языков в ХХ – XXI вв. 14
Глава 2. Методы повышения скорости анализа форм слов 27
2.1. Обозначения строк 27
2.2. Преобразования строки. Элементарные преобразования 28
2.3. Цепочки преобразований
2.3.1. Обозначения цепочек, их тождественность и эквивалентность 32
2.3.2. Избыточность цепочек и их редукция
2.4. Грамматическая информация и цепочки преобразований 38
2.5. Повышение скорости анализа форм слов в текстах
2.5.1. Направления работ по ускорению процесса анализа форм слов 40
2.5.2. Ускорение анализа форм слов путём оптимизации представления цепочек преобразований 41
2.5.3. Хранение всех словоформ в словаре для ускорения анализа форм слов 47
2.5.4. Рекомендации к выбору алгоритма анализатора 51
Глава 3. Представление знаний о формообразовании естественных языков 53
3.1. Подходы к организации словарей в системах анализа форм слов 54
3.1.1. Хранение правил преобразования без их структуризации 54
3.1.2. Таблицы основ, окончаний и вспомогательные таблицы 54
3.1.3. Словари со структурированной грамматической информацией 55
3.2. Представление основных структурных единиц словаря 56
3.2.1. Элементарные компоненты грамматической информации 56
3.2.2. Представление морфологических форм 57
3.2.3. Представление правил получения словоформ 57
3.2.4. Представление парадигм 58
3.2.5. Иерархия типов слов в словаре 63
3.2.6. Обобщённая структура словаря 65
3.3. Представление результатов анализа слов текста и словаря 67
3.3.1. Форматы хранения словаря и файлов с результатами анализа 68
3.3.2. XML-представление словаря 69
3.3.3. Формальная грамматика, описывающая словарь 70
3.3.4. Кодирование результатов анализа текста 74
3.3.5. Хранение результатов при наличии полного банка словоформ 79
3.3.6. Морфологическое сжатие текста 79
Глава 4. Разработка комплекса программ определения и генерации форм слов естественных языков 82
4.1. Цели и задачи разработки комплекса программ генерации и определения форм слов 82
4.2. Выбор средств разработки 83
4.3. Планирование структуры модулей системы 84
4.4. Реализация основного модуля генерации и определения форм слов естественных языков 87
4.5. Реализация редактора словарей информационной системы 92
4.5.1. Задачи, решаемые средством редактирования словарей 92
4.5.2. Структура редактора словаря
4.6. Применение алгоритмов анализа и синтеза форм слов в электронных словарях 96
4.7. Экспериментальная проверка эффективности алгоритмов анализа форм слов естественных языков 97
Заключение 101
Библиографический список 103
- Обозначения цепочек, их тождественность и эквивалентность
- Ускорение анализа форм слов путём оптимизации представления цепочек преобразований
- Словари со структурированной грамматической информацией
- Задачи, решаемые средством редактирования словарей
Введение к работе
Актуальность темы исследования. В настоящее время информация является одним из наиболее ценных ресурсов в мире. Объёмы информации, порождаемой, передаваемой и, как следствие, нуждающейся в оперативной обработке и, что немаловажно, оперативном восприятии, непрерывно растут. Вследствие этого всё большую ценность приобретают методы автоматизации обработки информации.
Текст является одной из важнейших форм представления информации, поэтому в свете постоянного увеличения интенсивности информационных потоков всё более важную роль играет автоматическая обработка текста.
Обработка текста на естественном языке – это процесс, включающий в себя несколько стадий, соответствующих уровням обработки текста: морфологический (выделение и анализ отдельных слов текста), синтаксический (определение структур предложений), семантический (выявление смысла) и прагматический (определение целей говорящего).
Предсинтаксический анализ текста на естественном языке, включающий в себя в общем случае этап разбиения текста на слова и этап определения форм слов, является необходимым в любом процессе, включающем обработку текста на естественном языке, поэтому тема диссертации, посвященная повышению скорости определения форм слов в текстах на естественных языках, является актуальной.
Степень разработанности темы. Существенный вклад в развитие методов автоматической обработки текстов на естественных языках внесли отечественные учёные Г.Г. Белоногов, Э.В. Попов, Д.А. Поспелов, Ю.Д. Апресян, М.Г. Мальковский, И.В. Сегалович, В.М. Брябин, О.С. Кулагина, Ю.Н. Марчук, И.А. Мельчук, А.С. На-риньяни, В.А. Фомичев и другие, а также зарубежные специалисты Т. Виноград (T. Winograd), В.А. Вудс (W.A. Woods), К. Коскенниеми (K. Koskenniemi), М. Портер (M. Porter), Н. Хомский (N. Chomsky), Д. Джурафски (D. Jurafsky), Дж. Мартин (J.H. Martin) и другие.
Первым этапом обработки текста является этап определения форм слов. Алгоритм определения форм слов – это правило, ставящее в соответствие каждому из слов анализируемого текста специальный маркер, описывающий грамматическую информацию, присущую этому слову (например, «столами» – «неодушевлённое существительное во множественном числе, в творительном падеже»).
Существует целый ряд алгоритмов определения форм слов, однако каждому из них присущи некоторые недостатки (невысокая скорость определения форм слов, ориентированность на конкретный язык, невозможность обратного процесса – генерации форм слов с заданной грамматической информацией).
Устранить перечисленные недостатки позволяет метод генерации и определения форм слов, который является универсальным, и допускает как анализ (определение), так и синтез (генерацию) форм слов. Однако универсальность достигается за счет низкой скорости анализа.
Соответствие паспорту специальности. Диссертация соответствует пункту 4 «Системы управления базами данных и знаний» специальности 05.13.11 – «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», поскольку в работе разработаны программные средства для ЭВМ, включающие систему управления базами знаний о формообразовании естественных языков, и метод решения задачи определения и генерации форм слов на основе этих знаний.
Цель и задачи исследования. Целью диссертационной работы является разработка методов повышения скорости определения форм слов естественных языков и усовершенствование способа представления знаний о формообразовании естественных языков.
Для достижения цели диссертационного исследования необходимо решить следующие задачи:
– разработать универсальную языконезависимую модель представления правил формообразования и алгоритмы на ее основе, применение которых повысит скорость определения форм слов;
– разработать формальное описание структуры словаря системы генерации и определения форм слов, использующей предложенные алгоритмы, что позволило бы сделать процесс заполнения словаря как можно менее трудоёмким;
– разработать информационную систему генерации и определения форм слов, реализующую разработанные алгоритмы.
Научная новизна. Научная новизна выполненных исследований состоит в следующем:
-
предложены модель представления правил формообразования естественных языков, метод повышения скорости определения форм слов на её основе, использующий особенности постфиксного базиса элементарных операций и обеспечивающий полуторакратный прирост скорости определения по сравнению с существующими аналогами и метод повышения скорости анализа на основе построения полного банка словоформ (обеспечивающий ещё большую скорость определения за счёт увеличенных затрат памяти), приведены рекомендации по их применению;
-
разработана формальная грамматика, описывающая структуру словаря для хранения знаний о формообразовании, необходимого для повышения скорости определения форм слов;
-
получено представление знаний о формообразовании русского языка в терминах предложенной модели, отличающееся высоким уровнем структуризации знаний и снижающее трудозатраты при пополнении словаря (система требует ввода только словоформ, соответствующих разрешённым комбинациям грамматических значений, исключая заведомо запрещённые, например, падежные формы неизменяемых существительных, причастия совершенного вида настоящего времени, сравнительная степень относительных прилагательных; усреднённая доля запрещённых комбинаций в русском языке для разных частей речи колеблется от 1–5% (доля неизменяемых существительных) до 90-95% (глаголы));
-
разработан метод морфологического представления текста, позволяющий сохранить результаты анализа текста и обеспечивающий сжатие текста до 30–40% от исходного.
Теоретическая и практическая значимость работы. Ценность проведенной работы состоит в том, что в её результате была построена универсальная иерархическая модель представления знаний о формообразовании естественных языков, включающая в себя и разбиение хранимых слов языка на их классы, и ассоциации классов с правилами формообразования, и гибкую систему описания парадигм для отдельных классов слов.
Для языков, характеризующихся постфиксным формообразованием, предложены алгоритмы анализа форм слов, обеспечивающие более высокую по сравнению с существующими аналогами скорость определения форм слов.
Результаты, полученные в диссертационном исследовании, являются развитием научного направления разработки и исследования универсальных методов генерации и определения форм слов.
В результате работы был создан программный комплекс, использующий предложенную модель организации знаний о формообразовании языка для решения задачи определения и генерации форм слов, включающий в себя редактор словарей, средство анализа текстов и систему проверки знаний формообразования.
Объект исследования. Объектом исследования является система правил формообразования естественного языка, исследуемая с целью построения её формальной модели для системы анализа форм слов естественных языков.
Предмет исследования. Предметом исследования являются математические модели правил формообразования естественных языков и алгоритмы, решающие в рамках этих моделей задачи генерации и определения форм слов естественных языков.
Методология и методы исследования. Теоретико-методологической основой исследования являются труды отечественных и зарубежных авторов, посвящён-ные проблемам анализа текстов на естественных языках.
К числу применённых в работе общенаучных методов относятся метод формализации, метод моделирования, системный подход.
При решении задач диссертационного исследования нашли применение теория алгоритмов и структур данных, а также элементы теории алгебр, графов, формальных грамматик, алгоритмов и морфологических категорий в лингвистике.
Положения, выносимые на защиту:
– модель представления правил формообразования естественных языков, алгоритм определения форм слов на её основе, использующий встречные префиксные деревья для представления правил формообразования, алгоритм определения форм слов, основанный на подходе «определение через генерацию»;
– формальное описание структуры словаря в системе генерации и определения форм слов (на языке описания формальных грамматик);
– представление знаний о формообразовании русского языка в терминах предложенной модели;
– алгоритм кодирования проанализированных текстов, обеспечивающий их морфологическое сжатие.
Решение поставленных задач. Решение задач проведено по следующей схеме. Рассматривается одна из существующих моделей представления правил формообразования (цепочки элементарных преобразований), анализируются возможные подходы к ускорению алгоритма анализа при определённых условиях (в частности, для постфиксного базиса элементарных операций), доказывается существование верхнего предела числа операций в цепочке, что даёт возможность более компактного представления правил преобразования. Это, в свою очередь, приводит к построению более эффективных алгоритмов анализа (для языков с постфиксным формообразованием).
Поскольку любая система анализа форм слов естественного языка, использующая словарь (слов в начальных формах или основ), обязательно требует структуризации этого словаря, в работе также решается задача создания и формального описания структуры словаря системы, использующей предложенные алгоритмы для анализа форм слов, которая позволила бы сделать процесс заполнения словаря как можно менее трудоёмким.
Для проверки практической применимости разработанных моделей и алгоритмов в рамках работы создан программный комплекс Salvinia, предназначенный для решения задач определения и генерации форм слов, и набран тестовый словарь, содержащий более 8000 начальных форм слов (гистограмма, описывающая структуру тестового словаря, приведена в автореферате).
С помощью созданного программного комплекса выполнен ряд контрольных замеров скорости определения форм слов на больших наборах слов с целью сравнения её со скоростью работы существующих средств анализа.
Личный вклад диссертанта. Все результаты диссертационной работы получены автором самостоятельно, что отражено в приводимой в конце автореферата библиографии. Программные средства, реализующие предложенные алгоритмы, разработаны автором. Работы, выполненные в соавторстве, подчинены общей постановке проблемы и концепции её решения, предложенной автором.
Степень достоверности и апробация результатов. Достоверность научных результатов, вынесенных на защиту, подтверждена экспериментальной проверкой скорости предложенных методов, свидетельством о регистрации программы для ЭВМ, наличием актов внедрения исследований в организациях и компаниях.
Полученные результаты докладывались на Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях» (г. Рязань, 2011, 2013 гг.), научно-практической конференции «Традиции и инновации в лингвистике и лингвообразовании» (г. Арзамас, 2012 г.), на конференции «Математические методы в технике и технологиях» (г. Рязань, 2015 г.), 6th Seminar on Industrial Control Systems: Analysis, Modeling and Computation (г. Москва, 2016 г.), а также на научном семинаре в Рязанском государственном радиотехническом университете под руководством д.ф.-м.н., профессора Миронова В.В.
Внедрение результатов работы. Результаты исследований, подтвержденные соответствующими актами, внедрены:
– в компании «Консалт Недвижимость» (г. Москва) для первоначальной классификации объявлений по их наиболее вероятным целям;
– во внутренней системе генерации документов компании «ДизайнЕвро-Строй» (г. Москва) для согласования падежей;
– в учебном процессе в ФГБОУ ВПО «Рязанский государственный радиотехнический университет».
Публикации. Основные результаты диссертации отражены в 16 работах, 7 из которых опубликованы в изданиях из перечня ВАК, 1 публикация в каталоге Web of Science. Получено 2 свидетельства о регистрации программы для ЭВМ.
Структура и объем работы. Диссертация состоит из введения, четырёх глав, разделенных на параграфы (15 параграфов), заключения, списка литературы, включающего 107 наименований, и 2 приложений. Работа изложена на 117 страницах стандартного машинописного текста, содержит 6 таблиц.
Обозначения цепочек, их тождественность и эквивалентность
Несмотря на всеобщую информатизацию и господство цифровых средств обработки, хранения, передачи и выдачи информации, одной из центральных проблем, препятствующих росту доступности информации, является проблема понимания естественного языка. Так, к примеру, на настоящий момент не существует универсальных методов формализации знаний, выраженных на естественном языке [40], хотя разнообразные прикладные онтологии на искусственных языках (например, на языке OWL) применяются довольно успешно [43]. Помимо этого, большинство людей знают очень небольшое число естественных языков, и для обладания информацией последняя должна быть переведена на эти языки – и это обуславливает актуальность проблемы адекватного машинного перевода текстов [44, 45].
С ростом актуальности задач автоматизации переводов текстов начала формироваться математическая лингвистика – ветвь науки искусственного интеллекта, которая имеет целью использование математических моделей для описания естественных языков.
В задачах обработки текстов на естественных языках традиционно выделяют морфологический, синтаксический, семантический и прагматический уровни понимания [1, 40].
На морфологическом уровне решаются задачи разбиения текста на слова (в тех языках, где такая задача решается нетривиально [46, 47]), и определения грамматической информации, соответствующей каждому из слов текста.
Синтаксический уровень включает в себя определение структуры текста, то есть деление его на предложения, устойчивые словосочетания и прочие структурные единицы текста.
На семантическом уровне система анализирует смысл, заключенный в тексте с целью формализации информации и сохранения её в формате, удобном для обработки с помощью ЭВМ, либо с целью получения представления этой информации на другом естественном языке [40]. Методы этого уровня находят своё применение в вопросно-ответных системах [2], информационно-поисковых системах [48, 49], естественноязыковых системах [7, 50], а также в интеллектуальных решателях задач и системах управления [51, 11, 52].
На прагматическом уровне система (как правило, прагматический анализ представлен блоком целей в экспертных системах, работающих в диалоговом режиме) трактует вводимую пользователем информацию как запрос или команду, и определяет возможность (или, например, правомерность) её выполнения, а также то, какие действия необходимо для этого предпринять.
В целом следует отметить, что развитие методов морфологического анализа и синтеза во многом определялось развитием средств вычислительной техники и успехами в конкретных областях математики (так, с развитием математической статистики появились методы приближенного анализа без словаря [53, 54]) и искусственного интеллекта (в частности, нейронных сетей [55]).
Подавляющее большинство методов анализа и синтеза словоформ являются зависимыми от языка и либо не могут быть применены к другим языкам вообще, либо требуют существенной переработки для функционирования в контексте других языков [56]. Это во многом обусловлено тем, что системы, использующие морфологические модули, реализующие рассматриваемые алгоритмы, изначально создавались для одного конкретного языка (или, в случае систем машинного перевода, для конкретной пары языков). Следует, однако, отметить, что сами идеи зачастую являются достаточно универсальными для их распространения если не на все естественные языки, то на значительную их часть.
В данной главе будут названы в порядке их появления основные методы, подходы и алгоритмы, применяемые для анализа форм слов естественных языков [57]. Для каждого из методов будет приведено краткое описание сути подхода, будут указаны основные преимущества и недостатки, и для тех методов, которые нашли своё применение в известных успешных проектах, таковые также будут отмечены.
Алгоритм анализа слов русского языка Г. Г. Белоногова Г.Г. Белоногов совместно с Т.С. Белоноговой и А.К. Родионовой предложили в рамках автоматизированной информационно-поисковой системы точные и приближенные процедуры морфологического анализа и синтеза словоформ [4].
Словарь основ содержит основы нормальных форм слов и вариантные основы (для двух типов изменения основы: чередования согласных и нерегулярных основ). Вариантная основа – основа, отличающаяся от основы нормальной формы слова чередованием букв.
Достоинства метода: – простота структуры словаря основ и таблиц; – простота алгоритма для слов с неизменяемыми основами; – определение словоформ, отсутствующих в словарях системы. Недостатки метода: – структура таблиц не универсальна: для синтеза форм слов необходимо преобразовать морфологическую таблицу; – словарь основ содержит несколько основ одного слова; – каждый тип изменения основы русского языка обрабатывается отдельным алгоритмом; – ориентация только на русский язык; – ориентация на флективный анализ по окончанию. В работе Г.Г. Белоногова и В.И. Богатырева [3], помимо алгоритмов анализа, приведена весьма детальная структурная информация о формообразовании в русском языке (так, приведены наиболее распространённые флективные классы слов, таблицы окончаний и таблицы для отыскания грамматической информации по окончаниям и номерам флективных классов).
Представленное деление основ на классы и, что важно, весьма полный перечень флективных классов для русского языка, представляют интерес даже вне контекста рассматриваемой автором системы.
Помимо прочего, автор предлагает приближённые методы определения основ слов, отсутствующих в словаре. В работе [3] приводится оценка, свидетельствующая о 95% вероятности правильного определения основы слова. Тестирование проводилось на словаре объёмом около 30 тысяч словоформ. В наборе, из которого были исключены иностранные слова, вероятность верного определения основы возрастала до 97%.
Следует отметить, что авторы этого подхода развивали идеи впоследствии, о чём свидетельствуют их более поздние публикации [2, 4, 5, 6] (в работах [4, 5] и некоторых более поздних работах соавторами Г.Г. Белоногова являлись Зеленков Ю.Г., Новоселов А.П., Хорошиловы Александр и Алексей). Алгоритм стемминга (М. Портер)
Мартин Портер разработал алгоритм стемминга [36] (от англ. stem – основа) (конец 1970-х), который заключается в отделении от словоформы суффиксов и окончаний и получении основы для ее дальнейшей автоматической обработки. По Портеру, основу составляют корень и приставка. Данный метод стемминга позиционируется автором как чисто алгоритмический, в отличие от словарных методов, описанных выше. В то же время в программной реализации суффиксы и окончания присутствуют в программном коде, хотя рациональней было бы хранить их в словаре. Этот метод получения основы реализован в системе Snowball [58].
Ускорение анализа форм слов путём оптимизации представления цепочек преобразований
Как нетрудно видеть, данный алгоритм для цепочки из N операций выполнит не более чем 5(iV2 + ЛО/2 сравнений с таблицей замен, и не более N- 1 замен внутри редуцируемой цепочки, то есть, предложенный алгоритм является полиноминальным от количества операций в цепочке.
Следовательно, если принять независящей от времени сложность операции сравнения с таблицей замен и операции замены внутри цепочки, легко видеть, что время работы алгоритма полиноминально зависит от числа операций в цепочке.
Заметим также, что правила 1 и 2 таблицы замен описывают ситуацию (+а-а) (независимо от того, к какому конкретно из пунктов её условно относить), и последовательность (+а-а) удаляется из редуцируемой цепочки.
Последнее правило в таблице замен соответствует любой цепочке, которую нельзя применить ни к какой строке символов, поскольку операция (+а) обеспечивает любой строке окончание а, а операция {-б) требует от полученной строки окончания б, которое, исходя из обозначений, не заканчивается на а.
Рассмотрим свойства редукции произвольной цепочки по данному алгоритму: а) ни одна из замен не меняет области применимости цепочки, следовательно, область применимости редуцированной цепочки обязательно будет совпадать с областью применимости исходной цепочки; б) любые две соседние однородные операции заменяются на одну по правилам 3 и 4 таблицы замен, так что в результирующей цепочке не может быть двух однородных операций подряд; в) всякая последовательность вида С = (+S1—S2) будет либо удалена из цепочки целиком (случай S± = S2), либо редуцирована по правилам 1 или 2 (случай, когда одна из строк 5l5 S2 содержит в себе другую справа), либо будет означать бессмысленную цепочку (оставшийся случай, когда вторая операция требует отделения окончания, которым после первой операции входная строка заведомо не обладает). Иными словами, в редуцируемой цепочке не может встретиться последовательность из операций присоединения и удаления подстроки, идущих подряд. Следовательно, ни одна из редуцированных цепочек (из числа имеющих непустую область применимости) не сможет состоять из трёх и более операций, поскольку в этом случае либо найдутся две однородные операции подряд (что исключено в силу пункта (б) вышеприведённого анализа алгоритма), либо найдётся последовательность из операций присоединения и удаления подстрок (что исключено в силу пункта (в) анализа). Вместе с тем, цепочки вида (-а+б), очевидно, не могут быть редуцированы в рамках постфиксного базиса, а значит, максимальная длина нередуцируемой цепочки в постфиксном базисе равна 2. Утверждение доказано.
Так, к примеру, для цепочки С = (-а-б+в+г-двг), приведённый алгоритм выполнит следующий ряд замен: (-а-б+в+г-двг) - (-а-б+в-дв) - (-а-б-д) - (-ба-д) - (-дба).
Все перечисленные схемы соответствуют общему случаю операции замены окончания (в случае присоединения заменяется пустое окончание, в случае отделения пустое окончание заменяет собой имевшееся).
Замечание. Имея формальное описание алгоритма редукции цепочек и определение их тождественности (пункт 2.3.1 настоящей работы), можно формально определить редуцированные цепочки как цепочки, являющиеся тождественными результату собственной редукции. Поскольку алгоритм редукции таков, что всякая цепочка имеет ту же область применимости, что и результат её редукции, а результат применения любой цепочки всегда совпадает с результатом применения цепочки, полученной в результате её редукции, в дальнейшем не будут рассматриваться нередуцированные цепочки, что позволит оставить по одному (наиболее простому в смысле числа операций) представителю от каждого из классов эквивалентности на множестве всех допустимых цепочек.
Словари со структурированной грамматической информацией
Хранение результатов анализа текста – это служебная задача, возникающая, как правило, в системах с повышенными требованиями к быстродействию, поэтому можно ожидать, что аппаратные средства таких систем будут более мощными, чем в системах, не требующих анализа крупных по объёму текстов.
Если для анализа форм слов текстов применяется алгоритм на основе банка всех известных словоформ, этот банк можно применять также и при хранении результатов анализа. В этом случае словарная часть файла может быть либо вовсе исключена (в этом случае в общий словарь анализатора достаточно добавить все допустимые для рассматриваемого естественного языка знаки пунктуации), либо представлена в упрощённом виде: вместо хранения множества трактовок достаточно хранить уникальный код словоформы, по которому она однозначно находится в полном банке словоформ.
Это позволяет сократить размер файла и ускорить его загрузку: если полный банк словоформ всегда находится в оперативной памяти, нет необходимости повторно считывать варианты трактовки слов из файла.
При сохранении результатов анализа текста в файл такого формата наблюдается сжатие текста (полученный файл имеет меньший размер, чем исходный текстовый файл). Более того, для рассмотренных текстов архиватор общего назначения сжал файл с результатами анализа до меньшего размера, чем файл исходного текста.
Это обусловлено следующими причинами: – длинные слова (например, слово «информационно-справочный», занимающее 24 байта в кодировке ANSI и 47 – в наиболее распространённой кодировке UTF-8) заменяются кодами, которые в худшем случае имеют длину 4 байта, поскольку наличие в банке более чем 229 различных словоформ (при переменной длине кода), а тем более – 232 различных словоформ (при кодировании с постоянной длиной кода, то есть без использования алгоритма, подобного приведённому на рисунке 3.3), не представляется возможным для естественного языка, так как словоформ гораздо меньше; – сама словарная часть файла может быть сокращена или опущена целиком в ситуациях, описанных в пункте 3.3.5. Сам факт наличия морфологического сжатия позволяет говорить о внедрении предложенного формата хранения результатов анализа для высокопроизводительных систем, требующих анализа и хранения больших объёмов данных.
Отметим также, что восстановление исходного текста с посимвольной точностью может быть невозможным (к примеру, алгоритмы токенизации, как правило, игнорируют цепочки белых символов (пробелы, знаки табуляции, переводов строк, и другие).
Из этого следует, что предлагаемый формат хранения текстов не является форматом общего назначения, и должен применяться только в случае, когда значение имеет не точное содержимое исходного текстового файла, а смысл текста, содержащегося в нём. К задачам, предъявляющим именно такие требования к формату хранения данных, можно отнести задачи индексации содержимого и задачи статистической обработки текстов.
Для количественной оценки морфологического сжатия был произведён обширный анализ текстов на русском языке, взятых из различных источников.
Характер текста Объём текста (слов, байт) Сжатиеархиватором(байт) Морфологическое сжатие (байт) Сжатие архиватором послеморфологического сжатия(байт) Текст типового договора 2 сторон 513, 7168 2259 (31%) 2727 (38%) 1911 (27%) Научная статья [2] (А. В. Пруцков) 3283, 50442 8647 (17.1%) 15233 (30%) 8378 (16.6%) Роман «Сами боги» (А. Азимов) 82797, 950571 188251 (20%) 327730 (35%) 167869 (18%) Введение в философию: учеб. пособие для вузов 294149, 4161770 691893 (17%) 1535125 (37%) 656488 (16%) Из таблицы 3.3 видно, что результат анализа текстового файла, сжатый архиватором общего назначения, имеет размер меньший, чем сам текст, сжатый этим же архиватором. Это является преимуществом предлагаемого формата хранения результатов анализа, например, перед текстовым форматом (как по памяти, так и по скорости загрузки файла с диска), когда общее число проанализированных текстов достаточно велико, чтобы вопрос выбора формата файла с результатами анализа с целью повышения производительности системы вообще имел смысл.
Основным преимуществом такого представления текста является то, что текст в таком формате не нужно подвергать повторному анализу: информационная система из такого файла читает поток уже проанализированных слов, снабжённых всей грамматической информацией. Поэтому хранение текста в таком формате может требоваться в информационных системах, требующих, к примеру, статистической обработки текстов, их сравнения, быстрого поиска по словоформам и быстрого поиска словосочетаний по формулам (например, «прилагательное + система» для поиска терминов «открытая система», «информационная система»).
Таким образом, основные положительные результаты, описываемые в главе 3, заключаются в – построении модели знаний о формообразовании, адекватно представляющей формообразование русского языка, а также формальной грамматики, позволяющей описать формообразование конкретного языка с помощью специализированного искусственного языка; – создании алгоритма, позволяющего сохранять результаты анализа текста и обеспечивающего при этом сжатие (результаты анализа занимают меньше места, чем исходный файл).
Задачи, решаемые средством редактирования словарей
Приложение, предназначенное для редактирования словарей информационной системы анализа и генерации форм слов естественных языков, обеспечивает решение следующих задач: – модификация знаний о языке, таких как набор супертипов, их состав, реестр грамматических категорий; – добавление новых слов в словарь; – проверка целостности базы слов (соответствие каждого из слов своим семействам, соответствие семейств типам (по картам значений у цепочек, ассоциированных с этими семействами), проверка отсутствия конфликтов карт грамматических значений), обнаружение семейств с эквивалентными наборами цепочек; – пакетные операции, обеспечивающие ускоренное добавление больших групп слов в уже имеющиеся семейства, с предсказанием наиболее подходящих семейств; – подсчёт статистических данных о словаре. Для пользователей, имеющих необходимость развивать структуру словаря конкретного языка предусмотрены такие функции, как – быстрое определение различий между схожими семействами (так, для многих глаголов с похожими правилами формообразования затруднительно мгновенно оценить, какие формы этих глаголов будут образовываться с помощью эквивалентных цепочек, а какие – нет); – быстрое определение тождественных семейств (добавленных, возможно, по ошибке); – быстрое определение структуры полной парадигмы, характерной для слов некоторого типа (для большинства семейств); – выявление пустых семейств и семейств, для которых не определены цепочки. При заполнении словаря новыми словами важны следующие возможности: – возможность определить, какое из семейств в пределах данного супертипа наиболее близко к данному слову (или, как минимум, исключить семейства, к которому это слово точно не может относиться по причине наличия несовместимых цепочек); – возможность получить наиболее вероятные формы слова для каждой из комбинаций грамматических значений, допустимых в рамках выбранного типа слов; – возможность автоматизированного последовательного добавления неизвестных слов из некоторого текста (текстового файла); – возможность быстрой навигации по всей структуре словаря (рисунок 4.4) в процессе добавления новых слов (к примеру, чтобы уточнить, подойдёт ли некоторое слово к одному из уже существующих семейств).
Структура модуля редактора словарей приведена на рисунке 4.4. Такое выделение компонентов и связей было обусловлено следующими причинами: – повторное использование кода должно требовать минимальных его модификаций (в идеале – полного их отсутствия); – во избежание нагромождения функций следует предлагать пользователю интерфейс, ориентированный на выполнение типовых операций (наряду со средствами низкоуровневого редактирования). В этом случае процедуры-мастера обеспечивают автоматизацию задач в пошаговом режиме.
Модуль редактора содержит большое число оконных классов. Каждое из вспомогательных окон редактора служит для решения конкретной задачи. При таком подходе решение общих подзадач (выбор конкретной сущности (или набора) из списка, определение и вывод на экран различий между двумя схожими сущностями) выполняется один раз, и соответствующий оконный класс повторно используется в любой задаче, требующей этого.
Алгоритмы, предложенные автором в настоящей работе, нашли применение также и в электронных словарях иностранных языков. Убедительным примером такой системы может служить разработанный коллективом авторов (при участии соискателя) Электронный русско-английский словарь математических терминов [105, 106] (рисунок 4.7).
Электронный словарь имеет функцию автоматической подсказки перевода для слова, скопированного пользователем в буфер обмена, поэтому автоматическое получение слова в начальной форме обеспечивает работу словаря в ситуациях, когда пользователь выделил слово, находящееся не в начальной форме.
Разработанный электронный словарь может быть полезен как при изучении английского языка, так и при написании научных и технических текстов на данном языке [107]. 4.7. Экспериментальная проверка эффективности алгоритмов анализа форм слов естественных языков
Для подтверждения эффективности разработанных алгоритмов и оценки практической целесообразности их применения был проведён ряд измерений и оценены некоторые параметры производительности предложенных алгоритмов.
Ключевыми характеристиками любого алгоритма, на которые ориентируются при выборе его среди возможных альтернатив, являются его скорость работы и объём памяти, потребляемой ЭВМ при работе.
Для выполнения расчётов скорости анализа и для оценки потребления памяти был выполнен анализ нескольких текстов разных объёмов с применением тестового словаря для русского языка, содержащего более 8000 начальных форм слов.