Алфавитное кодирование

Алфавитное кодирование — вид кодирования, построенный на взаимной однозначности кодирования слов некоторого алфавита при помощи замены каждой буквы некоторым словом того же или какого-либо другого алфавита^[1]. Основоположником этого направления в России считается математик из Нижнего Новгорода Александр Александрович Марков^[2]. При алфавитном кодировании количество элементарных кодов должно быть равно мощности алфавита сообщений, то есть должно быть фиксированным. В алфавитном кодировании преимущественно используются префиксные коды, так как свойство префикса гарантирует однозначную декодируемость^[3].

Описание

Пусть существует некий алфавит (множество) ${\displaystyle \alpha =\left\{a_{1},a_{2},...,a_{r}\right\}}$, а также алфавит ${\displaystyle \mathrm {B} =\left\{b_{1},b_{2},...,b_{q}\right\}}$.

Слово в алфавите — упорядоченный набор элементов из алфавита вида: ${\displaystyle A=\left\{a_{i_{1}},a_{i_{2}},...,a_{i_{n}}\right\}}$

S(ℳ) — множество слов алфавита ℳ, S(β) — множество слов алфавита β

Суть алфавитного кодирования в том, что каждой букве алфавита ℳ сопоставляется слово из алфавита β согласно схеме кодирования Σ. ${\displaystyle \Sigma \quad -\quad {\begin{matrix}a_{1}\to B_{1}\\\\a_{2}\to B_{2}\\...\\a_{r}\to B_{r}\end{matrix}}}$

Примечания

1. Марков А. А. Об алфавитном кодировании : [арх. 29 января 2023] // Доклад ы Академии наук СССР. — 1960. — Т. 132, № 3. — С. 521–523.
2. Дергач П. С. Алфавитное кодирование регулярных языков с полиномиальной функцией роста : [арх. 29 января 2023] // Московский государственный университет им. М.В.Ломоносова. Диссертация на соискание ученой степени кандидата физико-математических наук. — 2016.
3. Корабельщикова С.Ю., Мельников Б.Ф. Максимальные префиксные коды и подклассы класса контекстно-свободных языков // Arctic Environmental Research. — 2015. — С. 121—129. — УДК 519.713.

Литература

• Яблонский. Введение в дискретную математику ISBN 978-5-06-005943-4; 2008 г.
• Марков А. А. Вопросы взаимной однозначности и сложности в алфавитном кодировании : Автореф. дис. … д-ра физ.-мат. наук. — М., 1983. — 17 с.
• Марков А. А. Кодирование алфавитное // Математическая энциклопедия. — М.: Советская энциклопедия, 1979. — Т. 2. — С. 935—937.