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

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

В математике

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

• $A$ — алфавит, набор букв;
• $\alpha$, $\beta$, $\gamma$ — слова, составленные из букв;
• $a_1\dots a_n$ и $b_1\dots b_m$ — записанные подряд и пронумерованные буквы двух слов.

Если $\alpha =a_1\dots a_n$ и $\beta =b_1\dots b_m$ — слова из алфавита $A$, то конкатенацией слов $\alpha$ и $\beta$, которую обозначим в этой статье как $\alpha \cdot \beta$, будет слово $\gamma$ из того же алфавита $A$, определяемое равенством

$\gamma =\alpha \cdot \beta =a_1\dots a_n{b}_1\dots b_m$.

Например, если $\alpha =media$ и $\beta =wiki$ — слова из алфавита $A=\{a,b,c,\dots ,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\ne wikimedia$: от перестановки операндов меняется результат операции, что и означает её некоммутативность.
• Пустое слово $\epsilon$ — является нейтральным элементом (единицей) операции конкатенации. То есть, если $\epsilon$ — пустое слово, то для любого слова $\alpha$ выполнено равенство:

$\epsilon \cdot \alpha =\alpha \cdot \epsilon =\alpha$.

• Множество $A^{*}$ всех слов в алфавите образует моноид (так называемый Шаблон:Нп5).
• Множество $A^{*}\setminus \{\epsilon \}$ всех непустых слов в алфавите образует полугруппу.
• Длина (количество букв) конкатенации слов равна сумме длин операндов:

$|\alpha \cdot \beta |=|\alpha |+|\beta |$.

Итерации

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

$\begin{array}{cc}\gamma ={\alpha }^n=& \underbrace{\alpha \cdot \dots \cdot \alpha }\\ & n\end{array}$

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

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

В информатике

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

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

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

См. также

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

Примечания

Шаблон:Compu-prog-stub Шаблон:Math-stub Шаблон:Нет ссылок