Теория информации

Такие коды существуют - это коды Шеннона  Фано и Хаффмана. Код Шеннона-Фано и код Хаффмана относятся к множеству оптимальных кодов. Алгоритм Шеннона-Фано ‒ один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: символы, имеющие большую вероятность появления, кодируется кодом меньшей длины, символы с малой вероятностью появления ‒ кодом большей длины. Рассмотрим каждый из алгоритмов в отдельности. Принцип построения оптимальных кодов: 1. Каждый элементарный символ должен переносить максимальное количество информации, для этого необходимо, чтобы элементарные символы (0 и 1) в закодированном тексте встречались в среднем одинаково часто. Энтропия в этом случае будет максимальной. 2. Необходимо буквам первичного алфавита, имеющим большую вероятность, присваивать более короткие кодовые слова вторичного алфавита. При равномерном распределении вероятностей символов в сообщении оптимальным будет равномерный код. При равномерном кодировании каждому символу алфавита сообщений присваивается код, состоящий из ]log2n[ двоичных значений, где n – число различных кодируемых символов, ]log2n[ – ближайшее целое, не меньшее n. Это можно сделать, например , сопоставив каждому символу число от 0 до n – 1 в двоичной системе счисления. Одним из способов оптимального кодирования является метод Шеннона-Фано.