Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста




НазваниеФакультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста
страница1/6
Дата конвертации14.01.2013
Размер0.65 Mb.
ТипДокументы
  1   2   3   4   5   6

Белорусский государственный университет
Факультет прикладной математики и информатики



Кафедра МО АСУ



БОНДАРЕНОК АЛЕКСЕЙ ВЯЧЕСЛАВОВИЧ


АВТОМАТИЧЕСКОЕ РЕФЕРИРОВАНИЕ ТЕКСТА


Дипломная работа

студента 5 курса


“ Допустить к защите “ Руководитель

Зав. кафедрой МО АСУ Совпель Игорь Васильевич –

заведующий кафедрой МО АСУ


__ ___________ 2001 г.

Рецензент

Краснопрошин Виктор Владимирович –

доцент кафедры МО АСУ

МИНСК 2001

С


ОДЕРЖАНИЕ



ВВЕДЕНИЕ 5

2.1.1. Основные типы машинных словарей 19

2.1.2. Машинные словари русского и белорусского языка 24

2.2.1. Лексический анализ 26

2.2.2. Лексико-грамматический анализ 27

2.2.3. Синтаксический анализ 34

2.2.1. Семантический анализ 42

Глава III. Система автоматического реферирования для русского и белорусского языков 55

3.2.1. Лексический анализ и преформатирование 58

3.2.2. Лексико-грамматический анализ 61

3.2.3. Взвешивание предложений 62

3.2.4. Генерация реферата 65

Выводы 68

1.В силу близости русского и белорусского языков при построении системы реферирования для них использовалась одна и та же структура машинного словаря. 68

2.Этап автоматического анализа в разработанной системе состоит из лексического и лексико-грамматического анализа. 68

ЗАКЛЮЧЕНИЕ 69

Список использованных источников 70

Приложение1. Список лексико-грамматических кодов. 72

Приложение 2. Примеры шаблонов со словами-подсказками 75

Приложение 3. Текст “Гидросфера” 76

Приложение 4. Машинный реферат текста “Гидросфера” (размер – 30% от исходного текста) 78

Приложение 5. Машинный реферат текста “Гидросфера” полученный системой TextAnalyst 2.01 (НПИЦ “Микросистемы”) 79

(подсвечены основные понятия, размер – 27% от исходного текста) 79


П


ЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ,

СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ


ЕЯ – естественный язык

АПТ – автоматическая переработка текста

ИИ – искусственный интеллект

ЛБЗ – лингвистическая база знаний

КТ – корпус текстов

МС – машинный словарь

ТЕЯ – текст естественного языка

БСС – банк синтаксических структур

NLP – Natural Language Processing (обработка естественного языка)

HMM – Hidden Markov Model (скрытая модель Маркова)

ВВЕДЕНИЕ



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

Идея создания искусственного разума для решения сложных задач витала в воздухе с древнейших времен. Впервые ее выразил Р.Луллий (ок.1235 - ок.1315), который еще в XIV в. пытался создать машину для решения различных задач на основе всеобщей классификации понятий. В XVIII в. Г.Лейбниц (1646 - 1716) и Р.Декарт (1596 - 1650) независимо друг от друга развили эту идею, предложив универсальные языки классификации всех наук. Эти идеи легли в основу теоретических разработок в области создания искусственного интеллекта (ИИ). Но развитие искусственного интеллекта как научного направления стало возможным только после создания ЭВМ (50-е, 60-е годы), когда в рамках ИИ произошло объединение математиков (теоретиков и прикладников), психологов и специалистов в области робототехники, электроники, кибернетики, с тем чтобы научить ЭВМ в определенном смысле думать и вести себя подобно человеку (естественному интеллекту). Одновременно возникло еще одно важное совместное предприятие, объединившее математиков и лингвистов и имеющее самое непосредственное отношение к ИИ. Эта область получила название вычислительной (компьютерной) лингвистики или в соответствии с оригинальным названием Computational linguistics (CL). Ее задача как научного направления заключалась в том, чтобы научить ЭВМ понимать и обрабатывать естественный язык (текст естественного языка).

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

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

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

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

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

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

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

3. Разработать алгоритмы взвешивания элементов текста.

4. Разработать алгоритмы синтеза реферата.

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

На защиту выносятся:

- структура машинных словарей;

- алгоритмы анализа текстов на русском и белорусском языках;

- алгоритм взвешивания элементов текста;

- алгоритм синтеза реферата;

- система автоматического реферирования для русского и белорусского языков.


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


Практическая новизна и реализация результатов работы. Работа выполнена и внедрена в рамках госбюджетной НИР № 077/35 от 07.05.1999 по заданию «Разработать инструментальные программные средства семантического поиска в информационных сетях и автоматического реферирования» Программы работ по развитию единой научно-информационной компьютерной сети Республики Беларусь на 1999-2000 гг.

Апробация результатов работы. Основные результаты дипломной работы докладывались на 58-й научной конференции студентов и аспирантов БГУ. По результатам доклада работа представлена на Республиканский конкурс студенческих научных работ.

Структура и объём дипломной работы. Дипломная работа состоит из введения, трёх глав, заключения, списка литературы (12 наименований) и приложений. Общий объём работы составляет 80 страниц, в том числе 71 страница основного текста.

Глава I. Задача автоматического реферирования текста

1.1. Естественный язык как объект моделирования


При решении проблем разработки и представления знаний о ЕЯ для задач АПТ необходимо, прежде всего, учитывать природу самого моделируемого объекта, т.е. естественного языка.

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

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

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

