ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Алгоритм Шеннона-Фано.Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов. Алгоритм: 1) Символы алфавита сортируются в порядке убывания вероятностей их появления в сообщении. 2) Полученный список разбивается на две части таким образом, чтобы суммы вероятностей были примерно одинаковы, первая группаполучает в коде первый бит – единицу, вторая – 0. Затем каждая группа разбивается так, чтобы сумма вероятностей была примерно одинаковой. 3) И так до тех пор, пока разбиение не перестанет быть возможным. Пример.
Алгоритм Хаффмана. Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины. Алгоритм: 1. Символы алфавита сортируются в порядке убывания вероятностей их появления в сообщении. 2. Два символа с наименьшей вероятностью заменяются псевдо символом с вероятностью равной сумме вероятностей замененных символов. И так до тех пор пока не получиться вероятность равная 1. 3. Далее строиться кодовое дерево, по которому определяется код каждого символа. Пример.
Не нашли, что искали? Воспользуйтесь поиском:
|