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

Конкатенація (лат. concatēnāre, об'єднання, з'єднання) — в загальному сенсі - функція з'єднання двох сутностей або результат такої операції^[1][2].

Конкатенація в програмуванні - послідовне з'єднання значень декількох змінних та повернення результуючого значення. Аргументами такої функції можуть бути такі сутності, як рядки або масиви, результатом - ланцюжок цих сутностей.

Приклади:

• конкатенація слів «мікро» і «світ» дасть слово «мікросвіт».
• конкатенація рядків «34» та «84» дають результат «3484».

У математиці[3]

Конкатенація — бінарна операція, визначена на словах даного алфавіту. Якщо ${\displaystyle \alpha =a_{1}\ldots a_{n}\,}$ і ${\displaystyle \beta =b_{1}\ldots b_{m}\,}$ слова в алфавіті ${\displaystyle A\,}$, то конкатенацією слів ${\displaystyle \alpha \,}$і ${\displaystyle \beta \,}$, яку позначимо в цій статті як ${\displaystyle \alpha \cdot \beta \,}$, буде слово ${\displaystyle \gamma \,}$в тому ж алфавіті ${\displaystyle A\,}$, що визначається рівністю

${\displaystyle \gamma =\alpha \cdot \beta =a_{1}\ldots a_{n}b_{1}\ldots b_{m}\,}$.

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

${\displaystyle \gamma =\alpha \cdot \beta =media\cdot wiki=mediawiki}$.

Властивості конкатенації

• Операція конкатенації асоціативна.
• Операція конкатенації некомутативна. Дійсно, ${\displaystyle wiki\cdot media=wikimedia\,}$, але ${\displaystyle media\cdot wiki=mediawiki\neq wikimedia\,}$. Від перестановки операндів змінюється результат операції, що й означає її некомутативність.
• Порожнє слово, ${\displaystyle \varepsilon \,}$, є нейтральним елементом (одиницею) операції конкатенації. Тобто, якщо ${\displaystyle \varepsilon \,}$- порожнє слово, то для будь-якого слова ${\displaystyle \alpha \,}$ виконана рівність:

${\displaystyle \varepsilon \cdot \alpha =\alpha \cdot \varepsilon =\alpha \,}$.

• Множина ${\displaystyle A^{*}\,}$ всіх слів у алфавіті утворює моноїд (так звана «вільна напівгрупа»).
• Множина ${\displaystyle A^{*}\setminus \{\varepsilon \}\,}$ всіх непустих слів у алфавіті утворює напівгрупу.
• Довжина конкатенації слів дорівнює сумі довжин операндів:

${\displaystyle |\alpha \cdot \beta |=|\alpha |+|\beta |}$.

Піднесення до степеня

Операція конкатенації слів, подібно операції множення чисел, породжує операцію піднесення до степеня. Нехай ${\displaystyle \alpha \,}$ деяке слово в алфавіті ${\displaystyle A\,}$ , а ${\displaystyle n\,}$ ціле невід'ємне число. Тоді ${\displaystyle n\,}$-м ступенем слова ${\displaystyle \alpha \,}$, що позначається ${\displaystyle \alpha ^{n}\,}$, буде слово ${\displaystyle \gamma \,}$ в тому ж алфавіті ${\displaystyle A\,}$, визначене рівністю:

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

У випадку ${\displaystyle n=0\,}$, степінь ${\displaystyle \alpha ^{0}\,}$за визначенням буде рівною порожньому слову, ${\displaystyle \varepsilon \,}$.

В інформатиці

Операція конкатенації визначається для типів даних, які мають структуру послідовності (список, чергу, масив і ряд інших). У загальному випадку, результатом конкатенації двох об'єктів ${\displaystyle A\,}$ і ${\displaystyle B\,}$ є об'єкт ${\displaystyle C=A\cdot B\,}$, отриманий почерговим додаванням всіх елементів об'єкта ${\displaystyle B\,}$, починаючи з початку, в кінець об'єкта ${\displaystyle A\,}$.

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

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

Алгоритм

Алгоритм конкатенації на прикладі двох масивів наведений нижче^[4].

Дано:

1. Масив ${\textstyle A}$ з розміром ${\textstyle N}$.
2. Масив ${\textstyle B}$ з розміром ${\textstyle M}$.
3. Масив ${\textstyle C}$ з розміром ${\textstyle M+N}$, що є результатом конкатенації масивів ${\textstyle A}$ та ${\textstyle B}$.
4. Індекс масиву ${\textstyle I}$.

Суть алгоритму:

1. Виконати копіювання масиву ${\textstyle A}$ в масив ${\textstyle C}$ для ${\textstyle I\in {1,2,...M}}$:

${\textstyle C[I]\leftarrow A[I]}$

2. Виконати копіювання масиву ${\textstyle B}$ в масив ${\textstyle C}$ для ${\textstyle I\in {1,2,...N}}$:

${\textstyle C[M+I]\leftarrow B[I]}$

3. END