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

Конкатена́ция (сцепле́ние) - операция склеивания объектов линейной структуры, обычно, строк. Например, конкатенация слов "паро" и "воз" даст слово "паровоз".

Содержание

В математике

Конкатенация - бинарная операция, определенная на словах данного алфавита. Если \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 = wikimedia\,, но media \cdot wiki = mediawiki\,. От перестановки операндов меняется результат операции, что и означает ее некоммутативность.
  • Пустое слово, \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}

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

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

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

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

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


Эту статью следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home