Сети ЭВМ и телекоммуникации. Брейман А.Д. - 42 стр.

тый файл может состоять из записей вида [a,l,t], где a – адрес (номер позиции),
с которой начинается такая же строка длины l, что и текущая строка. Если a>0,
то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a =
0, то в поле t записаны l символов, которые до сих пор в такой последователь-
ности не встречались.
       Алгоритм сжатия заключается в постоянном поиске в уже упакованной
части данных максимальной последовательности символов, совпадающей с по-
следовательностью, начинающейся с текущей позиции. Если такая последова-
тельность (длины > 3) найдена, в результат записывается ее адрес и длина.
Иначе в результат записывается 0, длина последовательности и сама (несжатая)
последовательность.

6.3.3. Кодирование Шеннона-Фано

      Методы эффективного кодирования сообщений для передачи по дискрет-
ному каналу без помех, предложенные Шенноном и Фано, заложили основу
статистических методов сжатия данных. Код Шеннона-Фано строится следую-
щим образом: символы алфавита выписывают в таблицу в порядке убывания
вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятно-
стей в каждой из групп были максимально близки (по возможности, равны). В
кодах всех символов верхней группы первый бит устанавливается равным 0, в
нижней группы – 1. Затем каждую из групп разбивают на две подгруппы с оди-
наковыми суммами вероятностей, и процесс назначения битов кода продолжа-
ется по аналогии с первым шагом. Кодирование завершается, когда в каждой
группе останется по одному символу.
      Качество кодирования по Шеннону-Фано сильно зависит от выбора раз-
биений на подгруппы: чем больше разность сумм вероятностей подгрупп, тем
более избыточным оказывается код. Для дальнейшего уменьшения избыточно-
сти, используют кодирование крупными блоками – в качестве “символов” ис-
пользуются комбинации исходных символов сообщения, но и этот подход име-
ет те же ограничения. От указанного недостатка свободна методика кодирова-
ния Хаффмана.

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

      Алгоритм Хаффмана гарантирует однозначное построение кода с наи-
меньшим для данного распределения вероятностей средним числом символов
кода на символ сообщения. На первом шаге подсчитываются частоты всех сим-
волов в исходных данных. На втором шаге строятся новые коды (битовые по-
следовательности) для каждого символа, так, чтобы никакие две разные после-
довательности не имели общего начала, например, три последовательности 0,
10, 110. удовлетворяют этому требованию. Хаффман предложил строить дво-
ичное дерево символов, в корне которого находится наиболее частый символ,
на расстоянии 1 от корня – следующие по частоте символы, и так далее. На ос-
нове такого дерева коды для символов получаются путем выполнения простой
                                     - 42 -