Анализ способов представления информации морфемными структурами при наличии случайных возмущений тема автореферата и диссертации по физике, 01.04.03 ВАК РФ

у V ч

На правах рукописи

» пси

Сычев Александр Васильевич

АНАЛИЗ СПОСОБОВ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ МОРФЕМНЫМИ СТРУКТУРАМИ ПРИ НАЛИЧИИ СЛУЧАЙНЫХ ВОЗМУЩЕНИЙ

Специальность 01.04.03 - радиофизика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Воронеж - 1998

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

Научный руководитель - доктор технических наук,

профессор Хромых В.Г.

Официальные оппоненты:

- доктор технических наук, профессор Бухарин C.B.

- кандидат физико-математических наук, доцент Радченко Ю.С.

Ведущая организация - НПО "Заря" (г. Воронеж).

Защита состоится " деке&Ьл_ 1998 г. в —

на заседании диссертационного совета Д 063.48.06 по присуждению учено* степени кандидата физико-математических наук в Воронежско!\ государственном университете по адресу:' 394693, г. Воронеж, Универси тетская пл., 1, аудитория № У39

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

Автореферат разослан "23"_кэл&ря_1998 г.

Ученый секретарь диссертационного совета к.ф.-м. наук, доцент /,; у

Маршаков В.К.

Общая характеристика работы.

Актуальность темы обусловлена глобализациией и интенсификацей соммуникаций (системы сотовой связи, Internet и т.д.), которые выдвигают фоблему передачи информации в число приоритетных. Актуальными на :егодняшний день становятся вопросы повышения пропускной способности ;етевых и других коммуникационных каналов для обеспечения максимально [асыщенного (аудио, видео) взаимодействия абонентов и пользователей в >ежиме реального времени, а также обеспечение защиты каналов от ^санкционированного доступа.

Все это требует решения ряда радиофизических задач.

Феномен коммуникации в социальных системах, в том числе в тех, в :оторых он опосредован материальными средствами (что и 'будет нас ттересовать в дальнейшем в • первую очередь), предполагает наличие трех лементов:

1) субъекта - источника информации;

2) среды передачи информации;

3) субъекта - приемника информации.

В рамках теории информации и кодирования первые два элемента были ыведены за пределы рассмотрения путем редукции их к некоторому источнику

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

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

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

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

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

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

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

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

Таким образом, в работе были использованы методы, большей частью ¡ентированные на дискретную математику, поскольку исследование »водилось над полями представленными конечными и конечно южденными множествами и системами конечных множеств - отношениями, ювной инструмент, используемый здесь, - комбинаторный анализ. И хотя 1бинаторный анализ обладает меньшей общностью и универсальностью [ятий чем дедуктивные разделы математики, он в большей степени наделен [кретным содержанием.

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

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

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

Основные положения и результаты, выносимые на публичную защиту.

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы

докладывались и обсуждались на:

- региональной научно-практической конференции "Новые информационные технологии в обучении ", г. Воронеж, 1994 г.;

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

- IV всероссийской конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования", Тамбов, 1995 г.;

- научно-технической конференции "Направления развития систем и средств радиосвязи", г. Воронеж, 1996 г.;

- 2-й Международной конференции "Теория и техника передачи, приема и обработки информации", г. Туапсе, 1996 г.;

- 3-й Международной конференции "Теория и техника передачи, приема и обработки информации", г. Туапсе, 1997 г.;

- 4-ой Международной научно-технической конференции "Радиоло навигация, связь", г.Воронеж, 1998 г.;

- научно-технической конференции "Информационная безопа< автоматизированных систем", г. Воронеж, 1998 г.

Структура работы. Объем диссертационной работы составляем страниц. Работа включает в себя 41 рисунок и 10 таблиц. Приведен с литературы из 72 источников. Работа состоит из введения, четырех г заключения.

Содержание работы.

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

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

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

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

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

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

Если морфа т описывается набором языковых признаков X = (х1>Хз>-">Хо)> т0 количество информации, извлекаемой из контекста относительно морфы т определяется как

1{Х:т) = Н(т)-Н(т\Х).

После описания собственно методики проведено практическое исследование зависимости энтропии морфемного инвентаря от различных параметров. Для этого было введено многомерное пространство признаков морф C1.C2v.Cz>» в котором каждая морфа представлялась в виде точки из этого пространства. Если были известны только к признаков морфы, то им ставились в соответствие все точки из подпространства размерностью й-к (остаточный класс), построенное из исходного пространства размерности В при фиксированных значениях с^С,- • На базе инвентаря морфем было

проведено исследование зависимости усредненной по остаточным классам морф энтропии

л с^С^Сь С^С,-,

от фиксированных значений ^ в многомерном пространстве

признаков морф: С1>Сг>—Расчет выполнялся путем перебора всех возможных значений с с и подсчета соответствующего количества

морф N (с,-, с,, , ■ • • > С,,) ■ Результаты представлены в виде таблиц и графиков по

приставкам, суффиксам и окончаниям как для всех частей речи в общем так и для существительных, прилагательных и глаголов в отдельности. Из анализа полученных данных в работе был сделан вывод о том, что среди выбранных выделяются как достаточно значимые так и малозначимые языковых признаков выделяются как достаточно значимые так и малозначимые признаки. Кроме того, указано, что признаки не являются независимыми (кроме окончаний существительных), что является одной из причин существования избыточности. Также приведены оценки числа двоичных разрядов, необходимых при кодировании текстовых сообщений. Так при обычном побуквенном кодировании на одну морфу требуется в среднем от 10 до 20 двоичных разрядов, тогда как переход к представлению алфавита источника в виде простого списка морф требует 6-9 дв. разрядов для служебных морф (аффиксов) и 12-13 дв. разрядов для знаменательных (корневых) морф. Еще один важный практический вывод заключается в том, что переход к описанию морфемных фрагментов текстовых сообщений в виде набора языковых признаков увеличивает общее число морф в инвентаре из-за широко распространенного в языке явления омонимии. Однако знание 1-2 значений признаков морфы дает выигрыш, если рассматривать энтропию как оценку средней длины кодовой комбинации, необходимой для передачи морфы по каналу связи.

превосходить

функция /(х) -

где функция /(X)— .х ставит в соответствие

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

"Л"

п

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

где = = 2&082л!

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

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

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

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

Для первой задачи исследуются два случая морфемного кодирования: б< учета внутрисловного контекста и при его учете. В первом случае в качестг верхней оценки средней условной энтропии получается выражение:

ЩА\В) = ЦYxies/N- I N(l,E,s,J )х

ы £=° л=0 WW,

хlog.,Е,s,/ )] = ES^e S1 H,es(A\B),

