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

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

Москин Николай Дмитриевич

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

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

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

Петрозаводск - 2006

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

Научный руководитель:

к. ф.-м. н., доцент Варфоломеев Алексей Геннадьевич

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

д. т. н., доцент Рогов Александр Александрович,

к. т. н. Сидоров Юрий Владимирович

Ведущая организация:

Институт прикладных математических исследований

Карельского научного центра РАН, г. Петрозаводск

Защита диссертации состоится 3 ноября в 10 часов на заседании Диссертационного совета Д212.190.03 при Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, д. 33.

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

Автореферат разослан 2006 г.

Ученый секретарь диссертационного совета ^ Поляков В. В.

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

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

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

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

Объект исследования. Объектом исследования являются теоретико-графовые модели фольклорных текстов и методы их анализа.

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

Для этого необходимо решить следующие задачи:

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

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

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

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

Методы исследования. В работе применяются следующие методы:

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

- Методы многомерного статистического анализа данных.

- Современные возможности среды и языка программирования Delphi 7.0.

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

1. Разработана теоретико-графовая модель семантической структуры фольклорных песен, рассмотренная на примере коллекции бесёд-ных песен Заонежья XIX - начала XX века.

2. Предложены и апробированы следующие методы анализа графов:

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

2.2 Модификация метода аппроксимации для графов с упорядоченными вершинами.

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

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

4. Создана информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов на языке визуального программирования Delphi 7.0.

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

Основные положения диссертации, выносимые на защиту:

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

2. Предложен метод визуализации теоретико-графовых моделей фольклорных песен.

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

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

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

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем диссертации составляет 121 страница, включая 16 страниц приложения, 44 иллюстрации и 5 таблиц. Список литературы содержит 97 наименований источников.

Апробация работы и публикации. Основные результаты диссертации были представлены в виде докладов на III, IV и V Всероссийских конференциях RCDL «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (2001 г. — Петрозаводск, 2002 г. — Дубна, 2003 г. - Санкт-Петербург), на Седьмой конференции АДИТ «Информационные технологии: доступ к культурному наследию» (2003 г. — Пушкинские Горы), на XII Научных чтениях Даугавпилсского университета (2003 г. - Даугавпилс, Латвия), на IV Международной конференции «Рябининские чтения: Локальные традиции в народной культуре Русского Севера» (2003 г. - Петрозаводск), Международной школе молодых фольклористов (2003 г. - Пушкин), Летней школе «Формальные методы анализа и дескрипции фольклорного текста» (2004 г. - Псков), Всероссийской конференции «Проблемы компьютерной лингвистики и фольклористики» (2004 г. - Воронеж), Международ-

ной конференции «Русская и сопоставительная филология: состояние и перспективы» (2004 г. — Казань), на X Международной конференции Ассоциации «История и компьютер» (2006 г. - Москва), на научных семинарах кафедры информатики и математического обеспечения Петрозаводского государственного университета (2000—2006 гг. - Петрозаводск). По теме диссертации опубликованы 4 статьи и 5 тезисов докладов, а также получено свидетельство об официальной регистрации информационной системы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатенте).

Содержание диссертации

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

В 1 главе рассмотрены основные теоретико-графовые модели языковой структуры текстов, описанные в работах А. М. Пешковского, И. П. Севбо, Э. Ф. Скороходько, А. В. Гладкого, А. И. Новикова, А. Я. Шай-кевича и др. К таким моделям относятся лексические сети, деревья зависимостей, деревья составляющих, семантические сети и т. д. Основной особенностью данных графов является упорядоченность вершин и ребер, что соответствует последовательности появления элементов модели в тексте.

Для хранения и изучения подобных моделей предлагается использовать язык теоретико-графовой разметки TextGML (Textual Graph Modelling Language), разработанный на основе XML. Этот язык позволяет описывать теоретико-графовые модели текста, построенные по различным принципам. В его основе лежат следующие элементы (теги): tgml — корневой элемент.

text — элемент, определяющий границы текста. Элемент text имеет два атрибута: пате — название текста и type - тип текста (например, «стихотворение», «басня», «статья», «эссе» и т. д.).

text^parameter — характеристики текста (например, автор, год и место издания), которые определяются в виде элементов parameter. Каждому параметру соответствует два атрибута: id — идентификатор параметра и пате — название параметра.

g^aph - граф, соответствующий тексту. Каждый граф задается набором вершин (node) и ребер (Jink), соединяющих эти вершины. У элемента graph три атрибута: id - идентификатор графа, пате — название

графа (например, «дерево зависимостей первого предложения»), type — тип графа и directed — индикатор, указывающий, является ли граф ориентированным.

node - структурные единицы текста. У этого элемента пять атрибутов: id - идентификатор вершины, пате - название вершины (например, «основная форма слова»), type - тип вершины, order — порядок вершины в графе и id_graph — ссылка на идентификатор графа-потомка. Последний параметр позволяет организовать в тексте иерархию уровней графа, где граф низшего уровня является вершиной графа более высокого уровня.

link — отношения между единицами текста. У данного элемента семь параметров: id — идентификатор ребра, пате — название ребра, source и target - ссылки на идентификаторы вершины-источника и вершины-приемника, type — тип ребра (например, «однородность слов»), cost — сила связи и order - порядок ребра в графе.

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

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

