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

Конкатена́ция (лат. 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. Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.

См. также

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