Однако можно построить однозначно декодируемые двоичные коды без пробела. Для этого достаточно строить код так, чтобы он удовлетворял префиксному свойству – ни одно используемое кодовое слово не должно совпадать с началом (префиксом) другого кодового слова. В рассмотренном коде это правило не выполнено. Существует несколько алгоритмов построения неравномерных кодов с префиксным свойством.
Простым является алгоритм Фено. Сообщения алфавита источника, записанные в порядке невозрастания вероятностей, разбиваются на две части с почти одинаковыми суммарными вероятностями. Сообщениям первой части приписывается первый символ 0, сообщения второй части – 1. Затем каждая из частей, содержащих более одного сообщения, вновь делится на две, по возможности равновероятные части и в качестве второго символа в первой из них берется 0, а во второй – 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не окажется по одному сообщению. Например,
А 0,4 0 А 0
Б 0,3 1 0 Б 10
В 0,1 1 1 0 0 В 1100
Г 0,08 1 1 0 1 Г 1101
Д 0,07 1 1 1 0 Д 1110
Е 0,05 1 1 1 1 Е 1111
Этот код обладает префиксным свойством. Последовательность декодируется как ААГАААЕА. Среднее число символов на одно сообщение равно 2,2 и превышает энтропию менее, чем на 2%.
Оптимальным является алгоритм Хафмена, позволяющий лучше других приблизиться к границе, определяемой энтропией. Сообщения алфавита источника, записывают в порядке невозрастания вероятностей. Затем выбирают два сообщения с наименьшими вероятностями и одному из них приписывается символ 0, а другому – 1. Выбранные сообщения объединяют в промежуточное сообщение с вероятностью, равной сумме вероятностей выбранных сообщений. Затем вновь находят два сообщения с наименьшими вероятностями и поступают так же, как на первом шаге. Процедуру повторяют до тех пор, пока не будет исчерпан весь алфавит. Например,
|
|
А 0,4 А 1
|
|
|
Б 0,3 Б 01Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.