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



Скачать 244.86 Kb.
страница1/2
Дата06.07.2013
Размер244.86 Kb.
ТипДиссертация
  1   2


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

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

 
 
 
Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ
 
 
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
 

 


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

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

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

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

к. т. н. Сидоров Юрий Владимирович
Ведущая организация:

Институт прикладных математических исследований
Карельского научного центра РАН, г. Петрозаводск
Защита диссертации состоится 3 ноября в 10 часов на заседании Диссертационного совета Д212.190.03 при Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, д. 33.
С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан «___»____________ 2006 г.


Ученый секретарь

диссертационного совета Поляков В. В.

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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

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

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

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

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

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

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

    2. Создана информационная система по исследованию фольклорных коллекций с теоретико-графовой формализацией текстов на языке визуального программирования 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 г. – Казань), на Х Международной конференции Ассоциации «История и компьютер» (2006 г. – Москва), на научных семинарах кафедры информатики и математического обеспечения Петрозаводского государственного университета (2000–2006 гг. – Петрозаводск). По теме диссертации опубликованы 4 статьи и 5 тезисов докладов, а также получено свидетельство об официальной регистрации информационной системы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатенте).
Содержание диссертации
Во введении обосновывается актуальность темы диссертации и её научная новизна, формулируются цели и задачи исследования, описывается структура работы и определяется её практическая значимость.
В 1 главе рассмотрены основные теоретико-графовые модели языковой структуры текстов, описанные в работах А. М. Пешковского, И. П. Севбо, Э. Ф. Скороходько, А. В. Гладкого, А. И. Новикова, А. Я. Шай-кевича и др. К таким моделям относятся лексические сети, деревья зависимостей, деревья составляющих, семантические сети и т. д. Основной особенностью данных графов является упорядоченность вершин и ребер, что соответствует последовательности появления элементов модели в тексте.

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

tgml – корневой элемент.

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

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

graph – граф, соответствующий тексту. Каждый граф задается набором вершин (node) и ребер (link), соединяющих эти вершины. У элемента graph три атрибута: id – идентификатор графа, name – название графа (например, «дерево зависимостей первого предложения»), type – тип графа и directed – индикатор, указывающий, является ли граф ориентированным.

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

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

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

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

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

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

Покупили жонам тафты; Вы белила, румяна мои

Ещё мой муж не доброй до меня, Дороги были покупленныя,

Он купил, мутил, На вини были развожены,

Коровушку купил, На бело лицо положены;

Жены лишнюю работу снарядил; Вы белила, румяна мои,

Он бы лучше пуд масла купил, Сокатитесь со бела лица долой,

Полтора пуда крупищатой муки. Скажут: едет не милой муж домой,

Я младешенька стряпейку наняла, Не в любовь везет подарок дорогой -

Стряпеюшка постряпливала, Шелковую плеть не хлыстанную,

Я по горенке похаживала, Молоду жону не биваную.

Каблучками притолачивала, Не убыток шелковая плеть купить,

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


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

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

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

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

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

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

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

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

,

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

,

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

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

,

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

.

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

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

,

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

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

.

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

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

Для того чтобы сравнить матрицы смежности графов и , вводится функционал :

,

где и – элементы матрицы и соответственно. Задача аппроксимации графов состоит в нахождении такого графа и такого соответствия , при которых достигает минимума.

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

.

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

,

где и – элементы матрицы и соответственно.

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

,

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

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

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

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

,

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

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

,

где – минимальный общий надграф графов и .

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

.

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

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

  1. .

  2. .

  3. .

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

  1. .

  2. .

  3. .

В диссертации показано, что расстояние удовлетворяет всем свойствам метрики.
В 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% песен (число вершин , а ребер ). В эту группу попали все песни на темы «свадьба» и «игра». Также сюда вошли все медленные песни, где число объектов примерно 8-10.

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

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

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

,

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

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

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

    • Максимальная степень вершины .

    • Функциональный вес вершины .

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

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

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

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

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

,

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

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

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

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

Похожие:

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

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

Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация iconДипломний проект пояснювальна записка гюік. 8080403. Пз программная реализация многоко
Тема проекту “Программная реализация многокопонентных систем в cреде браузера
Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация iconСистемный анализ корпуса текстов научного знания
Также описан алгоритм поиска в корпусе документов с помощью описанной модели. Рассматривается подход к обработке текстов авторефератов...
Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация iconUral State University Полнотекстовый поиск, clb-дерево, поисковые системы, инвертированные файлы. Рассматриваются задачи поиска в большом объеме текстов и их решение
Рассматриваются задачи поиска в большом объеме текстов и их решение с использованием ранее предложенной автором новой структуры данных...
Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация iconТемы курсовых работ по дисциплине Визуальное программирование
Проектирование иерархической структуры объектов в заданной предметной области и их программная реализация среде ооп
Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация iconПрограмма дисциплины Алгоритмы и структуры данных для поиска для направления 010400. 68 «Прикладная математика и информатика»

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


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