В диссертации предложена теоретико-графовая модель семантической структуры фольклорных песен, рассмотренная на примере коллекции бесёдных песен Заонежья XIX - начала XX века, собранной Р. Б. Калашниковой из архивных фондов музея-заповедника «Кижи» и дореволюционных публикаций. Бесёдными назывались песни, исполнявшиеся в закрытом помещении - избе — во время заонежских молодежных вечеринок в осенне-зимний период. В основе этой модели лежит понятие мотива, который, по выражению Б. Н. Путилова, является «узловой категорией художественной организации произведения фольклора».

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

соответствующие синтагматическим и парадигматическим отношениям в тексте. Если связать графы мотивов, объединив одинаковые персонажи в одну вершину, то подобную структуру можно изобразить в виде единого графа сюжета песни. На рисунке 1 приведен пример теоретико-графовой модели песни «Все мужовья до жон добры» из сборника Ф. Студитского:

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

Леную побуживала. Вы белила, румяна мои Дороги были покупленныя, На вини были развожены, На бело.лицо положены; Вы белила, румяна мои, Сокатитесь со бела лица долой, Скажут: едет не милой муж домой, Не в любовь везет подарок дорогой -Шелковую плеть не хлыстанную, Молоду жону не биваную. Не убыток шелковая плеть купить, Не безчестье молода жена учить.

стряпейка горенка

Рис. 1. Граф песни "Все мужовья до жон добры"

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

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

— Упорядочение элементов графа по мере их появления в сюжете

песни.

- Группировка вершин и ребер графа согласно структуре мотивов песни и их функциональному весу.

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

При модификации этого метода будем использовать следующие закономерности:

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

Пусть р(и) и р(у) - номера слов в тексте песни, соответствующие объектам и и V. Если один объект определяется несколькими словами, то вычисляется среднее арифметическое значение их номеров. Определим естественную длину пружины 1е между вершинами и и V при помощи следующей формулы:

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

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

// = k«\d(u,v) - Лг | р(и) - p(v) I - ,

где d(u,v) - расстояние между вершинами и и v,a - коэффициент жесткости (упругости) пружины.

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

и . Тогда определим коэффициент силы отталкивания между объ-

ектами и и v по следующей формуле:

¿(2) ¿2 (И,У) A(m) + A(V) *

где ¿2 - коэффициент отталкивания, постоянный для всех вершин. В этом случае х -ая координата силы отталкивания g-(u v) будет определяться по формуле:

х ____Х" ~ ху

g(a'v) A(m) + A(v) (of(«,v))3 '

3. Чтобы учитывать порядок появления связей в сюжете песни, для каждого ребра е = (u,v) введем дополнительную силу he. Эта сила будет стремиться расположить ребра графа как можно ближе к установленным заранее упорядоченным точкам <7(a>V). Точки q^UyV) следует расположить последовательно на одинаковом расстоянии друг от друга по окружности (или полуокружности) с центром в середине экрана. Радиус окружности подбирается таким образом, чтобы полученный граф не выходил за границы экранной области.

Тогда значение для х -й координаты силы he найдем следующим образом:

K=(u,v) — С) * d(<3(u,v)»C(u,v) ) • (xq ~ Хс ) ,

где С(м v) - центральная точка ребра (центр ребра), координаты которой вычисляются как среднее арифметическое координат вершин и и v, а — коэффициент силы притяжения между <7(MjV) и c(u v). Чем он больше, тем сильнее ребро е = (и, v) стремится к точке .

В результате, общая сила F(u) , приложенная к вершине и, будет находиться как сумма трех сил:

e=(u,v)eE (u.v)eK2 e=(u,v)eE

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

