§5

§5. Графы

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

Лингвистика заимствует графы из математической теории графов, тесно связанной с теорией множеств, что отражено в предложенном К. Бержем определении графа: «Собственно говоря, граф, обозначенный символом G = (Х, Г), есть пара, которая состоит из множества Х и отображения Г» (Берж, 1962).

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

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

Дерево зависимостей

Рис.16

Подобные деревья называют также иерархическими.

В грамматике зависимостей, исследуя возможности представления структуры предложения с помощью графов, И.Б. Долинина широко пользуется как линейными (см. рис. 1 7 ) , так и иерархическими графами (Долинина, 1977). Предложение

12 345 678

A little girl is sitting at the table при линейном изображении выглядит так:

Рис.17

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

1 23 456

Одно обстоятельство причиняет американцам в последнее

789

время особое беспокойство.

Рис.18

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

.Структурные и функционально-смысловые характеристики текста интерпретировал при помощи графов Ю.А. Головенко. Использование теории графов позволяет этому ученому охватить синтагматические цепи значительной протяженности.

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

Конкатенация

Рис.19

Иррадиация

Рис.20 110

Смешанную структуру покажем на примере семантической структуры английского слова floor (см. рис. 21). Рассмотрим следующие восемь его ЛСВ: 1. Пол, 2. Дно. 3. Ровная поверхность. 4. Почва. 5. Места членов Парламента. 6. Право выступить, взять слово. 7. Минимальный уровень. 8. Этаж.

Рис.21

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

Конкатена́ция (лат. concatenatio «присоединение цепями; сцепле́ние») — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».

Содержание

[убрать]

[править]В математике

Конкатенация — бинарная операция, определённая на словах данного алфавита. Если $\alpha=a_1 \ldots a_n\,$ и $\beta=b_1\ldots b_m\,$ слова в алфавите $A\,$ , то конкатенацией слов $\alpha\,$ и $\beta\,$ , которую обозначим в этой статье как $\alpha \cdot \beta\,$ , будет слово $\gamma\,$ в том же алфавите $A\,$ , определяемое равенством

$\gamma = \alpha\cdot\beta = a_1\ldots a_n b_1 \ldots b_m\,$ .

Например, если $\alpha = media \,$ и $\beta = wiki \,$ слова в алфавите $A = \{a,b,c,\ldots,z\} \,$ , содержащем все буквы латинского алфавита, то

$\gamma = \alpha \cdot \beta = media \cdot wiki = mediawiki$ .

[править]Свойства конкатенации

Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трех слов, то от расстановки скобок результат не изменится: $(wiki \cdot media) \cdot pedia = wikimediapedia$ и в то же время $wiki \cdot (media \cdot pedia) = wikimediapedia$ .
Операция конкатенации некоммутативна. В самом деле, $wiki \cdot media = wikimedia\,$ , но $media \cdot wiki = mediawiki \neq wikimedia\,$ . От перестановки операндов меняется результат операции, что и означает её некоммутативность.
Пустое слово, $\varepsilon\,$ , является нейтральным элементом (единицей) операции конкатенации. То есть, если $\varepsilon\,$ — пустое слово, то для любого слова $\alpha\,$ выполнено равенство:

$\varepsilon \cdot \alpha = \alpha \cdot \varepsilon = \alpha\,$ .

Множество $A^*\,$ всех слов в алфавите образует моноид (так называемая «свободная полугруппа»).
Множество $A^*\setminus \{\varepsilon\}\,$ всех непустых слов в алфавите образует полугруппу.
Длина конкатенации слов равна сумме длин операндов:

$|\alpha\cdot\beta| = |\alpha| + |\beta|$ .

[править]Возведение в степень

Операция конкатенации слов, подобно операции умножения чисел, порождает операцию возведения в степень. Пусть $\alpha\,$ некоторое слово в алфавите $A\,$ , а $n\,$ целое неотрицательное число. Тогда $n\,$ -ой степенью слова $\alpha\,$ , обозначаемой $\alpha^n\,$ , будет слово $\gamma\,$ в том же алфавите $A\,$ , определяемое равенством:

$\begin{matrix} \gamma = \alpha^n = & \underbrace{\alpha\cdot\ldots\cdot\alpha} \\ & n \end{matrix}$

В случае $n=0\,$ , степень $\alpha^0\,$ по определению полагается равной пустому слову, $\varepsilon\,$ .

[править]В информатике

Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список,очередь, массив и ряд других). В общем случае, результатом конкатенации двух объектов $A\,$ и $B\,$ является объект $C = A\cdot B\,$ , полученный поочерёдным добавлением всех элементов объекта $B\,$ , начиная с первого, в конец объекта $A\,$ .

Из соображений удобства и эффективности различают две формы операции конкатенации:

Модифицирующая конкатенация. Результат операции формируется в левом операнде.
Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.