АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Cпособи опису алгоритмів
  2. Автором опыта выделен алгоритм формирования умения работать с моделями.
  3. Алгоритм sum-product
  4. Алгоритм активного слушания
  5. Алгоритм Беллмана
  6. Алгоритм ва хосиятёои он
  7. Алгоритм використання ІКТ в роботі з дошкільниками
  8. Алгоритм Витерби
  9. Алгоритм выбора антибиотиков при остром бронхите
  10. Алгоритм выбора направления предпринимательской деятельности
  11. АЛГОРИТМ ВЫПОЛНЕНИЯ
  12. Алгоритм выполнения манипуляции

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

 

Алгоритм 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.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)