Наконец, следует подчеркнуть важность еще одной, можно сказать фундаментальной проблемы, непосредственно связанной с разработкой знаний о ЕЯ. Речь идет об организации лингвистического эксперимента, который чаще всего ограничивается одной определенной языковой единицей, контекстом которой выступает фраза. Исследования в области ИИ показали, что ЕЯ является процессом, основанным на памяти, который требует для своего исчерпывающего изучения учета того, как обработка лингвистической информации соотносится с реальным миром. При этом исследователю недостаточно полагаться на свои интуиции в суждениях о том, как язык используется, и тесты, которые всегда более или менее искусственны, а необходимо иметь доступ к данным вне ежедневного опыта. Что же может служить тем эффективным информационным базисом, на котором возможно осуществление широкомасштабного и фундаментального исследования самых разнообразных аспектов ЕЯ? Самый убедительный и надежный источник знаний о ЕЯ - это сам язык в том виде, в котором он действительно используется в речи и при написании, т.е. в виде некоторого определенным образом подобранного множества текстов ЕЯ. Именно они обеспечат объективность и чистоту эксперимента. При этом наиболее оптимальной будет следующая схема. На основании опыта, интуиции исследователя разрабатывается лишь некоторая основная совокупность свойств и правил ЕЯ, которая затем корректируется в ходе лингвистического эксперимента с разными текстами достаточно большого объема (эти объемы, также как и категории текстов, принципы их формирования и т.п. должны быть тщательно аргументированы). Вполне возможно, что полученные в результате такого тестирования данные могут оказаться настолько неожиданными, что приведут к пересмотру общепринятых способов описания некоторых языковых фактов, выработке новых лингвистических понятий и принципов, а иногда и к ревизии лингвистических концепций.

Таким образом, полигоном лингвистического эксперимента должны стать крупные машинные архивы – корпуса текстов (КТ) – с соответствующими инструментальными средствами доступа, извлечения, переработки и т.п. ЕЯ-информации. Именно в этом направлении ведут свою работу десятки научно-исследовательских групп и лабораторий мира. Так, например, фирма IBM осуществляет соответствующие исследования на основе корпуса текстов в 60 млн. слов, фирма MDC создает корпус текстов в 5 млрд. слов.
1.2. Постановка задачи автоматического реферирования


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

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

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

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

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

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

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

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



1. Как объект моделирования естественный язык имеет следующие особенности:

- неоднородность правил;

- недостаточность формализации;

- неабсолютность правил.

2. Основными этапами автоматического реферирования являются:

- автоматический анализ входного текста

- взвешивание (оценивание) элементов текста

- генерация реферата

Глава II. Методы и алгоритмы автоматического реферирования текста
2.1. Машинные словари естественных языков


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

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

Машинные словари (МС) [1] являются основным компонентом ЛБЗ, от их разработки и метода представления в памяти ЭВМ существенно зависит эффективность систем АПТ и, прежде всего, скорость обработки входного текста. Поэтому вопросы, связанные с организацией хранения словарей, поиска в них, корректировки и т.п., играют одну из важнейших ролей при проектировании систем такого типа, тем более, что речь идет об больших по объему массивах данных — порядка 103—105 слов и порядка 106 – 107 байтов памяти ЭВМ. При этом наиболее подходящая структура словаря и метод его обработки зависят не только от объемных параметров словаря, но и от конфигурации используемой ЭВМ, характеристик операционной системы и т.п.

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

Словарь основ состоит из списка основ и списка окончаний. Во время работы с таким словарем необходимые формы слов образуются путем присоединения по заданным правилам (алгоритмам) соответствующих окончаний к основам. Словари основ позволяют сократить объем памяти, отводимой под МС. Однако для такого словаря требуются чрезвычайно громоздкие алгоритмы морфологического анализа и весьма трудоемкая работа по морфологическому описанию данного ЕЯ.

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

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

  1   2   3   4   5   6

Добавить в свой блог или на сайт

Похожие:

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconПрикладная математика и кибернетика
Факультет прикладной математики и кибернетики, кафедра прикладной математики, кафедра исследования операций, кафедра теории вероятностей...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconФакультет бизнес-информатики и прикладной математики магистратура

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconПрограмма дисциплины История прикладной математики и информатики
Программа дисциплины История прикладной математики и информатики для подготовки магистров по направлению 010500. 68 (магистерская...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconУчебно-методический комплекс по дисциплине "компьютерное моделирование" (факультет прикладной информатики и информационных технологий) для специальности (050202-09-14 R)
Курс компьютерное моделирование предназначен для подготовки будущих учителей с квалификацией "Учитель информатики и математики" к...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconФакультет теоретической и экспериментальной физики кафедра прикладной математики
Перед каждой лекцией студентам рекомендуется повторить материал предыдущих лекций и семинаров

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconЛекция 4 Обеспечивающие подсистемы асу
Асу; программное обеспечение асу; техническое обеспечение асу; лингвистическое обеспечение асу; информационное обеспечение асу; организационное...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconАлгоритм реферирование текста 2 ® Утёмов В. В
Можно принимать во внимание только левосторонние связи, то есть связи с предшествующим текстом, не учитывая правосторонние связи,...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconРоссийской Федерации Государственный университет Высшая школа экономики Факультет бизнес-информатики Отделение прикладной математики
Центральной частью курса служат высшая алгебра и ее алгоритмические приложения, которые являются необходимым фундаментом для большинства...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconРабочая программа курса "основы автоматизированных систем управления" Лекции -60 ч. Цели и задачи дисциплины, ее место в учебном процессе. 1
Асу концентрируются знания из различных областей знаний математики, вычислительной техники, информатики, коммуникаций, эргономики,...

Факультет прикладной математики и информатики Кафедра мо асу бондаренок алексей вячеславович автоматическое реферирование текста iconФакультет бизнес-информатики и прикладной математики Программа дисциплины бизнес и политика
...


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница