нозначного декодирования сообщений с переменной длиной кодовых слов: никакое кодовое слово не может быть началом другого кодового слова. 1 Обычно это условие называют условием Шеннона-Фано, а код, удовлетворяющий этому условию - префиксным кодом.
Каждому набору кодовых слов можно поставить в соответствие ориентированный граф (орграф), определяющий этот код. Демонстрируется построение орграфа, соответствующего заданной кодовой таблице, содержащей набор кодовых слов, не являющихся префиксным кодом. Далее демонстрируется построение графа для префиксного кода по заданной кодовой таблице. Учащиеся делают вывод об особенностях графа для префиксного кода, сравнивая два графа.
Наиболее эффективными неравномерными кодами являются префиксные коды. Математиками доказано, что самый эффективный префиксный код получается с помощью алгоритма Хаффмана. Чтобы получить код Хаффмана нужно построить орграф следующим образом:
Все символы кодируемой информации образуют вершины-листья. Каждой вершине приписывается вес, равный количеству вхождений данного символа в сжимаемое сообщение.
Среди вершин, которым приписаны веса, выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них).
Создается следующая вершина графа, из которой выходят две дуги к выбранным на предыдущем шаге вершинам; одна дуга помечается символом 0, другая - символом 1. Созданной вершине приписывается вес, равный сумме весов выбранных вершин, а веса этих двух вершин стираются.
К вершинам, которым приписаны веса, применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.
Пример кодирования заданной фразы "на дворе трава, на траве дрова" кодом Хаффмана представлен на презентации. (Приложение 1, сл
Страницы: << < 1 | 2 | 3 | 4 > >>