/=i я=о j=o

где А - множество морф на входе канала, подверженного воздействию шума, ] - множество морф на выходе канала, А = В = М, М - множество всех Mops языка; Zmax - максимальная длина морфы (в буквах), Е - число искаженных бук

в морфе; s - номер вектора ошибки (¡\[3 = Cf )> 7Zw.s' вероятность задаваемог вектором ошибки искажения Е букв в морфе длины /; N - общее число морс в языке; N(X) - целочисленная функция, задающая размер подмножеств морф-гипотез, построенного для значений, указанных в качестве аргументов И, - совокупность индексов, соответствующих положению неискаженных бук внутри морфы; с помощью /к обозначен кортеж (fQ .

1 Wj-l

Приведены графики зависимости JJm —--]Г }J,Es (А | В) от числ;

N,

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

4X0 Hie = ПРИ Е = const. В связи с чем был предложен мето;

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

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

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

В полиномиальной записи вид кодовой последовательности значности п для циклических кодов дается как

An (х) = Аы (х) ■ X + ад Я(х) = А-, (X) ■ X mod Рг,

где /[к_х (х) представляет к информационных разрядов, R(x) представляет г проверочных разрядов, рг - образующий полином, tt-k + r.

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

На вход такой системы подаются информационные разряды Akayi (х) ■> в

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

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

Рисунок 1. Система передачи закодированных морф с выбором образующего полинома в зависимости от длины /

Далее рассмотрен случай, когда наряду с полученной морфой Вк рассматриваются морфы В\Вг'"Вк-\Bk+¡''' Bu, образующие вместе с ней словоформу и образующие по огношешпо к В к межморфный контекст.

Для условной энтропии с учетом межморфного контекста получено выражение

= ZI-EZZZffx

i\ í'l-l't»! i ti ' E S Nw

Jur¡ Jui-E-1

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

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

'¿ШВ1,В2,--,Вк,~;Вм) = 1: -Z P(G,-,Cd)T. I IЛХ

С, Со I Е s

Juc, } Ul-E-Í

Приведены зависимости ]~1 ¡г от числа достоверно известных значений признаков в морфе при различных значениях длины / для приставок суффиксов и окончаний. При вычислении предполагалось, что значения признаков морф известны достоверно и частоты р(С,Сп) одинаковы для всех комбинаций значений признаков. Для приставок были выбраны признаки: исходная часть речи, результирующая часть речи, сочетаемость; для суффиксов: исходная часть речи, результирующая часть речи, валентность, одушевленность, род, модель словоизменения; для окончаний: часть речи, род, число, падеж, модель словоизменения. Отмечено, что с помощью перехода от побуквенного кодирования к поморфемному можно добиться уменьшения нагрузки непосредственно на канал связи за счет такого ее перераспределения, при котором увеличиваются затраты на обработку сообщений устройствами абонентов системы связи по сравнению с затратами на передачу через канал. Приводится схема примерной организации такой системы.

