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

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

Определение:

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

Определение:

Алфавит (англ. Alphabet) $\Sigma$ — непустое множество символов.

Примеры:

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

Определение:

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

Определение:

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

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

Определение:

Цепочка (англ. Chain) — элемент конечной длины из $\Sigma^*$.

Определение:

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

Определение:

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

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

Определение:

Префикс (англ. prefix) строки $\beta$ — строка $\alpha$: $\beta = \alpha \gamma$.

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

Определение:

Суффикс (англ. suffix) строки $\beta$ — строка $\alpha$: $\beta = \gamma \alpha$.

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

Определение:

Бордер (англ. circumfix) строки $\beta$ — строка $\alpha$: $\beta = \gamma \alpha = \alpha \eta$.

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

Определение:

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

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

Утверждение:

Пусть известна строка $\tau$ — период $\alpha$ и $|\alpha|$, тогда можно восстановить всю строку $\alpha$.

$\triangleright$

Из определения периода строки следует, что $\alpha[1...|\tau|] = \alpha[|\tau| + 1...2*|\tau|] = ... = \alpha[|\tau|*(k - 1) + 1...|\tau|*k]$, где $k = \lfloor\frac{|\alpha|}{|\tau|} \rfloor$. Таким образом $\alpha = \sum_{i=1}^{\lfloor\frac{|\alpha|}{|\tau|} \rfloor} \tau + \tau[1...|\alpha| mod |\tau|]$.

$\triangleleft$

Определение:

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

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

Определение:

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

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

Определение:

Строка $\alpha$ лексикографически меньше строки $\beta$ ($\alpha \lt \beta$), если 1. $\alpha$ — префикс $\beta$ или 2. $\mathcal {9} k\leqslant \min(|\alpha|, |\beta|): \alpha[k] \lt \beta[k]$ и при этом $\mathcal {8} j \lt k ~\alpha_j = \beta_j$

Строка $\alpha = aca \lt \beta = acaaba$, так как является префиксом $\beta$.

Строка $\alpha = acaa \lt \beta = acab$, так как $a \lt b$.

Смотри также

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

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

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

Литература

• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 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.