Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Кодирование по Шеннону-Фано

Алгоритм Шеннона-Фано- один из первых алгоритмов сжатия, который впервые сформулировалиамериканские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмомХаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: частовстречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины.Коды Шеннона Фано префиксные, то есть, никакое кодовое слово не является префиксом любого другого.Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Основные сведения

Кодирование Шеннона-Фано (англ. Shannon-Fano coding) — алгоритм префиксного неоднородногокодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделированиянулевого порядка). Подобно алгоритму Хаффмана алгоритм Шеннона-Фано использует избыточностьсообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, тоесть заменяет коды более частых символов короткими двоичными последовательностями, а коды болеередких символов — более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи»,1948 год) и, позже, Фано (опубликовано как технический отчёт).

Основные этапы

Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.

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

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

Поиск по сайту: