Алгоритм Шеннона-Фано
Особливості одного з перших алгоритмів стиснення, який сформулювали американські вчені Шеннон і Фано. Методика побудови кодування Шеннона-Фано за допомогою дерева. Розмітка гілок кодового дерева. Відмінності між кодом Хаффмана та кодом Шеннона-Фано.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | украинский |
| Дата добавления | 07.05.2015 |
| Размер файла | 247,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алгоритм Шеннона-Фано - один з перших алгоритмів стиснення, який сформулювали американські вчені Шеннон і Фано. Даний метод стиснення має велику схожість з алгоритмом Хаффмана, який з'явився на кілька років пізніше. Алгоритм використовує коди змінної довжини: символ, який часто зустрічається, кодується кодом меншої довжини, а той що рідше зустрічається - кодом більшої довжини. Коди Шеннона-Фано префіксні, тобто ніяке кодове слово не є префіксом будь-якого іншого. Ця властивість дозволяє однозначно декодувати будь-яку послідовність кодових слів.
Кодування Шеннона-Фано (англ. Shannon-Fano coding) - алгоритм префіксного неоднорідного кодування. Відноситься до ймовірнісних методів стиснення (точніше, методів контекстного моделювання нульового порядку). Подібно алгоритму Хаффмана, алгоритм Шеннона-Фано використовує надмірність повідомлення, укладених в неоднорідному розподілі частот його символів (первинного) алфавіту, тобто замінює коди символів, які частіше використовуються, короткими двійковими послідовностями, а коди більш рідкісних символів - більш довгими двійковими послідовностями.
Алгоритм був незалежно один від одного розроблений Шенноном (публікація "Математична теорія зв'язку", 1948 рік) і, пізніше, Фано (опубліковано як технічний звіт).
Код Шеннона-Фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Їм відповідають вершини третього рівня. Якщо підмножина містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Подібним чином поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0.
Відмінності між кодм Хаффмана та кодом Шеннона-Фано:
· Алгоритм Хаффмана рухається від листків до кореня, а алгоритм Ш-Ф, використовуючи ділення, рухається від кореня до листків
· На деяких послідовностях можуть сформуватися неоптимальні коди Шеннона-Фано, тому більш ефективним вважається стиснення методом Хаффмана
алгоритм кодування шеннон фано
Размещено на Allbest.ru
...Подобные документы
Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.
курсовая работа [59,4 K], добавлен 17.04.2009Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.
контрольная работа [94,6 K], добавлен 04.05.2015Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
контрольная работа [491,4 K], добавлен 15.10.2013Вычисление количества информации, приходящейся на один символ по формуле Шеннона. Изменения информационной энтропии в текстах экономического, естественнонаучного и литературного содержания. Максимальное количество информации на знак по формуле Хартли.
лабораторная работа [28,2 K], добавлен 06.12.2013Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Бит, неопределенность, количество информации и энтропия. Формула Шеннона. Формула Хартли. Логарифмы. Количество информации, получаемой в процессе сообщения. Взаимодействие источника и приемника информации. Количество, информационная емкость ячеек памяти.
реферат [579,6 K], добавлен 17.07.2008Основні теоретичні відомості алгоритмів стиснення зображень: класи зображень та їх представлення в пам'яті, алгоритми та принципи групового кодування. Огляд та аналіз сучасних програмних засобів конвертування. Тестування, опис роботи програмного засобу.
курсовая работа [2,9 M], добавлен 15.03.2014Сучасні методи захисту текстової інформації. Порівняльний аналіз шифру Бекона з іншими відомими шифрами. Практичне використання алгоритмів кодування тексту. Написання програми "Шифр Бекона", використані компоненти для реалізації алгоритму, їх властивості.
курсовая работа [606,8 K], добавлен 28.03.2016Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа [1,7 M], добавлен 25.10.2012Розробка програмного продукту, який виконує розрахунок оптимального розподілу механізмів по роботах. Алгоритм методу мінімального елемента, побудови опорного плану транспортної задачі. Реалізація алгоритмів мовою С++. Методи побудови опорного плану.
курсовая работа [1,6 M], добавлен 07.06.2012В пам'яті машини (на дискові чи в ОЗУ) данні зберігаються в вигляді послідовності нулів та одиниць. Кожна мінімальна комірка файлу зберігає нуль або одиницю. Спосіб представлення інформації на ПК. Ідея кодування з стисненням. Алгоритм Хаффмана.
курсовая работа [55,7 K], добавлен 27.06.2008Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева.
контрольная работа [81,6 K], добавлен 14.12.2011Методика та порядок програмування алгоритмів циклічної структури із заданим числом повторень за допомогою мови програмування VAB. Алгоритм роботи з одновимірними масивами. Програмування алгоритмів із структурою вкладених циклів, обробка матриць.
курсовая работа [27,7 K], добавлен 03.04.2009Бібліотека документів, зображень, музична бібліотека та бібліотека відеозаписів. Алгоритм відкриття бібліотеки. Створення архівів файлів за допомогою спеціалізованих програм — архіваторів. Вибір методу стиснення. Видалення файлів після стиснення.
лабораторная работа [685,4 K], добавлен 13.02.2016Анализ правил выбора хода на шахматной доске К. Шеннона. Характеристика программного модуля искусственного интеллекта для игры в шахматы. Контроль времени, поиск лучшего хода в шахматных алгоритмах. Разработка программы для игры с компьютерным оппонентом.
дипломная работа [3,7 M], добавлен 07.07.2012Схема и коэффициент эффективности дискретного канала. Функции блоков, свойства канальных матриц, информационные характеристики источника сообщений и приемника. Теоремы Шеннона о критической скорости, криптографическому и помехоустойчивому кодированию.
учебное пособие [994,9 K], добавлен 06.05.2011
