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

Конкатена́ция (лат. concatenatio «присоединение цепями; сцепле́ние») — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».

В математике[править]

Конкатенация — бинарная операция, определённая на словах данного алфавита. Обозначения:

$A$ — алфавит, набор букв;
$α$ , $β$ , $γ$ — слова, составленные из букв;
$a_{1} \dots a_{n}$ и $b_{1} \dots b_{m}$ — записанные подряд и пронумерованные буквы двух слов.

Если $α = a_{1} \dots a_{n}$ и $β = b_{1} \dots b_{m}$ — слова в алфавите $A$ , то конкатенацией слов $α$ и $β$ , которую обозначим в этой статье как $α \cdot β$ , будет слово $γ$ в том же алфавите $A$ , определяемое равенством

$γ = α \cdot β = a_{1} \dots a_{n} b_{1} \dots b_{m}$ .

Например, если $α = m e d i a$ и $β = w i k i$ — слова в алфавите $A = {a, b, c, \dots, z}$ , содержащем все буквы латинского алфавита, то

$γ = α \cdot β = m e d i a \cdot w i k i = m e d i a w i k i$ .

Свойства конкатенации[править]

Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: $(w i k i \cdot m e d i a) \cdot p e d i a = w i k i m e d i a p e d i a$ , и в то же время $w i k i \cdot (m e d i a \cdot p e d i a) = w i k i m e d i a p e d i a$ .
Операция конкатенации некоммутативна. В самом деле, $w i k i \cdot m e d i a = w i k i m e d i a$ , но $m e d i a \cdot w i k i = m e d i a w i k i \neq w i k i m e d i a$ . От перестановки операндов меняется результат операции, что и означает её некоммутативность.
Пустое слово — $ε$ , — является нейтральным элементом (единицей) операции конкатенации. То есть, если $ε$ — пустое слово, то для любого слова $α$ выполнено равенство:

$ε \cdot α = α \cdot ε = α$ .

Множество $A^{*}$ всех слов в алфавите образует моноид (так называемый «свободный моноид»^[англ.]).
Множество $A^{*} ∖ {ε}$ всех непустых слов в алфавите образует полугруппу.
Длина (количество букв) конкатенации слов равна сумме длин операндов:

$| α \cdot β | = | α | + | β |$ .

Итерации[править]

Операция конкатенации слов, подобно операции умножения чисел, порождает операцию итерации (или «возведения в степень»). Пусть $α$ — некоторое слово в алфавите $A$ , а $n$ — целое неотрицательное число. Тогда $n$ -ой степенью слова $α$ , обозначаемой $α^{n}$ , будет слово $γ$ в том же алфавите $A$ , определяемое равенством:

$\begin{matrix} γ = α^{n} = & \underset{⏟}{α \cdot \dots \cdot α} \\ n \end{matrix}$

(повтор слова $α$ $n$ раз). Пример: «a»³="aaa".

В случае $n = 0$ , степень $α^{0}$ по определению полагается равной пустому слову, $ε$ .

В информатике[править]

Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список, очередь, массив и ряд других). В общем случае, результатом конкатенации двух объектов $A$ и $B$ является объект $C = A \cdot B$ , полученный поочерёдным добавлением всех элементов объекта $B$ , начиная с первого, в конец объекта $A$ .

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

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

См. также[править]

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