|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Алгоритм ХаффманаСледующий рекурсивный алгоритм строит схему оптимального префиксного алфавитного кодирования для заданного распределения вероятностей появления букв.
Алгоритм 6.2. Построение оптимальной схемы – рекурсивная процедура Huffman Вход: n – количество букв, P: array [1..n] of real – массив вероятностей букв, упорядоченный по убыванию. Выход: C: array [1..n,1..L] of 0..1 – массив элементарных кодов, l: array [1..n] of 1..L – массив длин элементарных кодов схемы оптимального префиксного кодирования. if n=2 then C [1, 1]:= 0; l[1]:= 1; { первый элемент } C [2, 1]:= 1; l[2]:= 1; { Второй элемент } else q:= P[n-1]+P[n] { сумма двух последних вероятностей } j:= Up (n, q) { поиск места и вставка суммы } Huffman (P, n-1) { рекурсивный вызов } Down (n, j) { достраивание кодов } End if Функция Up находит в массиве P место, в котором должно находиться число q (см. предыдущий алгоритм) и вставляет это число, сдвигая вниз остальные элементы. Вход: n – длина обрабатываемой части массива p, q – вставляемая сумма. Выход: измененный массив P.
for I from n-1 downto 2 do if P [i-1] <= q then P[i]:= P[i-1] { сдвиг элемента массива } else j:=i-1 { определение места вставляемого элемента } exit for I { все сделано – цикл не нужно продолжать } end if end for P[j]:= q; return j
Процедура Down строит оптимальный код для n букв на основе построенного оптимального кода для n-1 буквы. Для этого код буквы с номером j временно исключается из массива C путем сдвига вверх кодов букв с номерами, большими j, а затем в конец обрабатываемой части массива С добавляется пара кодов, полученных из кода буквы с номером j удлинением на 0 и 1, соответственно. Здесь C[I,*] означает вырезку из массива, то есть i-ю строку массива С. Вход: n – длина обрабатываемой части массива P, j – номер «разделяемой» буквы. Выход: оптимальные коды в первых n элементах массивов С и l.
c:= C [j, *] { запоминание кода буквы j } l:= l[j] { и длины этого кода } for i from j to n-2 do C[I,*]:=C[i+1,*] { сдвиг кода } l[i]:= l[i+1] { и его длины } end for C[n-1,*]:=c; C[n,*]:= c { копирование кода буквы j } C[n-1,l+1]:=0; C[n, l+1]:= 1 { наращивание кодов } L[n-1]:= l+1; l[n]:= l+1 { и увеличение длин }
Обоснование Для пары букв при любом распределении вероятностей оптимальное кодирование очевидно: первой букве нужно назначить код 0, а второй – 1. Именно это и делается в первой части оператора if основной процедуры Huffman. Рекурсивная часть алгоритма в точности следует доказательству теоремы предыдущего подраздела. С помощью функции Up в исходном упорядоченном массиве P отбрасываются две последние (наименьшие) вероятности, и их сумма вставляется в массив P, так чтобы массив (на единицу меньшей длины) остался упорядоченным. Заметим, что при этом место вставки сохраняется в локальной переменной j. Так происходит до тех пор, пока не останется массив их двух элементов, для которого оптимальный код известен. После этого в обратном порядке строятся оптимальные коды для трех, четырех и т. д. элементов. Заметим, что при этом массив вероятностей Р уже не нужен – нужна только последовательность номеров кодов, которые должны быть изъяты из массива кодов и продублированы в конце с добавлением разряда. А эта последовательность храниться в экземплярах локальной переменной j, соответствующих рекурсивным вызовам процедуры Huffman. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |