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

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

В математике

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

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

Если $\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}}$

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

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

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

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

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

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

См. также

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.