Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Кодирование.
Для практики важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, то есть S=A*. Если больше про множество S ничего не известно, то точно сформулировать задачу оптимизации затруднительно. Однако на практике часто доступна дополнительная информация. Например, для текстов естественных языках известно распределение вероятности появления буквы в сообщении. Использование такой информации позволяет строго поставить и решить задачу построения оптимального алфавитного кодирования.
Минимальная длина кода сообщения.
Если задана разделимая схема алфавитного кодирования , то любая схема , где является перестановкой , так же будет разделимой. Если длины элементарных кодов равны, то перестановка элементарных кодов в схеме не влияет длину кода сообщения. Но если длины элементарных кодов различны , то длина кода сообщений зависит от состава букв в сообщении и от того, какие элементарным коды каким буквам назначены. Если заданы конкретное сообщение и конкретная схема кодирования, то нетрудно подобрать такую перестановку элементарных кодов, при которой длина кода сообщения минимальна.
Пусть в сообщение S, а - длины элементарных кодов соответственно. Тогда, если и , то . Действительно, пусть и , , где a,b. Тогда
(
Отсюда вытекает алгоритм назначения элементарных кодов, при котором длина кода конкретного сообщения S будет минимальна: нужно отсортировать буквы в порядке убывания количества вхождений, элементарные коды отсортировать в порядке возрастания длины и назначить коды буквам в порядке.
Замечание
Это простой метод решает задачу минимизации длины кода только для фиксированного сообщения Sи фиксированной схемы
Цена кодирования.
Пусть задан алфавит A={} и вероятности появления букв в сообщении P= (- вероятность появления буквы . Не ограничивая общности, можно считать, что и (то есть можно сразу исключить буквы, которые не могут появится в сообщении, и упорядочить буквы по убыванию вероятности их появления).
Для каждой (разделимой) схемы алфавитного кодирования математическое ожидание коэффициента увеличения длины сообщения при кодировании (обозначается определяется следующим образом:
, где
И называется средней ценой (или длиной) кодирования σ при распределении вероятностей P.
Пример
Для разделимой схемы A={a,b}, B={0,1}, δ={ при распределении вероятностей <0.5, 0.5> цена кодирования составляет 0.5*1+0.5*2=1.5, а при распределении вероятностей <0,9, 0,1> она равна 0.9*1+0.1*2=1.1
Обозначим
Очевидно, что всегда существует разделимая схема , такая что Такая схема называется схемой равномерного кодирования. Следовательно, 1 и достаточно учитывать только такие схемы, для которых , где – целое и . Таким образом, имеется лишь конечное число схем σ, для которых . Следовательно, существует схема , на котором инфимум достигается:
Алфавитное (разделимое) кодирование , для которого : называется кодированием с минимальной избыточностью, или оптимальным кодированием, для распределения вероятностей P.
Алгоритм Фано
Следующий рекурсивный алгоритм строит разделимую префиксную схему алфавитного кодирования, близкого к оптимальному.
Алгоритм
Вход: Р : array[1..n] of real –массив вероятностей появления букв в сообщении, упорядоченный по невозрастанию; 1
Выход: С : array[1..n, 1..L] of 0..1 –массив элементарных кодов.
Fano(1,n,0) {вызов рекурсивной процедуры Fano}
Основная работа по построению элементарных кодов выполняется следующей рекурсивной процедурой Fano.
Вход: b-индекс начала обрабатываемой части массива P, e – индекс конца обрабатываемой части массива P, k-длина уже построенных кодов в обрабатываемой части массива С.
Выход: заполненный массив С.
If e>b then
K:=k+1 {место для очередного разряда в коде}
m:=Med(b,e) {деление массива на две части}
for I from b to e do
C[i,k]:=i>m {в первой части добавляем 0, во второй -1}
end for
Fano(b,m,k) {обработка первой части}
Fano(m+1,e,k) {обработка второй части}
end if
Функция Med находи медиану указанной части массива P[b..e], то есть определяет такой индекс m(bm<e), что сумма элементов P[b..m] Наиболее близка к сумме элементов P[m+1..e].
Вход: b- индекс начала обрабатываемой части массива P, е –индекс конца обрабатываемой части массива Р.
Выход: m- индекс медианы, то есть
{сумма элементов первой части}
for I from b to e-1 do
{вначале все, кроме последнего}
end for
{сумма элементов второй части}
m:=e {начинаем искать медиану с конца}
repeat
d:={разность сумм первой и второй части}
m:=m-1 {сдвигаем границу медианы вниз}
until |d
return m