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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

В математике

[править | править код]

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

  •  — алфавит, набор букв;
  • , ,  — слова, составленные из букв;
  • и  — записанные подряд и пронумерованные буквы двух слов.

Если и  — слова из алфавита , то конкатенацией слов и , которую обозначим в этой статье как , будет слово из того же алфавита , определяемое равенством

.

Например, если и  — слова из алфавита , содержащем все буквы латинского алфавита, то

.

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

[править | править код]
  • Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: , и в то же время .
  • Операция конкатенации некоммутативна. В самом деле, , но : от перестановки операндов меняется результат операции, что и означает её некоммутативность.
  • Пустое слово  — является нейтральным элементом (единицей) операции конкатенации. То есть, если  — пустое слово, то для любого слова выполнено равенство:

.

.

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

(повтор слова раз). Пример: «a»3=«aaa».

В случае , степень по определению полагается равной пустому слову, .

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

[править | править код]

Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список, очередь, массив и ряд других).В общем случае, результатом конкатенации двух объектов и является объект [2], полученный поочерёдным добавлением всех элементов объекта , начиная с первого, в конец объекта .

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

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

Примечания

[править | править код]
  1. Борзенко Владимир Игоревич. Кратная конкатенация (рус.) // Школа №1553 им. В.И. Вернадского. — 2024. — С. 1.
  2. Александр Охотин. [https://users.math-cs.spbu.ru/~okhotin/teaching/tcs3_2018/okhotin_tcs3_2018_l1.pdf Формальные языки и действия над ними. Регулярные выражения. Детерминированные и недетерминированные конечные автоматы. Детерминизация недетерминированных автоматов, преобразование регулярных выражений к автоматам∗] (неопр.). — 2018. — С. 2. — 12 с. Архивировано 20 декабря 2024 года.