Сайт o сименсе

Список терминов и летературы.

ЭНЦИКЛОПЕДИЯ WiMAX ПУТЬ К 4G - В. Портной

Назад 55 Вперед

Здесь для компенсации первых двух недостатков нельзя не упомянуть про­стой и достаточно эффективный метод кодирования источника с неизвестным распределением вероятностей, известный как сжатие при помощи «стопки книг». или как сжатие сортировкой, или хешированием. Метод был разработан Рябко в 1980 году. Идея метода состоит в следующем: пусть алфавит источника со­стоит из А' символов с номерами 1,2,...,А". Кодирующий алгоритм сохраняет последовательность символов, представляющую собой некоторую перестановку символов в последовательности первичного входного алфавита. При поступлении на вход некоторого символа, имеющего в этой переставленной последовательно­сти номер 1, кодирующий алгоритм записывает код этого символа (например, монотонный префиксный код). Затем поступивший символ переставляется в на­чало последовательности и номера всех символов, стоящих перед ним. увели­чиваются на 1. Таким образом, наиболее часто встречающиеся символы будут переходить в начало списка и иметь более короткие коды, что, в свою очередь, снизит объем выходного потока при их записи в качестве символов выходного потока.

Кодирование Лемпеля-Зива использует синтаксический метод для динами­ческого источника и борется с третьей проблемой. Очевидно, что посимвольное кодирование, рассмотренное выше, не использует резервы сжатия информации. связанные с повторяемостью цепочек символов, т. е. памятью канала. Наиболее удачным алгоритмом сжатия, основанным на таком подходе, является алгоритм

Лемпеля Зива, который в разных модификациях используется, в частности, в большинстве программ-архиваторов. Основная идея алгоритма состоит в том. что цедочки символов, уже встреченные ранее, кодируются ссылкой на их «ко­ординаты» (номер первого символа и длину) в «словаре», где находится уже обработанная часть сообщения. Более детально основные идеи алгоритма ил­люстрирует рис. 2.4.

Назад 55 Вперед