Русская Википедия:Конкатенация

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

В математике

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

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

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

<math> \gamma = \alpha\cdot\beta = a_1\ldots a_n b_1 \ldots b_m</math>.

Например, если <math> \alpha = media</math> и <math> \beta = wiki</math> — слова из алфавита <math> A = \{a,b,c,\ldots,z\}</math>, содержащем все буквы латинского алфавита, то

<math> \gamma = \alpha \cdot \beta = media \cdot wiki = mediawiki </math>.

Свойства конкатенации

• Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: <math> (wiki \cdot media) \cdot pedia = wikimediapedia </math>, и в то же время <math> wiki \cdot (media \cdot pedia) = wikimediapedia </math>.
• Операция конкатенации некоммутативна. В самом деле, <math> wiki \cdot media = wikimedia</math>, но <math> media \cdot wiki = mediawiki \neq wikimedia</math>: от перестановки операндов меняется результат операции, что и означает её некоммутативность.
• Пустое слово <math> \varepsilon</math> — является нейтральным элементом (единицей) операции конкатенации. То есть, если <math> \varepsilon</math> — пустое слово, то для любого слова <math> \alpha</math> выполнено равенство:

<math> \varepsilon \cdot \alpha = \alpha \cdot \varepsilon = \alpha</math>.

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

<math> |\alpha\cdot\beta| = |\alpha| + |\beta| </math>.

Итерации

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

<math> \begin{matrix} \gamma = \alpha^n = & \underbrace{\alpha\cdot\ldots\cdot\alpha} \\ & n \end{matrix} </math>

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

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

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

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

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

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

См. также

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