Алгоритм Шеннона-Фано.

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

Алгоритм:

1) Символы алфавита сортируются в порядке убывания вероятностей их появления в сообщении.

2) Полученный список разбивается на две части таким образом, чтобы суммы вероятностей были примерно одинаковы, первая группаполучает в коде первый бит – единицу, вторая – 0. Затем каждая группа разбивается так, чтобы сумма вероятностей была примерно одинаковой.

3) И так до тех пор, пока разбиение не перестанет быть возможным.

Пример.

Алгоритм Хаффмана.

Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.

Алгоритм:

1. Символы алфавита сортируются в порядке убывания вероятностей их появления в сообщении.

2. Два символа с наименьшей вероятностью заменяются псевдо символом с вероятностью равной сумме вероятностей замененных символов. И так до тех пор пока не получиться вероятность равная 1.

3. Далее строиться кодовое дерево, по которому определяется код каждого символа.

Пример.

Не нашли, что искали? Воспользуйтесь поиском: