Конкатенация
Конкатена́ция (лат. concatenatio «присоединение цепями; сцепле́ние») — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».
В математике
Конкатенация — бинарная операция, определённая на словах данного алфавита. Обозначения:
- [math]\displaystyle{ A }[/math] — алфавит, набор букв;
- [math]\displaystyle{ \alpha }[/math], [math]\displaystyle{ \beta }[/math], [math]\displaystyle{ \gamma }[/math] — слова, составленные из букв;
- [math]\displaystyle{ a_1 \ldots a_n }[/math] и [math]\displaystyle{ b_1 \ldots b_m }[/math] — записанные подряд и пронумерованные буквы двух слов.
Если [math]\displaystyle{ \alpha=a_1 \ldots a_n }[/math] и [math]\displaystyle{ \beta=b_1\ldots b_m }[/math] — слова в алфавите [math]\displaystyle{ A }[/math], то конкатенацией слов [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math], которую обозначим в этой статье как [math]\displaystyle{ \alpha \cdot \beta }[/math], будет слово [math]\displaystyle{ \gamma }[/math] в том же алфавите [math]\displaystyle{ A }[/math], определяемое равенством
[math]\displaystyle{ \gamma = \alpha\cdot\beta = a_1\ldots a_n b_1 \ldots b_m }[/math].
Например, если [math]\displaystyle{ \alpha = media }[/math] и [math]\displaystyle{ \beta = wiki }[/math] — слова в алфавите [math]\displaystyle{ A = \{a,b,c,\ldots,z\} }[/math], содержащем все буквы латинского алфавита, то
[math]\displaystyle{ \gamma = \alpha \cdot \beta = media \cdot wiki = mediawiki }[/math].
Свойства конкатенации
- Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: [math]\displaystyle{ (wiki \cdot media) \cdot pedia = wikimediapedia }[/math], и в то же время [math]\displaystyle{ wiki \cdot (media \cdot pedia) = wikimediapedia }[/math].
- Операция конкатенации некоммутативна. В самом деле, [math]\displaystyle{ wiki \cdot media = wikimedia }[/math], но [math]\displaystyle{ media \cdot wiki = mediawiki \neq wikimedia }[/math]. От перестановки операндов меняется результат операции, что и означает её некоммутативность.
- Пустое слово — [math]\displaystyle{ \varepsilon }[/math], — является нейтральным элементом (единицей) операции конкатенации. То есть, если [math]\displaystyle{ \varepsilon }[/math] — пустое слово, то для любого слова [math]\displaystyle{ \alpha }[/math] выполнено равенство:
[math]\displaystyle{ \varepsilon \cdot \alpha = \alpha \cdot \varepsilon = \alpha }[/math].
- Множество [math]\displaystyle{ A^* }[/math] всех слов в алфавите образует моноид (так называемый «свободный моноид» ).
- Множество [math]\displaystyle{ A^*\setminus \{\varepsilon\} }[/math] всех непустых слов в алфавите образует полугруппу.
- Длина (количество букв) конкатенации слов равна сумме длин операндов:
[math]\displaystyle{ |\alpha\cdot\beta| = |\alpha| + |\beta| }[/math].
Итерации
Операция конкатенации слов, подобно операции умножения чисел, порождает операцию итерации (или «возведения в степень»). Пусть [math]\displaystyle{ \alpha }[/math] — некоторое слово в алфавите [math]\displaystyle{ A }[/math], а [math]\displaystyle{ n }[/math] — целое неотрицательное число. Тогда [math]\displaystyle{ n }[/math]-ой степенью слова [math]\displaystyle{ \alpha }[/math], обозначаемой [math]\displaystyle{ \alpha^n }[/math], будет слово [math]\displaystyle{ \gamma }[/math] в том же алфавите [math]\displaystyle{ A }[/math], определяемое равенством:
[math]\displaystyle{ \begin{matrix} \gamma = \alpha^n = & \underbrace{\alpha\cdot\ldots\cdot\alpha} \\ & n \end{matrix} }[/math]
(повтор слова [math]\displaystyle{ \alpha }[/math] [math]\displaystyle{ n }[/math] раз). Пример: «a»3="aaa".
В случае [math]\displaystyle{ n=0 }[/math], степень [math]\displaystyle{ \alpha^0 }[/math] по определению полагается равной пустому слову, [math]\displaystyle{ \varepsilon }[/math].
В информатике
Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список, очередь, массив и ряд других). В общем случае, результатом конкатенации двух объектов [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] является объект [math]\displaystyle{ C = A\cdot B }[/math], полученный поочерёдным добавлением всех элементов объекта [math]\displaystyle{ B }[/math], начиная с первого, в конец объекта [math]\displaystyle{ A }[/math].
Из соображений удобства и эффективности различают две формы операции конкатенации:
- Модифицирующая конкатенация. Результат операции формируется в левом операнде.
- Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.
См. также
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |