19 Кодирование

Алгоритм Хаффмана:

1. Составляем таблицу формата «символ» => «частота вхождения»

2. Составляем бинарное дерево, в котором «символы» являются листами.

3. Спускаясь по построенному дереву записываем код символа к которому спускаемся (если идем к правому потомку пишем 1, если к левому пишем 0). На выходе получаем код символа.

P.S. кодировка может кодировать 1 символ количество бит меньше 8 (кодировка UTF-8/Юникод), тем самым кодируемое сообщение сжимается.

Алгоритм Шеннона-Фано:

1. Символы первичного алфавита m₁ выписывают в порядке убывания вероятностей (частоты вхождения деленная на количество всех символов).

2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

5. Заканчивается алгоритм, когда в алфавите остается только 1 символ.

Алгоритм Зива-Лемпела:

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения.

2. Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами.

3. Считать очередной символ K из кодируемого сообщения.

4. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W, иначе

5. Если фраза WK уже есть в словаре, присвоить входной фразе W значение WK и перейти к Шагу 3, иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 3.

6. Конец

P.S. хуйня полная! При переходе к следующему символу, мы записываем в словарь (если такого символа нет) текущий + следующий символ (пример: S + G = SG). При чем размерность бит зависит от размера словаря (если словарь менее 32 символов, кодировать его необходимо 5 символами 2⁵=32).

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

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

Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1, ...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключительный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.