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

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

В математиці

Конкатенація - бінарна операція, визначена на словах даного алфавіту. Якщо $\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. Немодифікуюча конкатенація. Результатом є новий об'єкт, операнди залишаються незмінними.