Обычно задача аппроксимации формулируется следующим образом. Рассмотрим граф G с множеством вершин F = {v,,/" = 1,/?}, заданный матрицей смежности M(G). Пусть для каждой вершины v, определен порядковый номер q(vi). Возьмем некоторый граф Г с множеством вершин X = {xj,j = 1,т} , причем т меньше п. Каждому v, поставим в соответствие некоторое подмножество p(v,)eJ. Тогда построим вспомогательный граф G(r,<p) следующим образом: в качестве множества вершин возьмем V , а дугу из вершины v, в вершину Vj будем проводить тогда и только тогда, когда существуют такие вершины xs и х,, что, во-первых, xs е <p(v,) , х, е (p{Vj) и, во-вторых, в графе Г из xs идет дуга в .г,.

Для того чтобы сравнить матрицы смежности графов G и G(r,<p), вводится функционал 1Х:

h(ß,Г,ф) = ¡M(G)-M(G(r,#>))|2 = ¿К -ти(Г,(р))2 ,

',7=1

где ту и ту - элементы матрицы M(G) и A/(G(/\ ф)) соответственно. Задача аппроксимации графов состоит в нахождении такого графа Г и такого соответствия ф, при которых 1Х достигает минимума.

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

q(Vi)<q(Vj) (в противном случае ру =0). Для графа G(r,(p) матрица Р определяется на основе соответствия <р и графа Г. Пусть для некоторых вершин V, и vj ^(v/) = {x/i,x,2,...,xJ } и <p(v7) = {x7i,xy2,...,x7(}. Тогда p,j = 1, если суммарно порядок элементов из <p(Vj ) превосходит

порядок элементов из ^(v,), т. е.

i /

£X sign(q{Xji) - q(xlv)) > 0 .

1 z=1

В противном случае ру будет равняться нулю. В этом случае можно определить второй функционал «порядка» /2 :

I2{G,ry(p) = \\PiG)-P{G(<r,<p)f = £(Ру-Ру(Г,<р))2 ,

',7=1

где ру и ру - элементы матрицы P(G) и P(G(r,<p)) соответственно.

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

/ = а-/j + ¿>• /2 ,

где веса а и Ъ подбираются в зависимости от характера исследования.

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

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

- Мера на основе наибольшего общего подграфа:

где С/ - минимальный общий надграф графов ^ и С/2 .

- Мера на основе , операций редактирования (вставка, удаление и переименование вершин и ребер). Расстояние определяется как наименьшая последовательность 5 операций редактирования, которые преобразуют один граф в другой с минимальным суммарным весом /(5):

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

Тогда расстояние между графами <7,/г е Рп можно определить следующим образом:

G

rf(G"G2) = ,-max(|G,,|G2| )•

где О - максимальный общий подграф графов число вершин графа О.

- Мера на основе минимального общего надграфа:

п

пы\

3- d3(G,F)= max (¿/(g,,/f)).

На множестве расстояния dj удовлетворяют всем свойствам

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

m-l п

/'=1 /=/)!

• от-1 Я

2. D2 (G, F)=-i (2 ¿о?,, у;)+Ё ^(g., /,».

W /=1 l=M

3. £>3(G,F) = max( max d(gttft)t max

/=1,...1/и-1 i=m,.../i

В диссертации показано, что расстояние D3(G,F) удовлетворяет всем свойствам метрики.

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

При создании системы были поставлены следующие цели:

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

2. Апробация предложенных математических методов анализа графов.

3. Проведение исследований по конкретным фольклорным коллекциям.

Для этого необходимо решить следующие задачи:

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

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

3. Реализовать методы двух- и трехмерной визуализации графов.

4. Реализовать алгоритмы аппроксимации графов.

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

6. Разработать удобный интерфейс и средства помощи.

Общая структура созданной программы представлена на рис. 2.

Рис. 2. Общая структура программы

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

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

Шаг 1: Выбор параметров построения графа.

Шаг 2: Определение объектов в тексте.

Шаг 3: Разбиение объектов на группы.

Шаг 4: Определение связей в тексте.

Шаг 5: Разбиение связей на группы.

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

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

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

2. Методы аппроксимации графов (алгоритм И. Б. Мучника и алгоритм В. Л. Куперштоха - В. А. Трофимова, модифицированные для аппроксимации графов с упорядоченными вершинами и ребрами).

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

4. Методы сравнения и классификации графов при помощи метрик на основе общих подграфов и операций редактирования.

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

1. Публикация информации о проекте и предоставление коллекций текстов.

2. Демонстрация применения математических методов для анализа текстов.

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

4. Разработка и апробация методики создания подобного наукоемкого ресурса, изучение его функциональности и полезности для научного сообщества.

4 глава посвящена применению теоретико-графовых моделей для исследования коллекции бесёдных песен Заонежья XIX — начала XX века. Свойства графов анализировались при помощи следующих параметров:

• Параметры размерности графов. По числу вершин и ребер были выделены три группы песен:

1 группа: 62% песен (число вершин т < 14, а ребер п < 17 ). В эту группу попали все песни на темы «свадьба» и «игра». Также сюда вошли все медленные песни, где число объектов примерно 8-10.

2 группа: 28% песен (число вершин 14<т<20, а число ребер 14 < т < 24 ). В группу вошли любовные и семейные песни, которые исполняются в быстром темпе.

3 группа: 10% песен (число вершин /я >20, число ребер я >21). В эту группу вошли любовные и семейные песни с большим числом объектов и связей.

• Параметры связности текстов. Для анализа связности фольклорных песен введем понятие графа связности мотивов С". Пусть С, — это подграф графа С, соответствующий / мотиву. Два мотива / и у будем считать связанными, если существует вершина V* е V, такая что V* е и V* е (7у , или между некоторыми вершинами у' е С7, и у" е существует глобальное отношение. Тогда параметр связности мотивов С (С") определим по следующей формуле:

С{вт)= 2п

к{к-1) '

где к - это число мотивов, а п' — число пар мотивов, связанных между собой. Параметр С(<Зт) принимает значения на отрезке от 0 до 1.

При этом С(С") = 0 соответствует нуль-графу, а С(С") = 1 - полному графу.

В результате, по структуре мотивов песни разделились на следующие группы: 48% имеют монолитную структуру (Сш превышает значение 0,8), 34% песен имеют незамкнутую цепочечную или кусочно-линейную структуру, 12% представлены несвязными графами (Ст не превышает 0,33). Радиальные и кольцевые структуры в бесёдных песнях практически не встречаются.

• Значимость объектов в песнях. Для определения этой характеристики использовались следующие параметры:

- Максимальная степень вершины А(р) .

- Функциональный вес вершины <р„ (С).

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

При этом были обнаружены следующие закономерности. Песни, где значение А(С) превышает 10, исполняются «довольно бегло» «с тихой пляской-шеном». Это, как правило, хороводные песни. Для песен вида «бесёдная», «свадебная бесёдная» и «плясовая» в среднем значение А(Сг) равно 6,5 и не превышает 10. Для песен «в кругу-круговая» и «пляска в кругу» этот параметр в среднем равняется 10,5 с достаточно большим разбросом ( сг2 =10,7).

• Распределение объектов и связей на группы. Согласно А. Т. Хроленко, объекты песен делятся на следующие группы: «люди», «части

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

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

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

Н — >

т, + тг - тх 2

где т1 и т2 - число вершин в графах, а т12 - число общих вершин. При помощи этой меры были выделены наиболее типичные песни заданной «темы».

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

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

В приложении 1 представлено свидетельство об официальной регистрации программы для ЭВМ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатенте).

В приложении 2 содержатся примеры теоретико-графовых моделей фольклорных песен («Уж ты Ванюша, Иван», «Широкая борода», «Девушка в горенке сидела», «Тропинкой шла» и «Как назябло, навеяло лицо»).

В приложении 3 представлено DTD-описание языка TextGML 1.0 и пример формализации бесёдной песни «Все мужовья до жон добры».

В приложении 4 приводится описание нескольких алгоритмов, реализованных в информационной системе «Фольклор».

Заключение

В заключении сформулируем основные результаты работы:

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

2. Предложен метод визуализации теоретико-графовых моделей фольклорных песен.

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

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

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

6. Создана информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов на языке визуального программирования Delphi 7.0.

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

Публикации по теме диссертации

I. Москин Н. Д. Авторское свидетельство об официальной регистрации программы для ЭВМ «Информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов» № 2006612744. Федеральная служба по интеллектуальной собственности, патентам и товарным знакам (Роспатент), 03.08.2006.

2. Варфоломеев А. Г., Кравцов И. В., Москин Н. Д. Информационная система по фольклорным песням Заонежья как инструмент формализации и классификации песен // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды IV Всероссийской научной конференции RCDL'2002. Т. 2. — Дубна, 2002.-С. 143-147.

3. Варфоломеев А. Г., Москин Н. Д. Информационная система по фольклорным песням Заонежья конца XIX - начала XX века с формальным представлением структуры текста // Daugavpils Universi-tates Humanitaras fakultates XII Zinatnisko lasljumu materiali. Vesture. VI(I).- Daugavpils: Saule, 2003. - C.126-131.

4. Варфоломеев А. Г., Москин H. Д. О применении компьютерных технологий в исследовании фольклорных песен // Материалы IV Международной научной конференции «Рябининские чтения»: Локальные традиции в народной культуре Русского Севера. — Петрозаводск, 2003. - С. 424-427.

5. Варфоломеев А. Г., Кравцов И. В., Москин Н. Д. Проект специализированного Интернет-ресурса для представления и анализа фольклорных песен // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды V Всероссийской научной конференции RCDL'2003. - Санкт-Петербург, 2003.- С. 339-343.

6. Варфоломеев А. Г., Москин Н. Д. Об электронной коллекции фольклорных песен с теоретико-графовой формализацией текстов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Сборник аннотаций стендовых докладов III Всероссийской научной конференции RCDL'2001. - Петрозаводск, 2001.- С. 20.

7. Варфоломеев А. Г., Москин Н. Д. Проект информационной системы для представления и анализа текстов фольклорных песен // VII ежегодная конференция АДИТ-2003 «Информационные технологии: доступ к культурному наследию». Тезисы докладов. - Пушкинские Горы, 2003.-С. 101-103.

8. Москин Н. Д. К вопросу об изучении фольклорного наследия при помощи компьютерных технологий // Международная школа молодых фольклористов. Тезисы докладов. - Пушкин, 2003. - С. 16.

9. Москин Н. Д., Петров А. М. Духовный стих и былина: математические методы исследования специфики фольклорного жанра // Русская и сопоставительная филология: состояние и перспективы: Труды и материалы Международной научной конференции, посвя-

щенной 200-летию Казанского университета. - Казань, 2004. - С. 296-297.

10. МоскинН. Д. Применение контент-анализа для исследования коллекции текстов о народных святых Нижегородского края // Информационный бюллетень Ассоциации «История и компьютер». №34. Материалы X конференции АИК. - Москва, 2006. - С. 79-80.

Подписано в печать 18.09.06. Формат 60x84 716. Бумага офсетная. Офсетная печать. 1 уч.-изд. л. Тираж 100 экз. Изд. № 213.

Государственное образовательное учреждение высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Отпечатано в типографии Издательства Петр ГУ. 185910, г. Петрозаводск, пр. Ленина, 33

ВВЕДЕНИЕ.

ГЛАВА 1. ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ ТЕКСТОВ.

§1 Моделирование языковой структуры текста при помощи графов.

§2 Язык теоретико-графовой разметки текстов Тех10МЬ.

§3 Примеры описания теоретико-графовых моделей текстов на языке Тех10МЪ.

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

Актуальность темы

Данная работа посвящена применению математических методов и компьютерных технологий при исследовании фольклорных текстов. Уже достаточно давно в лингвистических, исторических и социальных науках для формализации текстов используется контент-анализ, который сводится к подсчету частот встречаемости в тексте определенных словосочетаний (индикаторов) [13]. Другой метод, часто применяемый в подобных ситуациях, - это представление объекта исследования в виде типологической формулы, похожей на формулу библиотечной классификации УДК. Ее использовал, например, И. Г. Левин при создании типологии таджикских сказок [55, стр. 76]. Однако такие методы, заменяющие текст набором из нескольких чисел или символов (вектором), вряд ли достаточны для отражения его содержания. Поэтому на сегодняшний день актуальным является разработка новых методов и технологий анализа текстов.

На наш взгляд, адекватной моделью для представления текста является граф, который определяется как конечное множество объектов (вершин) и множество пар различных вершин (ребер) [69, стр. 22]. Такая структура хорошо изучена с точки зрения математики и часто служит удобным средством представления структурированной информации для дальнейшего анализа. Графы используются в гуманитарных областях знаний для автоматической обработки текстов [3, 53], информационного поиска [63], реферирования и индексирования текстов [57, 59], автоматического перевода [26], стилистической диагностики [32, 56], в задачах атрибуции анонимных текстов [33, 45] и т. д. В фольклористике графы применялись крайне мало, такие работы единичны [30, 31].

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

Компьютерная лингвистика и интеллектуальные технологии», «АДИТ: Информационные технологии: доступ к культурному наследию», «Проблемы компьютерной лингвистики и фольклористики», конференции Ассоциации «История и компьютер» и т. д.

Объект исследования

Объектом исследования являются теоретико-графовые модели фольклорных текстов и методы их анализа.

Цель и задачи диссертации

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

Для этого необходимо решить следующие задачи:

1. Разработать теоретико-графовые модели структуры фольклорных текстов.

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

3. Создать информационную систему для хранения и исследования фольклорных коллекций с теоретико-графовой формализацией текстов.

4. Описать результаты применения данных методов на примере конкретных коллекций фольклорных текстов.

Структура и объем диссертации

Работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Первая глава посвящена применению графов для анализа языковой структуры текста. Здесь приводится описание языка теоретико-графовой разметки TextGML, разработанного на основе XML, который предназначен для описания теоретико-графовых моделей текстов. В конце главы рассмотрена теоретико-графовая модель семантической структуры фольклорных песен. Во второй главе представлены методы и алгоритмы анализа теоретико-графовых моделей и их модификации с учетом упорядоченности вершин и ребер. В третьей главе описывается информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов, реализованная в среде визуального программирования Delphi 7.0. В четвертой главе приводятся результаты применения разработанных методов для исследования бе-сёдных песен Заонежья XIX - начала XX века.

Общий объем диссертации составляет 121 страница, включая 16 страниц приложения, 44 иллюстрации и 5 таблиц. Список литературы содержит 97 наименований источников.

Научная новизна

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

1. Разработана теоретико-графовая модель семантической структуры фольклорных песен, рассмотренная на примере коллекции бесёдных песен Заонежья XIX - начала XX века.

2. Предложены и апробированы следующие методы анализа графов:

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

2.2. Модификация метода аппроксимации для графов с упорядоченными вершинами.

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

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

4. Создана информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов в среде визуального программирования Delphi 7.0.

Методы исследования

В работе применяются следующие методы:

1. Методы визуализации, аппроксимации и сравнения графов.

2. Методы многомерного статистического анализа данных.

3. Современные возможности среды и языка программирования Delphi 7.0.

Практическая значимость работы

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

Основные результаты, выносимые на защиту

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

2. Предложен метод визуализации теоретико-графовых моделей фольклорных песен.

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

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

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

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

Апробация работы и публикации

Основные результаты диссертации были представлены в виде докладов на III, IV и V Всероссийских конференциях ЛСБЬ «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (2001 г. - Петрозаводск, 2002 г. - Дубна, 2003 г. - Санкт-Петербург), на Седьмой конференции АДИТ «Информационные технологии: доступ к культурному наследию» (2003 г. - Пушкинские Горы), на XII Научных чтениях Даугавпилсского университета (2003 г. - Даугавпилс, Латвия), на IV Международной конференции «Рябининские чтения: Локальные традиции в народной культуре Русского Севера» (2003 г. - Петрозаводск), Международной школе молодых фольклористов (2003 г. - Пушкин), Летней школе «Формальные методы анализа и дескрипции фольклорного текста» (2004 г. - Псков), Всероссийской конференции «Проблемы компьютерной лингвистики и фольклористики» (2004 г. - Воронеж), Международной конференции «Русская и сопоставительная филология: состояние и перспективы» (2004 г. - Казань), на X Международной конференции Ассоциации «История и компьютер» (2006 г. - Москва), на научных семинарах кафедры информатики и математического обеспечения Петрозаводского государственного университета (2000-2006 гг. - Петрозаводск). По теме диссертации опубликованы 4 статьи и 5 тезисов докладов, а также получено свидетельство об официальной регистрации информационной системы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатенте).

Выход

• Мера на основе операций редактирования (переименование вершины, вставка ребра и удаление ребра). Расстояние ищется при помощи процедуры полного перебора. Однако при поиске расстояния на множестве деревьев применяется более быстрый алгоритм [91], описанный в приложении 4.

• Мера на множестве деревьев, заданная функцией подчинения [2].

На основе этих расстояний в системе организован поиск среднего графа (7 на множестве текстов коллекции £ (см. параграф 1.3 второй главы).

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

Кластерный анализ текстов

Список выбранных песен:

Группа 1 Все мужья до жен добры Широкая борода! Ты, отеческая дочь! Ты, хозяин, благослови! Не такова отце, матери бывала Группа 2

Девушка в горенке сидела Как вяла серая утка Группа 3 Уж ты Ванюша, Иван Невы зрев шей рябинушки нельзя Группа 4 Не огонь горит, не смола кипит Мальчик ты, мальчик Позябло, позябло лицо Ты пошго, мати, к орошу родила? Не стойки го стойкам стоят Воронок, воронок, черненькой воронок! Выйду на сини, на сиоероче''. Группа 5

Ач ты, вьюжик, ты, мой ььюночик. Группа 5 Туг шла, прошла корета

Распределение св язей между объект Как вила серая утка] Девушка в горенке сидела"] ; Невызревшей рябинушки нельзя эаломать [ Ты, отеческая дочь! |; || Ты, хозяин,благослови! || Не такова отца, матери бывала |. Критерий.

Распределение связей между объектами <"' Распределение объектов по группам Г Распределение связей по группам

Количество групп подобия Отображение групп. С Цветом Гругетировк.ой р' Вывести надписи Разбить на гр^лы

Изобразить графически

Подробный кластерный анализ

Рис. 29. Кластерный анализ текстов.

§3 Проект специализированного Интернет-ресурса для представления и анализа фольклорных текстов

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

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

С 2003 года аспирантом кафедры информатики и математического обеспечения Петрозаводского государственного университета И. В. Кравцовым ведется работа над представлением информационной системы по фольклорным коллекциям в виде специализированного Интернет-ресурса [16].

Основными целями создания Интернет-ресурса являются:

- Публикация информации о проекте и предоставление коллекций текстов.

- Демонстрация применения математических методов для анализа текстов.

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

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

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

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

Для организации быстрой и функционально удобной работы предполагается использовать технологию OLAP (On-Line Analytical Processing) [54]. В основном OLAP-средства используются в коммерческих приложениях, где необходим анализ больших объемов данных, собираемых операционными базами данных. Накопленные данные организуются в специальные хранилища (Data Warehouse) [6]. OLAP-средства рассчитаны на быструю обработку нерегламен-тированных запросов аналитиков к хранилищам данных. Данные в хранилищах заранее агрегированы и выстроены в многочисленные иерархии в зависимости от решаемых задач. Их можно представить, в отличие от реляционных баз данных, в виде многомерных кубов (гиперкубов), что позволяет говорить о многомерных базах данных.

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

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

Рис. 30. Запись в таблице фактов.

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

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

Такую схему таблиц с заданной иерархией измерений еще называют «звездой» или «снежинкой». В данном случае: obj wordJact - таблица фактов; song, object word, object class - таблицы измерений; collection, objectgroup - таблицы иерархии для измерений;

Рис. 31. Схема реляционных таблиц.

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

Заключение

В заключении сформулируем основные результаты работы:

1. Разработана теоретико-графовая модель семантической структуры фольклорных песен, рассмотренная на примере коллекции бесёдных песен За-онежья XIX - начала XX века.

2. Предложен метод визуализации теоретико-графовых моделей фольклорных песен.

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

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

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

6. Создана информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов в среде визуального программирования Delphi 7.0.

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

1. Прикладная статистика: Классификация и снижение размерности: Справ, изд. / С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешалкин / Под ред. С. А. Айвазяна. М.: Финансы и статистика, 1989. - 607 с.

2. Автоматическая обработка текста: Сб. ст. / Под ред. Э. Ф. Скороходько. -Киев, 1980. 74 с. - (Препринт / АН УССР. Ин-т кибернетики; 80-24).

3. Апресян Ю. Д. Идеи и методы современной структурной лингвистики. -М.: Просвещение, 1966. 302 с.

4. Артеменко Е. Б. Принципы народно-песенного текстообразования. Воронеж: Издательство Воронежского университета, 1988. - 173 с.

5. Архипенков С. Я., Голубев Д. В., Максименко О. Б. Хранилища данных. От концепции до внедрения / Под общ. ред. С. Я. Архипенкова. М.: Диалог-МИФИ, 2002. - 528 с.

6. Бауман Е. В., Мучник И. Б. Алгоритм перестройки структуры в задаче аппроксимации графов // Автоматика и телемеханика. 1976. №6. - С. 125-133.

7. Берц С., Херндон У. Подобие в графах и молекулах // Искусственный интеллект: применение в химии: Сб. статей / Ред. Т. Пирс, Б. Хони. М.: Мир, 1988.-С. 199-206.

8. Бородкин А. М., Мучник И. Б. Приближенный алгоритм аппроксимации графа, основанный на методе вторых разностей // Автоматика и телемеханика. 1977. №4.-С. 114-120.

9. Бородкин Л. И. Агрегирование структуры графов с размытыми блоками // Автоматика и телемеханика. 1978. №8. - С. 142-153.

10. Бородкин Л. И. Контент-анализ и проблемы изучения исторических источников // Математика в изучении средневековых повествовательных источников: Сб. ст. / Отв. ред. Б. М. Клосс. М.: Наука, 1986. - С. 8-30.

11. Браверман Э. М., Мучник И. Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983. - 464 с.

12. Венгранович М. А. Экстралингвистическая обусловленность лингвостиле-вой специфики фольклорного текста. Петрозаводск: Издательство Петрозаводского государственного университета, 2004. - 196 с.

13. Гладкий А. В. Синтаксические структуры естественного языка в автоматизированных системах общения / Серия «Проблемы искусственного интеллекта», №6. М.: Наука, 1985.- 144 с.

14. Древние российские стихотворения, собранные Киршею Даниловым. / Под ред. А. А. Горелова. (Серия «Полное собрание русских былин») СПб.: Тропа Троянова, 2000. - Т. 1. - 432 с.

15. Калашникова Р. Б. Беседы и бесёдные песни Заонежья второй половины XIX века. Петрозаводск: Издательство Петрозаводского государственного университета, 1999. - 162 с.

16. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 с.

17. Кулагина О. С. Исследования по машинному переводу. М.: Наука, 1979. -320 с.

18. Куперштох В. JL, Трофимов В. А. Алгоритм анализа структуры матрицы связи // Автоматика и телемеханика. 1975. №11.- С. 170-180.

19. Лысанов В. Д. Досюльная свадьба, песни, игры и танцы в Заонежье Олонецкой губернии. Петрозаводск: Северная скоропечатня Р. Г. Каца, 1916. -119,30 с.

20. Мальцев Г. И. Традиционные формулы русской народной необрядовой лирики: Исследования по эстетике устно-поэтического канона / Отв. ред. А. Ф. Некрылова. Л.: Наука, 1989. - 165 с.

21. Маранда П. «Золушка»: теория графов и множеств // Зарубежные исследования по семиотике фольклора: Сб. ст. / Сост. Е. М. Мелетинский, С. Ю. Неклюдов. М.: Наука, 1985. - С. 261-274.

22. Маранда П., Кёнгас-Маранда Э. Структурные модели в фольклоре. // Зарубежные исследования по семиотике фольклора: Сб. ст. / Сост. Е. М. Мелетинский, С. Ю. Неклюдов. М.: Наука, 1985. - С. 194-260.

23. Мартыненко Г. Я. Основы стилеметрии. Л.: Издательство ЛГУ, 1988. -173 с.

24. Марусенко М. А. Атрибуция анонимных и псевдонимных литературных произведений методами теории распознавания образов. Л.: Издательство ЛГУ, 1990.- 164 с.

25. Мелетинский Е. М. К вопросу о применении структурно-семиотического метода в фольклористике // Семиотика и художественное творчество: Сборник статей / Ред. коллегия: Ю. А. Барабаш и др. М.: Наука, 1977. - С. 152-170.

26. Миркин Б. Г. Анализ качественных признаков и структур. М.: Статистика, 1980.-319 с.

27. Миркин Б. Г., Родин С. Н. Графы и гены: Использование графов в анализе структуры функций и эволюции генетических систем / Под ред. В. А. Ратнера. -М.: Наука, 1977.-239 с.

28. Москин Н. К вопросу об изучении фольклорного наследия при помощи компьютерных технологий // Международная школа молодых фольклористов. Тезисы докладов. Пушкин, 2003. - С. 16.

29. Москин Н. Д. Применение контент-анализа для исследования коллекции текстов о народных святых Нижегородского края // Информационный бюллетень Ассоциации «История и компьютер». № 34. Материалы X конференции АИК. Москва, 2006. - С. 79-80.

30. Мучник И. Б. Анализ экспериментальных графов // Автоматика и телемеханика. 1974. №9. - С. 62-80.

31. Народные песни Вологодской и Олонецкой губерний, собранные Ф. Сту-дитским. Санкт-Петербург, 1841.

32. Новиков А. И. Семантика текста и ее формализация. М.: Наука, 1983. -215 с.

33. Описание Олонецкой губернии в историческом, статистическом и этнографическом отношениях. Сост. В. Дашков. Санкт-Петербург: тип. мин-ва внутренних дел, 1842. - 222 с.

34. От Нестора до Фонвизина: Новые методы определения авторства / Л. В. Милов, Л. И. Бородкин, Т. В. Иванова и др. / Под редакцией Л. В. Милова. М.: Прогресс, 1994.-445 с.

35. Песни городенского хора / Составление, предисловие, нотация напевов Е. Е. Васильевой. Новгород, 1990. - 144 с.

36. Песни, собранные П. Н. Рыбниковым / Под ред. Б. Н. Путилова. Т. 1. Былины. - Петрозаводск: Карелия, 1989. - 527 с.

37. Пешковский А. М. Русский синтаксис в научном освещении. 8-е изд. -М.: Эдиториал УРСС, 2001.-450 с.

38. Повести, сказки, притчи древней Индии / Перевод с пали и санскрита. Сост., предисл. и примеч. А. Я. Сыркина. М.: Наука, 1964. - 300 с.

39. Проблемы анализа дискретной информации: Сборник научных трудов / Новосибирск: ИЭиОПП, 1975. 181 с.

40. Путилов Б. Н. Фольклор и народная культура. In Memoriam: Сб. / Сост. Е. О. Путилова; Отв. ред. А. Н. Анфертьев. СПб.: Петербургское Востоковедение, 2003.-464 с.

41. Рэй Э. Изучаем XML. Пер. с англ. - СПб.: Символ-Плюс, 2001. - 408 с.

42. Сайт проекта «Автоматическая обработка текстов», http://www.aot.ru

43. Сахаров А. А. Концепция построения и реализации информационных систем, ориентированных на анализ данных // СУБД. 1996. №4. - С. 55-70.

44. Свод таджикского фольклора / Под ред. И. Г. Левина. М.: Наука, 1981. — Т.1. Басни и сказки о животных. - 389 с.

45. Севбо И. П. Графическое представление синтаксических структур и стилистическая диагностика. Киев: Наукова Думка, 1981. - 192 с.

46. Севбо И. П. Структура связного текста и автоматизация реферирования / Под ред. С. К. Шаумяна. М.: Наука, 1969. - 136 с.

47. Седжвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах. -СПб: ООО «ДиаСофтЮП», 2003. 480 с.

48. Скороходько Э. Ф. Семантические сети и автоматическая обработка текста. Киев: Наукова думка, 1983. - 218 с.

49. Собрание народных песен П. В. Киреевского: Записи П. И. Якушкина / Отв. ред. А. А. Горелов (серия «Памятники русского фольклора»). JL: Наука. Ленингр. отд-ние, 1986. - Т. 2. - 325 с.

50. Спецификация GXL. http://www.gupro.de/GXL/

51. Спецификация XGMML. http://www.cs.rpi.edu/~puninj/XGMML/

52. Сэлтон Г. Автоматическая обработка, хранение и поиск информации / Под ред. А. И. Китова. -М.: Сов. радио, 1973. 530 с.

53. Тарланов 3. К. Методы и принципы лингвистического анализа: Учебное пособие для вузов. Петрозаводск: Издательство Петрозаводского университета, 1995.- 189 с.

54. Терехина А. Ю. Анализ данных методами многомерного шкалирования. -М.: Наука, 1986.- 166 с.

55. Тулдава Ю. Проблемы и методы квантитативно-системного исследования лексики. Тарту: ТГУ, 1987. - 203 с.

56. Турыгина Л. А. Моделирование языковых структур средствами вычислительной техники. М.: Высшая школа, 1988. - 175 с.

57. Фаронов В. В. Delphi. Программирование на языке высокого уровня: Учебник для вузов. СПб.: Питер, 2004. - 640 с.

58. Харари Ф. Теория графов / Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 3-е, стереотипное. М.: КомКнига, 2006. - 296 с.

59. Химические приложения топологии и теория графов: Материалы симпозиума 18-22 апреля 1983 г., Афины, шт. Джорджия, США / Под ред. Ю. А. Жданова. -М.: Мир, 1987. 560 с.

60. Хроленко А. Т. Поэтическая фразеология русской народной лирической песни. Воронеж: Издательство Воронежского университета, 1981. - 163 с.

61. Хроленко А. Т. Семантика фольклорного слова. Воронеж: Издательство Воронежского университета, 1992. - 139 с.

62. Шайкевич А. Я. Дистрибутивно-статистический анализ текстов // Принципы и методы семантических исследований: Сб. статей / Под ред. В. Н. Ярцева. -М.: Наука, 1976. С. 353-378.

63. Шемакин Ю. И. Начала компьютерной лингвистики: Учебное пособие. -М.: Издательство Московского государственного открытого университета, 1992.- 113 с.

64. Ю. М. Лотман и тартуско-московская семиотическая школа / Сост. А. Д. Кошелев. М.: Гнозис, 1994. - 547 с.

65. Яншин В. В. Анализ и обработка изображений: принципы и алгоритмы: Учебное пособие для вузов. М.: Машиностроение, 1995. - 111 с.

66. Brandes U. Drawing on physical analogies // Lecture Notes in Computer Science. 2001. - Vol. 2025 - P. 71-86. http://citeseer.ist.psu.edu/631581 .html

67. Bunke H. Graph matching for visual object recognition // Spatial Vision. Vol. 13,No. 2-3.-2000.-P. 335-340.http://iamwww.unibe.ch/~fki/publications/public/Bu00-001.ps.gz

68. Bunke H. Graph matching: theoretical foundations, algorithms, and applications // Proc. Vision Interface. Montreal, 2000. - P. 82-88. http://tcw2.ppsw.rug.nl/ki2/literature/graphmatch-bunke.pdf

69. Bunke H., Jiang X., Kandel A. On the minimum common supergraph of two graphs // Computing. 2000. - Vol. 65, No. 1. - P. 13-25. http://wotan.liu.edu/docis/dbl/comput/2000 65 1 13 QTMCSQ.html

70. Bunke H., Shearer K. A graph distance metric based on the maximal common subgraph // Pattern Recognition Letters. 1998. - Vol. 19, No. 3-4. - P. 255-259. http://citeseer.ist.psu.edu/bunke98graph.html

71. Cardenosa J., Gelbukh A., Tovar E. Universal networking language: advances in theory and applications / Special issue of «Research on Computing Science». IPN, 2005.-Vol. 12.-443 p.

72. Codd E. F., Codd S. B., Salley C. T. Providing OLAP (on-line analytical processing) to user-analysts: an IT mandate // Technical Report, E. F. Codd & Associates, 1993.http://www.cs.bgu.ac.il/~dbm031/dw032/Papers/olaptouseranalystswp.pdf

73. Di Battista G., Eades P., Tamassia R., Tollis I. Algorithms for drawing graphs: an annotated bibliography // Computational Geometry Theoiy & Applications. -1994. Vol. 4, No. 5. - P. 235-282. http://www.cs.brown.edu/people/rt/papers/gdbiblio.pdf

74. Eiglsperger M., Fekete S. P., Klau G. W. Orthogonal graph drawing // Lecture Notes in Computer Science. 2001. - Vol. 2025. - P. 121 -171. http://www-ma2.upc.es/wood/papers/OrthogonalGraphDrawingSurvey- / LNCS2025.pdf

75. Isert C. The editing distance between trees // Ferienakademie Bäume: Algorith-mik und Kombinatorik. Sarntal, Italy, 1999. http://citeseer.ist.psu.edu/isert99editing.htinl

76. Ruspini E., Wolverton M. Graph-editing metrics for pattern matching // Working paper, Version 3. 2002.http://www.ai.sri.com/~law/graph-edit-distance-wk3.pdf

77. Sugiyama K., Tagawa S., Toda M. Methods for visual understanding of hierarchical system structures / IEEE Transactions on Systems, Man and Cybernetics. -1981.-Vol. 11, No. 2.-P. 109-125.

78. Ullmann J. R. An algorithm for subgraph isomorphism // Journal of the Association for Computing Machinery. 1976. - Vol. 23, No. 1. - P. 31-42.

79. Wagner R., Fischer M. The string-to-string correction problem // Journal of the Association for Computing Machinery. 1974. - Vol. 21, No. 1. - P. 168-173.

80. Zhang K. Computing similarity between RNA secondary structures // Proc. IEEE International Joint Symposia on Intelligence and Systems. 1998. - P. 126132. http://www.csd.uwo.ca/faculty/kzhang/rna/papers/rna sec sim.ps