Далее рассматривается проблема сжатия информации, содержащейся в текстовых сообщениях, то есть устранения естественной избыточности и замены ее управляемой. На основе анализа работ, в которых семантико-грамматическим аспектам проблемы уделяется особое внимание, сделан вывод, что здесь сжатие достигается за счет того, что исходный алфавит А = {э1 .Эг > ••• .ал/}> N I разбивается на подмножества

АЯА, / = 1.2,-..,5, А =Л]1ии-1и> I.

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

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

точки в этом пространстве. Если известны только к признаков морфы, то им

можно поставить в соответствие все точки из подпространства размерностью Ок (остаточный класс), построенного из исходного пространства размерности В при фиксированных значениях с,- ,С;-2 »■••>(?,■

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

Для кодирования текстовых сообщений на русском языке предложен следующий алгоритм. Вначале производится морфологический разбор сообщения (с привлечением синтаксического и семантического анализа по мере необходимости). На основе полученных значений с,,с2,...,с0языковых признаков морф строятся кодовые последовательности следующим образом. Для корней, суффиксов и приставок в кодовой последовательности должна содержаться информация по необходимости о всех полученных значениях признаков, поскольку для этих морф наиболее важное значение имеет внутрисловный контекст. Кроме того, в кодовой последовательности указывается порядковый номер морфы п(с1,с2,...,св) внутри остаточного класса, сформированного на основе установленных признаков о >Сз >■-'Со • Для окончаний достаточно кодировать только информацию о порядковом номере внутри остаточного класса, а значения признаков кодируются по мере необходимости.

Предложена оценка избыточности:

10&32--= 1---/,

10&32 5

т

где/-длина текста в буквах, 5" = X П1 С к I' Л'7„) > т " число морф в

/=1 а-1

тексте, п,- число признаков в /-ой морфе, |с*|" число всех возможных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1р = Но-Я/ - п П к,- n,

¡=1 1

где //() - энтропия исходного множества гипотез-словоформ, //у - энтропи: множества гипотез-словоформ после "фильтрации", к,, - количество морф

гипотез соответствующих у - ой морфе / - го типа, А' - число гипотез-словоформ после "фильтрации".

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

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

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

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

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

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

5. Разработана интегрированная программно-реализованная система дт инвентаризации морфемного состава русского языка, проведения ei информационных измерений и контроля его целостности.

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

1. Сычев A.B. Система грамматического разбора предложат естественного языка и обучение программированию на языке Пролог Новые информационные технологии в обучении: Тезисы доклад< региональной научно-практической конференции "Черноземье - 94". Воронеж, 1994. - с. 134 - 136.

2. Сычев A.B. О возможности использования технологии искусственно. интеллекта а npoifecce усвоения лингвистических знаний. Проблем современных технологий обучения и развития умственной активносп студентов и школьников: Тезисы республиканской научно-практичест конференции. - Воронеж, 1994. с. 11. . '

3. Хромых В.Г., Сычев A.B. Использование знаковой природы языка д. передачи информации через канал связи с шумом. /7 Мезювузовский сборт научных трудов "Синтез, передача и прием сигналов управления и связь Воронеж, ¡995. - с.8-13.

4. Хромых В.Г., Сычев A.B. Интеллектуальная обработка и переда1 сообщений на естественном языке. // Сборник материалов всероссийской конференции "Повышение эффективности средсг, обработки информации на базе математического и машинно. моделирования". Тамбов, 1995,- с. 305 - 307.

5. Хромых В.Г., Сычев A.B. Кодирование сообщений на основе их знаково-языковой природы // Межвузовский сборник научных трудов "Синтез, передача и прием сигналов управления и связи". Воронеж, 1996. - 179-186.

6. Сычев A.B., Хромых В.Г. Применение языковой грамматики для управления параметрами кода // Сборник докладов научно-технической конференции "Направления развития систем и средств радиосвязи". Воронеж, 1996, т.2.

7. Сычев A.B. Задачи сжатия, шифрации и помехоустойчивого кодирования сообщений с точки зрения знаково-языкового подхода // Сборник тезисов докладов 2-й Международной конференции "Теория и техника передачи, приема и обработки информации". Харьков-Туапсе, 1996. Часть П. с. 200-201.

8. Хромых В.Г., Сычев A.B. Оценка информационной емкости систем передачи информации, основанных на морфемном кодировании '/ Вестник ВГУ. Серия 2, Естественные науки. 1996. ,\Ь2, с. 140-147.

9. Хромых В.Г., Сычев A.B. Поморфемная шифрация сообщений Прикладные вопросы цифровой и защиты информации: Межвузовский сборник научных трудов. - Воронеж: ВВШ МВД России, 1997. - с. 4-6.

10. Хромых В.Г., Сычев A.B. Корректирующая способность моделей словообразования в системах передачи сообщений на естественном языке.

Сборник тезисов докладов 3-й Международной конференции "Теория и техника передачи, приема и обработки информации". Харьков-Туапсе, 1997. с. 45-46.

11. Хромых . В.Г., Сычев A.B. Экспериментальное исследование корректирующей способности языковых структур. // Межвузовский сборник научных трудов "Синтез, передача и прием сигначов управления и связи". Воронеж, 1998. - с.4-7.

12. Хромых В.Г., Сычев A.B. Машинная оценка избыточности текстовых сообщений на естественном языке / Сборник докладов 4-ой Международной научно-технической конференции "Радиолокация, навигация, связь". - Воронеж, 1998. Т. 1, с. 557-565.

13. Хромых В.Г., Сычев A.B. Повышение устойчивости зашифрованных сообщений к криптоанализу путем сокращения избыточности // Сборник докладов научно-технической конференции "Информационная безопасность автоматизированных систем". Воронеж, 1998. - с. 337-342.

14. Хромых В.Г., Сычев A.B. Исследование корректируюшей способности поморфемного кодирования текстовых сообщений, передаваемых через канал связи с шумом // Изв. высш. учеб. заведений. Радиоэлектроника.

Заказ №389 от20.».1998 г. Тир. 1 СО экз. Лаборатория оперативной полиграфии ВГУ

Воронежский государственный университет

На правах рукописи

Сычев Александр Васильевич

АНАЛИЗ СПОСОБОВ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ МОРФЕМНЫМИ СТРУКТУРАМИ ПРИ НАЛИЧИИ СЛУЧАЙНЫХ ВОЗМУЩЕНИЙ

Специальность 01.04.03 - радиофизика 1

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель -доктор технических наук, профессор Хромых В.Г.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.................................................................................................4

ГЛАВА 1. Анализ способов представления информационных полей.... 13

1.1. Система передачи информации........................................................... 13

1.2. Информационные оценки для линейного представления сообщения.........................................................................15

1.3. Формальная модель языкового взаимодействия и специфика естественного языка.............................................................................18

1.4. Моделирование языковой системы.....................................................20

1.5. Уровни иерархической структуры языка.............................................22

1.6. Факторы формирующие информативность языковых сообщений.....26

ГЛАВА 2. Методика измерения характеристик информационного поля. 29

2.1. Постановка задачи................................................................................ 29

2.2. Морфологическая структура и ее особенности.................................. 29

2.3. Инвентаризация морфемного состава русского языка.......................32

2.4. Выбор подхода к измерению информативности................................ 34

2.5. Практическое исследования энтропии морфемного инвентаря......... 37

2.6. Проблема выбора признаков для морфем

и ее связь с избыточностью...................................................50

ГЛАВА 3. Исследование устойчивости информационного поля к

случайным воздействиям............................................. 58

3.1. Помехоустойчивое кодирование и корректирование ошибок............ 58

3.1.1. Использование внутриморфного «контекста»................................. 61

3.1.2. Использование межморфного контекста.......................................... 70

3.2. Оптимальное кодирование и сжатие текстовых сообщений.............. 82

3.3. Поморфемная шифрация..................................................................... 90

ГЛАВА 4. Машинное моделирование взаимодействия

структур информационного поля...................................... 96

4.1. Постановка задачи............................................................................... 96

4.2. Описание структуры системы и ее работы..........................................99

4.3. Результаты эксперимента.................................................................... 106

4.4. Описание программного пакета...........................................................111

ЗАКЛЮЧЕНИЕ.............................................................................................113

СПИСОК ЛИТЕРАТУРЫ.............................................................................116

»

ВВЕДЕНИЕ.

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

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

Феномен коммуникации в социальных системах, в том числе в тех, в

г

которых он опосредован техническими средствами (что и будет нас интересовать в дальнейшем в первую очередь), предполагает наличие трех элементов:

1) субъекта - источника информации;

2) среды передачи информации;

3) субъекта - приемника информации.

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

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

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

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

Попытки использования результатов лингвистической науки в

конкретных прикладных системах (машинный перевод, распознавание и

>

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

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

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

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

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

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

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

разделы математики, он в большей степени наделен конкретным содержанием.

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

степенью полноты нежели это имеет место в теории информации, которая

>

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

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

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

Основные положения и результаты, выносимые на публичную защиту.

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

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

комбинаторном подходе к измерению информации;

}

• определена зависимость избыточности текстовых сообщений текстовых сообщений от ряда факторов, предложена методика их оценки и определены способы сокращения избыточности;

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

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

Диссертационная работа состоит из введения, четырех глав и заключения.

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

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

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

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

4

языковые факторы, как увеличивающие так и уменьшающие избыточность сообщений.

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

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

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

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

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

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

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