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

Конкатенація (об'єднання) — операція склеювання об'єктів лінійної структури, зазвичай рядків. Наприклад, конкатенація слів «мікро» і «світ» дасть слово «мікросвіт».

В математиці

Конкатенація — бінарна операція, визначена на словах даного алфавіту. Якщо $\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=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\,$ .

З міркувань зручності і ефективності розрізняють дві форми операції конкатенації:

Модифікуюча конкатенація. Результат операції формується в лівому операнді.
Немодифікуюча конкатенація. Результатом є новий об'єкт, операнди залишаються незмінними.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.