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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Конкатенація (об'єднання) — операція склеювання об'єктів лінійної структури, зазвичай рядків. Наприклад, конкатенація слів «мікро» і «світ» дасть слово «мікросвіт».

В математиці[ред.ред. код]

Конкатенація — бінарна операція, визначена на словах даного алфавіту. Якщо \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 \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}

У випадку  n=0\, , степінь  \alpha^0\, за визначенням буде рівною порожньому слову,  \varepsilon\, .

В інформатиці[ред.ред. код]

Операція конкатенації визначається для типів даних, які мають структуру послідовності (список, чергу, масив і ряд інших). У загальному випадку, результатом конкатенації двох об'єктів A\, і B\, є об'єкт C = A\cdot B\, , отриманий почерговим додаванням всіх елементів об'єкта B\, , починаючи з початку, в кінець об'єкта A\, .

З міркувань зручності і ефективності розрізняють дві форми операції конкатенації:

  1. Модифікуюча конкатенація. Результат операції формується в лівому операнді.
  2. Немодифікуюча конкатенація. Результатом є новий об'єкт, операнди залишаються незмінними.


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.