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

Конкатена́ция (лат. 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\,$.

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

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

См. также

В Викисловаре есть статья «конкатенация»

• Перебор по словарю

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.