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

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

У математиці

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

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

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