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

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

Описание

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

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

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

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

Примечания

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

Литература

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

Похожие исследовательские статьи

<span class="mw-page-title-main">Рациональное число</span> число, которое можно представить обыкновенной дробью , где числитель — целое число, а знаменатель — натуральное число

Рациона́льное число́ — число, которое можно представить в виде обыкновенной дроби $\text{[math]}$ , где $\text{[math]}$ — целое число, а $\text{[math]}$ — натуральное. Пример: $\text{[math]}$ , где $\text{[math]}$ , а $\text{[math]}$ .

Кватернио́ны — система гиперкомплексных чисел, образующая векторное пространство размерностью четыре над полем вещественных чисел. Обычно обозначаются символом $\text{[math]}$ . Предложены Уильямом Гамильтоном в 1843 году.

В математике, целая часть вещественного числа $\text{[math]}$ — округление $\text{[math]}$ до ближайшего целого в меньшую сторону. Целая часть числа также называется антье, или пол. Наряду с полом существует парная функция — потолок — округление $\text{[math]}$ до ближайшего целого в большую сторону.

Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Прямо́е, или дека́ртово произведе́ние двух непустых множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств. Предполагается, что впервые «декартово» произведение двух множеств ввёл Георг Кантор.

<span class="mw-page-title-main">Преобразование Мёбиуса</span>

Преобразование Мёбиуса — дробно-линейная функция одного комплексного переменного, тождественно не равная константе:

\text{[math]}

Умноже́ние — одна из основных математических операций над двумя аргументами, которые называются множителями или сомножителями. Результат умножения называется их произведением.

Фу́нкция Гри́на — функция, используемая для решения линейных неоднородных дифференциальных уравнений с граничными условиями . Названа в честь английского математика Джорджа Грина, который первым развил соответствующую теорию в 1830-е годы.

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

Код — взаимно однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации.

<span class="mw-page-title-main">Возведение в степень</span> математическая операция

Возведе́ние в сте́пень — арифметическая операция, первоначально определяемая как результат многократного умножения числа на себя. Степень с основанием $\text{[math]}$ и натуральным показателем $\text{[math]}$ обозначается как

\text{[math]}

Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних, находятся все переменные системы.

Регуля́рный язык в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.

$\text{[math]}$ -метод Уильямса — метод факторизации чисел $\text{[math]}$ с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель $\text{[math]}$ числа $\text{[math]}$ . Аналогичен $\text{[math]}$ -методу Полларда, но использует разложение на множители числа $\text{[math]}$ . Имеет хорошие показатели производительности только в случае, когда $\text{[math]}$ легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев.

В теории кодирования, неравенство Крафта — Макмиллана даёт необходимое и достаточное условие существования разделимых и префиксных кодов, обладающих заданным набором длин кодовых слов.

<span class="mw-page-title-main">Задача о разорении игрока</span>

Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность».

Исчисление Ламбека — формальная логическая система, предложенная в 1958 году Иоахимом Ламбеком, которая предназначена для описания синтаксиса естественных языков. С математической точки зрения исчисление Ламбека является фрагментом линейной логики.

Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова $\text{[math]}$ и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова $\text{[math]}$ существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.

Симметрии в квантовой механике — преобразования пространства-времени и частиц, которые оставляют неизменными уравнения квантовой механики. Рассматриваются во многих разделах квантовой механики, которые включают релятивистскую квантовую механику, квантовую теорию поля, стандартную модель и физику конденсированного состояния. В целом, симметрия в физике, законы инвариантности и сохранения являются основополагающими ограничениями для формулирования физических теорий и моделей. На практике это мощные методы решения задач и прогнозирования того, что может случиться. Хотя законы сохранения не всегда дают конечное решение проблемы, но они формируют правильные ограничения и наметки к решению множества задач.

Теория критического состояния грунта — область механики грунта, изучающая механическое поведение насыщенных переформованных грунтов на основе концепции критического состояния.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.