Основные определения, связанные со строками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Отношения между строками)
Строка 1: Строка 1:
== Базовые определения ==
+
 
 +
==Базовые определения==
 +
 
 +
{{Определение
 +
|definition='''Символ''' (англ. ''Symbol'') {{---}} объект, имеющий собственное содержание и уникальную читаемую форму.
 +
}}
 +
 
 +
{{Определение
 +
|definition='''Алфавит''' (англ. ''Alphabet'') <tex>\Sigma</tex> {{---}} непустое множество символов.
 +
}}
 +
 
 +
Примеры:
 +
* <tex>\Sigma = \left\{0, 1\right\} </tex> {{---}} бинарный алфавит.
 +
* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
 +
* <tex>\Sigma = \left\{a, b, c, d, ... , z\right\} </tex> {{---}} английский алфавит.
 +
* <tex>\Sigma = \left\{0, 1, 2, ..., 9\right\} </tex> {{---}} алфавит цифр.
 +
* Нотные знаки
  
 
{{Определение
 
{{Определение
|definition =
+
|definition='''Нейтральный элемент''' {{---}} пустая строка <tex>\varepsilon</tex>: <tex>\varepsilon \in \Sigma^{0}</tex>. Для любой строки <tex>\alpha \in \Sigma^k</tex> верно: <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
'''Алфавитом''' <tex>\Sigma</tex> называется конечное непустое множество элементов, называемых символами.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition='''Замыкание Клини''' (англ. ''Kleene closure'') {{---}} унарная операция над множеством строк либо символов. Замыкание Клини множества <tex>\Sigma</tex> есть <tex>\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^n</tex>.
'''Нейтральный элемент''' (пустую строку) обозначим как <tex>\varepsilon \in \Sigma^{0}</tex>. Для любой строки <tex>\alpha</tex> верно: <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
+
}}
 +
 
 +
Если <tex>\Sigma = \left\{0, 1\right\}</tex>, то <tex>\Sigma^* = \left\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ... \right\} </tex>.
 +
 
 +
{{Определение
 +
|definition='''Цепочка''' (англ. ''Chain'') {{---}} элемент конечной длины из <tex>\Sigma^*</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition='''Конкатенация''' (англ. ''Concatenation'') {{---}} бинарная, ассоциативная, некоммутативная операция, определённая на словах данного алфавита. Конкатецния строк <tex>\alpha \in \Sigma^k</tex> и <tex>\beta \in \Sigma^m</tex> является строка <tex>\alpha\beta \in \Sigma^{k + m}</tex>.
'''Цепочкой''' (словом, строкой) конечной длины обозначим элемент из <tex>\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^n</tex>.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition='''Моноид''' (англ. ''Monoid'') {{---}} множество, на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует нейтральный элемент. <tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид
'''Конкатенацией''' строк <tex>\alpha \in \Sigma^k</tex> и <tex>\beta \in \Sigma^m</tex> является строка <tex>\alpha\beta \in \Sigma^{k+m}</tex>. Конкатенация является ассоциативной операцией.
 
 
}}
 
}}
  
<tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид. Данный моноид совпадает со свободным над <tex>\Sigma</tex>.
+
==Отношения между строками==
 +
 
 +
{{Определение
 +
|id=prefix
 +
|definition='''Префикс''' (англ. ''Prefix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \alpha \gamma</tex>.  
 +
}}
  
== Отношения между строками ==
+
Пусть <tex>\beta = \underline{abr}acadabra</tex>, тогда <tex>\alpha = abr</tex> {{---}} префикс <tex>\beta</tex>.
  
 
{{Определение
 
{{Определение
|definition =
+
|id=suffix
<tex>\alpha</tex> называется '''префиксом''' <tex>\beta</tex>, если <tex>\beta = \alpha \gamma</tex>. Аналогично определяется '''суффикс''' строки.
+
|definition='''Суффикс''' (англ. ''Suffix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \gamma \alpha </tex>.  
 
}}
 
}}
  
Пусть <tex>\beta = \underline{abr}acada\underline{bra}</tex>, тогда
+
Пусть <tex>\beta = abracada\underline{bra}</tex>, тогда <tex>\alpha = bra</tex> {{---}} суффикс <tex>\beta</tex>.
*если <tex>\alpha = abr</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>
 
*если <tex>\alpha = bra</tex>, то <tex>\alpha</tex> является суффиксом <tex>\beta</tex>.
 
  
 
{{Определение
 
{{Определение
|definition =
 
<tex>\alpha</tex> называется '''бордером''' <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом <tex>\beta</tex>.
 
 
|id=border
 
|id=border
 +
|definition='''Бордер''' (англ. ''Circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \gamma \alpha = \alpha \eta</tex>.
 
}}
 
}}
  
Пусть <tex>\beta = \underline{abra}cad\underline{abra}</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.
+
Пусть <tex>\beta = \underline{abra}cad\underline{abra}</tex>, тогда <tex>\alpha = abra</tex> {{---}} бордер <tex\beta</tex>.
  
 
{{Определение
 
{{Определение
|definition =
+
|id=period
Число <tex>p</tex> называется '''периодом''' строки <tex>\alpha</tex> (<tex>n = |\alpha|</tex>), если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
+
|definition='''Период''' (англ. ''Period'') строки <tex>\alpha</tex> {{---}} число <tex>p</tex>: <tex>\forall i = 1 \ldots |\alpha| - p \alpha [i] = \alpha[i + p]</tex>.
|id=border
 
 
}}
 
}}
  
Строка <tex>\alpha = acaacaa</tex> является периодической (<tex>p = 3</tex>).
+
Пусть <tex>\alpha = acaacaa</tex>, тогда <tex>p = 3</tex> {{---}} период строки <tex>\alpha = acaacaa</tex>.
  
 
{{Определение
 
{{Определение
|definition =
+
|id=hardperiod
Строка <tex>\alpha \neq \varepsilon</tex>, имеющая период <tex>p</tex> (<tex>p \neq |\alpha|</tex>), называется '''сильнопериодической''' с периодом <tex>p</tex>, если <tex>|\alpha| \bmod p = 0</tex>.
+
|definition=Строка <tex>\alpha \neq \varepsilon</tex> c периодом <tex>p \neq |\alpha|</tex>, называется '''сильнопериодической''', если <tex>|\alpha| \bmod p = 0</tex>.
 
}}
 
}}
  
Строка <tex>\alpha = acaacaaca</tex> является сильнопериодической (<tex>p = 3</tex>).
+
Строка <tex>\alpha = acaacaaca</tex> является сильнопериодической с периодом <tex>p = 3</tex>.
  
 
{{Определение
 
{{Определение
|definition =
+
|id=substring
Строка <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\beta = \gamma \alpha \delta</tex>.
+
|definition='''Подстрока''' (англ. ''Substring'') {{---}} некоторая непустая связная часть строки.
 
}}
 
}}
  
Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abr\underline{aca}dabra</tex>.
+
Пусть <tex>\beta = abr\underline{aca}dabra</tex>, тогда <tex>\alpha = aca</tex> {{---}} подстрока строки <tex>\beta</tex>.
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
 
Строка <tex>\alpha \le \beta</tex>, если:
 
Строка <tex>\alpha \le \beta</tex>, если:
* <tex>\alpha</tex> префикс <tex>\beta</tex>
+
* <tex>\alpha</tex> {{---}} префикс <tex>\beta</tex>
* <tex>\gamma</tex> общий префикс <tex>\alpha</tex> и <tex>\beta</tex>, <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c < d</tex>
+
* <tex>\gamma</tex> {{---}} общий префикс <tex>\alpha</tex> и <tex>\beta</tex>: <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c \le d</tex>
 
}}
 
}}
  
 
Строка <tex>\alpha = aca \le \beta = acaaba</tex>, т.к. является префиксом <tex>\beta</tex>.
 
Строка <tex>\alpha = aca \le \beta = acaaba</tex>, т.к. является префиксом <tex>\beta</tex>.
 +
Строка <tex>\alpha = acaa \le \beta = acab</tex>, т.к. <tex>a \le b</tex>.
  
Строка <tex>\alpha = acaa \le \beta = acab</tex>, т.к. <tex>a \le b</tex>.
+
== Смотри также ==
 +
[[Период и бордер, их связь]]
 +
 
 +
[[Слово Фибоначчи]]
 +
 
 +
[[Слово Туэ-Морса]]
  
 
==Литература==
 
==Литература==
 
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
 
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
 +
* Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.
 +
* Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 21:55, 9 июня 2014

Базовые определения

Определение:
Символ (англ. Symbol) — объект, имеющий собственное содержание и уникальную читаемую форму.


Определение:
Алфавит (англ. Alphabet) [math]\Sigma[/math] — непустое множество символов.


Примеры:

  • [math]\Sigma = \left\{0, 1\right\} [/math] — бинарный алфавит.
  • [math]\Sigma = \left\{\cdot, -\right\} [/math] — алфавит, лежащий в основе азбуки Морзе.
  • [math]\Sigma = \left\{a, b, c, d, ... , z\right\} [/math] — английский алфавит.
  • [math]\Sigma = \left\{0, 1, 2, ..., 9\right\} [/math] — алфавит цифр.
  • Нотные знаки


Определение:
Нейтральный элемент — пустая строка [math]\varepsilon[/math]: [math]\varepsilon \in \Sigma^{0}[/math]. Для любой строки [math]\alpha \in \Sigma^k[/math] верно: [math]\alpha\varepsilon=\varepsilon\alpha=\alpha[/math].


Определение:
Замыкание Клини (англ. Kleene closure) — унарная операция над множеством строк либо символов. Замыкание Клини множества [math]\Sigma[/math] есть [math]\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^n[/math].


Если [math]\Sigma = \left\{0, 1\right\}[/math], то [math]\Sigma^* = \left\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ... \right\} [/math].


Определение:
Цепочка (англ. Chain) — элемент конечной длины из [math]\Sigma^*[/math].


Определение:
Конкатенация (англ. Concatenation) — бинарная, ассоциативная, некоммутативная операция, определённая на словах данного алфавита. Конкатецния строк [math]\alpha \in \Sigma^k[/math] и [math]\beta \in \Sigma^m[/math] является строка [math]\alpha\beta \in \Sigma^{k + m}[/math].


Определение:
Моноид (англ. Monoid) — множество, на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует нейтральный элемент. [math]\Sigma^*[/math] с операцией конкатенации и нейтральным элементом [math]\varepsilon[/math] образуют моноид


Отношения между строками

Определение:
Префикс (англ. Prefix) строки [math]\beta[/math] — строка [math]\alpha[/math]: [math]\beta = \alpha \gamma[/math].


Пусть [math]\beta = \underline{abr}acadabra[/math], тогда [math]\alpha = abr[/math] — префикс [math]\beta[/math].


Определение:
Суффикс (англ. Suffix) строки [math]\beta[/math] — строка [math]\alpha[/math]: [math]\beta = \gamma \alpha [/math].


Пусть [math]\beta = abracada\underline{bra}[/math], тогда [math]\alpha = bra[/math] — суффикс [math]\beta[/math].


Определение:
Бордер (англ. Circumfix) строки [math]\beta[/math] — строка [math]\alpha[/math]: [math]\beta = \gamma \alpha = \alpha \eta[/math].


Пусть [math]\beta = \underline{abra}cad\underline{abra}[/math], тогда [math]\alpha = abra[/math] — бордер <tex\beta</tex>.


Определение:
Период (англ. Period) строки [math]\alpha[/math] — число [math]p[/math]: [math]\forall i = 1 \ldots |\alpha| - p \alpha [i] = \alpha[i + p][/math].


Пусть [math]\alpha = acaacaa[/math], тогда [math]p = 3[/math] — период строки [math]\alpha = acaacaa[/math].


Определение:
Строка [math]\alpha \neq \varepsilon[/math] c периодом [math]p \neq |\alpha|[/math], называется сильнопериодической, если [math]|\alpha| \bmod p = 0[/math].


Строка [math]\alpha = acaacaaca[/math] является сильнопериодической с периодом [math]p = 3[/math].


Определение:
Подстрока (англ. Substring) — некоторая непустая связная часть строки.


Пусть [math]\beta = abr\underline{aca}dabra[/math], тогда [math]\alpha = aca[/math] — подстрока строки [math]\beta[/math].


Определение:
Строка [math]\alpha \le \beta[/math], если:
  • [math]\alpha[/math] — префикс [math]\beta[/math]
  • [math]\gamma[/math] — общий префикс [math]\alpha[/math] и [math]\beta[/math]: [math]\alpha = \gamma c \delta[/math], [math]\beta = \gamma d \xi[/math] и [math]c \le d[/math]


Строка [math]\alpha = aca \le \beta = acaaba[/math], т.к. является префиксом [math]\beta[/math]. Строка [math]\alpha = acaa \le \beta = acab[/math], т.к. [math]a \le b[/math].

Смотри также

Период и бордер, их связь

Слово Фибоначчи

Слово Туэ-Морса

Литература

  • Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
  • Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.
  • Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.