ХАФФМАН В ПЛАНЕ МИНИМИЗАЦИИ ПРОГРАММЫ

Домашняя страница

	1. Знакомство с Хаффманом
	2. Оптимален ли Хаффман?
	3. Вычисление длин битовых представлений символов
	4. Битовые представления символов
	5. Расшифровка сжатого текста
	6. Пример программы в целом
	7. Листинги
	   • ВЫЧИСЛЕНИЕ ДЛИН ПРЕДСТАВЛЕНИЙ
	   • ВЫЧИСЛЕНИЕ ПРЕДСТАВЛЕНИЙ
	   • ДЕКОДИРОВЩИК
	8. Заключение

	Обычно улучшение одних характеристик программы достигается в
ущерб другим. Однако отсечение лишнего в программе, например, при
конкретных требованиях к скорости, нередко позволяет выделить
существенные части алгоритма, выявить более глубокие закономерности
и добиться улучшения программы сразу по ряду показателей.

		     1. Знакомство с Хаффманом

	Возьмем набор символов
	1111111111222222222333333334444444555555 ,
в котором находятся 10 символов "1", 9 - "2", 8 - "3", 7 - "4", 6 - "5".
Если каждый символ представляется восемью битами, например,
"1" - 00110000, "2" - 0011001 и т.д., то взятый набор потянет на 320
битов.
	Сначала Хаффман рекомендует выбрать два символа, наиболее
редких в тексте, и приписать одному бит=0, а другому - бит=1. В
последствии эти биты окажутся последними в представлении этих двух
выбранных символов. Таким образом, пока прояснилось немного:
			"1" - ...
			"2" - ...
			"3" - ...
			"4" - ... 0
			"5" - ... 1
Даже длина представлений пока не известна.
	Далее предлагается вместо пяти исходных символов работать
с четырьмя: "1" , "2", "3" и неким вспомогательным символом "Z"
(обозначение особой роли не играет), для которого суммируются количества
вхождений символов "4" и "5". Т.е. далее имеем дело с количествами:
"1" - 10, "2" - 9, "3" - 8, "Z" - 13.
	Теперь опять надо выбрать два наименее употребительных
символа (это будут "2" и "3") и также приписать им 0 и 1, а затем
собрать обобщенный символ "Y":
			"1" - ...
			"2" - ... 0
			"3" - ... 1
			"Z" - ...
Количества: "1" - 10, "Y" - 17, "Z" - 13.
	Далее "1" и "Z" образуют "X" . Осталось всего 2 символа:
"Y" и "Z". Одному присваиваем бит = 0 , другому бит = 1. 

        

		       Рис.1. Дерево Хаффмана

Возвращаясь по построенному дереву к его листочкам, собираем цепочки
битов и получаем представления:
			"1" - 11
			"2" - 00
			"3" - 01
			"4" - 100
			"5" - 101
В таком случае исходный текст переводится в 93 бита.

		      2. Оптимален ли Хаффман?

	В рассмотренном примере 320 битов ужать до 93. Но не иллюзорна
ли выгода?	
	Поскольку избранная в примере кодировка не общеупотребительна,
то к 93 битам добавится существенная нагрузка: таблица соответствия.
Формально на каждый символ потребуется:
	а) общеупотребительное представление, например, 8-битовое,
	б) количество битов в построенном представлении (для которого
потребуется еще 2 бита, чтобы охватить рассматриваемый пример),
	в) собственно новое представление.
	Итого в пассиве: 62 бита.
	Вместо столь громоздкой таблицы можно хранить само дерево,
описанное выше, например, в форме, описанной ниже (массив из пар,
отражающих слияние, в разделе 3). Тогда можно либо развернуть таблицу
перед дешифровкой, либо более длительной процедурой ползания по дереву
всякий раз по заданным битам находить на этом дереве нужный листок. Но
и это крайне объемно, не говоря уже о неоправданных потерях времени на
расшифровку, которые во многих случаях могут оказаться неприемлемыми.
	Кроме того, чтобы некая программа могла расшифровывать не только
один текст, а еще хотя бы несколько, для этого перед таблицей соответствия
надо указать длину таблицы и длину сжатого текста, а также, возможно,
некие параметры таблицы. Правда, для длинных текстов издержки на таблицу
становятся относительно малыми.
	Гораздо большие неприятности ожидают нас при анализе другого
числа: 320.
	Широко распространенное 8-битовое представление символов,
охватывающее цифры, большие м малые буквы русского и латинского
алфавита, - далеко не единственно с теоретической точки зрения.
Во многих программах в ходу уже 16-битовое представление. С другой
стороны, для представления десятичных цифр достаточно 4 битов.
А в азбуке Морзе вообще нет единой длины: наиболее употребительные
символы записываются короткими цепочками точек и тире (эквивалентно:
нулей и единиц), менее употребительные - длинными цепочками.
	Для рассмотренного примера годится стандартная 4-битовая
кодировка цифр: "0" = 0000 , "1" = 0001 , "2"= 0010 и т.д. Тогда
исходный набор потянет не на 320, а на 160 битов, и выгоды от "сжатия"
как не бывало. Впрочем, тексты только из цифр встречаются не так уж
часто. А неутешительный итог для рассмотренного примера говорит лишь
о том, что метод Хаффмана (как и любой метод сжатия информации)
не всесилен. На любой из них нетрудно подобрать пример, на котором
метод пасует. А если какой-то текст уже является результатом
хорошего сжатия, то он, как правило, становится крепким орешком для
любого метода.

	Но даже при совершенно определенной длине исходных символов,
будь то хоть 8 битов, хоть 16, никто не запрещает запустить алгоритм
Хаффмана, например, для 4-битовых частей этих символов. Это неважно, что
в исходном тексте вроде бы станет больше символов. Зато каждый из них
получит более короткое новое представление, многократно сократится
таблица соответствия и прочее. По большому счету, для запуска алгоритма
неважно, имеем ли мы дело с осмысленным текстом или даже вообще с
символами.
	Исходный текст - это просто упорядоченный набор нулей и единиц.
Его можно разбить на кусочки по 2 бита, можно по 3 и т.д. Можно один
и тот же текст разбить на элементы разной длины. И всякий раз будут
получаться, вообще говоря, существенно отличающиеся объемы сжатого
текста. Например, чтобы сжать текст, поступивший по азбуке морзе,
надо разрезать поток точек и тире на куски разной длины, соответствующие
буквам.
	Какой способ лучше - зависит от конкретного текста. И выбор
наилучшего способа - это отдельная сложная задача, которой мы здесь
не касаемся. Но полезно заметить, что формула

			ТЕКСТ + ХАФФМАН =

далеко не ведет к однозначному результату даже для объема сжатого
текста, или во всяком случае оптимум здесь реально найти лишь в
очень простых ситуациях.
	Чтобы не утонуть в описанных случаях, далее мы ограничиваемся
разбиением исходного текста только на 8-битовые кусочки. Тем не менее,
избранный способ - не просто один из равных. Если в основе ЭВМ лежит
байтовая структура, по байтам строятся адреса, значения чисел, машинные
команды и пр., то и свойства информации, удобные для ее архивации, лежат,
как правило, на уровне байтов.

	Кроме того, компактность может достигаться многими способами, а
отнюдь не только кодировкой отдельных символов. Нетрудно догадаться,
что запись
		      10(1),9(2),8(3),7(4),6(5)

отвечает тому же взятому примеру.
	Есть очень сильные методы сжатия текста, если в нем неоднократно
встречаются некоторые сочетания символов. Таковы тексты на разных языках,
файлы в базах данных, загрузочные модули. Тогда, например, вместо очередного
сочетания достаточно указать адрес (еще лучше разницу адресов) и длину
предыдущего аналогичного сочетания.
	Но есть немало случаев, когда символы перемешаны, и только на
основе их частот можно как-то ужать текст. Для этого и предназначен
алгоритм Хаффмана, который с частотами, т.е. на своем поле, справляется
блестяще.
	Вообще говоря, лучшее сжатие требует и большего времени.
И с ростом объема исходного текста это время может катастрофически
расти. Но алгоритм Хаффмана - один из немногих, кто малочувствителен к
объему текста. В зависимости от объема всего лишь логарифмически
растет длина представлений символов (да и то не всех), и время на поиск
представлений становится исчезающе малым по сравнению с затратами
на чтение-запись файлов и на прочие перемещения информации,
необходимые для любого метода.
	Наоборот, более мощные алгоритмы сжатия берутся за перебор
сочетаний, число которых растет, вообще говоря, квадратично. А способы
ускорения перебора требуют большой оперативной памяти. (При дешифровке
аналогично Хаффману нужна только таблица соответствия. Другие
знаменитые методы требуют хранения в памяти большого словаря или
длинной части расшифрованного текста.)

	Таким образом, вопрос об оптимальности сжатия методом Хаффмана,
строго говоря, некорректен, так же как, например, вопрос об оптимальности
привычной таблицы умножения. Скажем, для умножения двоичных чисел таблица
не нужна. Но алгоритм Хаффмана, как и таблица умножения, в своем роде
точен, эффективен и является выдающимся научным достижением.

	  3. Вычисление длин битовых представлений символов

	Далее для определенности ограничимся текстами до 64 КБ
и 256 символами, за каждым из которых стоит его номер от 0 до 255,
т.е. некое 8-битовое двоичное число. Более длинные тексты в принципе
можно кодировать по частям. Кроме того, как отмечалось, Хаффман не
боится больших объемов.
	По методу Хаффмана неважно, какой из двух ветвей дерева
назначить 0, а какой 1. Поэтому результат неоднозначен в смысле
конкретной кодировки. Но он однозначен (при избранном выше делении
текста на 8-битовые кусочки) в смысле объема сжатого текста. И этот
объем полностью определяется длинами представлений символов. С другой
стороны, зная длины представлений, уже нетрудно (как будет показано)
построить собственно представления. Поэтому найти длины новых
представлений символов - это решающий, ключевой шаг, после которого
не выйти на оптимальное сжатие (оптимальное по частотам) можно
только в результате грубейших ошибок.
	Таким образом, задачу можно разделить на две относительно
независимые части: а) вычисление длин представлений, б) вычисление
значений представлений символов.
	Алгоритм Хаффмана примечателен тем, что в нем нет формул
и практически нет вычислений, если даже сравнивать с другими
методами архивации, обычно напичканными сложными расчетами и тонкими
оценками. Тем не менее, если попытаться запрограммировать алгоритм
Хаффмана максимально близко к его лаконичным фразам, то возникнут проблемы,
способные поставить в тупик даже опытного специалиста. И по неизменному
дереву лазить непросто, а тут может понадобиться 255 разных состояний
дерева, причем они появляются только в процессе расчета, заранее о них
нельзя сказать почти ничего. Уже маячит мегабайтный массив и множество
перетасовок, грозящих поставить крест на быстродействии.
	Однако после отсечения лишнего оказывается, что для вычисления
длин по заданным частотам вхождения символов достаточно 1 КБ оперативной
памяти и 0.09 КБ машинного кода (на IBM PC), т.е. десятка строк на
хорошем языке программирования.
	0.5 КБ придется потратить на количества вхождений символов в
текст. (Это - для исходного текста до 64 КБ. Исходный текст в 16 МБ
потребовал бы массив для вхождений объемом 0.75 КБ и т.д.) Соответствие
символам - позиционное, т.е. номер символа = номер позиции в массиве.
А собственно для работы понадобится еще до 0.5 КБ для пар номеров символов.
Каждая пара отражает образование очередного вспомогательного символа по
двум символам с минимальной частотой.

	АЛГОРИТМ ВЫЧИСЛЕНИЯ ДЛИН.
	Этап 1: заполнение рабочего массива.
	Выбираем пару символов с наименьшими ненулевыми количествами
вхождений К1 и К2. Если таких не нашлось то переходим на этап 2.
Засылаем в рабочий массив номера выбранных символов. Затем к ячейке с К2
добавляем К1, а ячейку с К1 обнуляем. Повторяем этап 1.
	Этап 2: подсчет длин.
	Для каждого символа S делаем следующее. Полагаем рабочее значение
R=S и обнуляем однобайтовый счетчик. Если в 1-й паре из рабочего массива
есть R, то полагаем R равным 2-му числу из этой пары и увеличиваем счеткик
на 1. Переходим ко 2-й паре и т.д.
	В итоге в счетчике находится искомая длина, так как она равна
количеству слияний, в которых участвовал символ S и его последователи.
КОНЕЦ алгоритма.

	В отличие от словесного изложения здесь не понадобились
вспомогательные символы Z, Y, X, ... и соответствующие ячейки памяти.
Можно сказать, что вспомогательный символ наследует имя одного из
родителей.
	Из изложенного алгоритма нетрудно извлечь и собственно битовые
представления. Достаточно на этапе 2 отмечать, каким элементом пары
оказалось R. Если первым, то кладем 0, иначе 1, это и будет битовое
представление символа S, правда, в обратном порядке. Так что формально
алгоритм исчерпывает метод Хаффмана. К сожалению, полученные битовые
представления - это совсем не те, которые минимизируют таблицу
соответствия и, строго говоря, объем сжатого текста, если его мыслить
вместе с ключом для расшифровки. Более того, никакими простыми
поправками не удается вывести алгоритм Хаффмана на лучшее во всех
отношениях представление символов. Его проще начать строить по другому
принципу, исходя только из длин.
	Вычисляемые длины можно помещать в массив, где раньше были
количества вхождений. Так что дополнительной памяти для длин не
требуется.
	Подсчет длин на этапе 2 можно ускорить на 2 порядка путем
однократного (а не 256-кратного, как у нас) прохода рабочего массива
и одновременного заполнения 256 счетчиков. В таком случае формально
не понадобится и рабочий массив из 0.5 КБ, так как пары можно засунуть
в стек. (Правда, читать его придется нестандартным образом.) Однако
из-за незначительного объема рабочего массива общий эффект от такого
ускорения малозаметен.
	Для не формального сокращения рабочего массива, а по существу,
можно использовать тот факт, что по мере заполнения рабочего массива
с той же скоростью, наоборот, освобождается массив с количествами
вхождений. Поэтому записывать пары можно на освободившееся место.
Но тогда для каждого двубайтового слова надо ввести однобитовый
признак, который будет указывать, что хранится в слове: то ли все еще
количество, то ли уже пара, отражающая слияние. При записи очередной
пары другие (все или частично) пары придется двигать, чтобы сохранить
порядок пар. Усложнится и алгоритм в целом. Во всяком случае экономия
480 байтов памяти в несколько раз превосходит убытки от роста
загрузочного модуля. 32 байта, занятые признаками, уже можно
разместить в регистрах (например, с лихвой хватает регистров
сопроцессора, использовать который ранее не было никакой надобности).
При подсчете длин также нетрудно добиться, чтобы пара за парой
становились излишними, тогда на освободившееся место можно писать
длины, аналогично используя 256 однобитовых признаков. Поэтому налицо
вариант алгоритма, который вообще не требует рабочих массивов в
оперативной памяти (если, конечно, не считать исходных данных).

	Нетрудно видеть, что если один символ встречается в тексте
в 2 раза чаще другого символа, то первый, вообще говоря, должен
получить длину представления на один бит короче, чем длина для 2-го
символа. Если символ встречается К раз, а объем исходного текста
(число всех символов) N, то оптимальная длина представления символа
должна оказаться возле двоичного логарифма от N/К . Вопрос с длинами
представлений легко решался бы, если все значения таких логарифмов
оказались целыми. Например, если в тексте из 64 символов оказалось
16 букв А, 16 букв Б, 16 букв В, 8 букв Д, 4 буквы Е и 4 буквы Ж,
то буквы А, Б, В получили бы 2 битовые представления, Д - 3-битовое,
Е и Ж - 4-битовые.
	Плоха идея просто округлять значения логарифмов до ближайшего
целого. Может оказаться, что будут использованы не все битовые
сочетания и длина сжатого текста не станет минимальной. Но еще хуже
будет, если некоторым символам не хватит возможных сочетаний битов.
	По длинам L1, L2, ... Ln легко определить, хватит ли сочетаний.
Для каждой Li надо взять 1/2 в степени Li и просуммировать по i от 1
до n. Если сумма превысила единицу, то такой набор длин вообще не
годится. Если сумма меньше 1, то сжатие не будет оптимальным.
(Полезно заметить, что для совпадения с единицей количество символов
с максимальной длиной должно быть четно.)
	Можно округлять всякий раз в такую сторону, чтобы рабочее
значение указанной суммы оставалось меньше единицы. Тогда надо быть
готовым, что иногда придется округлять не до ближайшего целого, а
перескакивать еще на несколько единиц. Но и этот подход, как правило,
не ведет к оптимуму, хотя и дает приемлемые результаты.
	Идею округлений можно развить, организовав перебор различных
способов округлений, и в итоге добраться до предельного по Хаффману
сжатия исходного текста. Но в итоге получается громоздкий и медленный
алгоритм.
	Упомянем еще один полезный метод вычисления длин. Сначала
назначаем всем символам 8-битовые длины. Если упомянутая в предыдущем
методе сумма меньше единицы, то наиболее употребительным символам
даем 7-битовые длины, пока та же сумма остается не более 1.
Если и здесь не достигнута 1, то аналогично назначаем 6-битовые
длины и т.д. Затем перебираем все имеющиеся значения длин, начиная
с меньших. Если с длиной L есть группа по крайней мере из 3 символов,
то пробуем длину для наиболее употребительного символа из этой группы
уменьшить на единицу, а длины для двух наименее употребительных -
увеличить на единицу. Легко подсчитать, как при этом должен измениться
объем итогового текста. Если объем уменьшился, то вновь режем группу
с длинами L, иначе переходим к L+1.
	Этот алгоритм быстр, компактен (0.07 КБ машинного кода),
ему достаточен массив в 0.625 КБ (0.5 КБ на заданные количества
вхождений и 0.125 КБ на длины). Но при большом разбросе частот
(и соответственно коротких группах для каждой длины L) алгоритм
не выводит на предельное сжатие. Для такого выхода нужны более
сложные пробы, например, удлинять представления не пары символов
из группы L, а только одного символа и пары из группы L+1 и т.п.
Доводка этой идеи ведет к усложнению и замедлению алгоритма, т.е.
к утрате его преимуществ. Имеет смысл применять его именно в
упрощенном виде, когда разброс частот невелик, либо предельное
сжатие не актуально.

		  4. Битовые представления символов

	По заданным длинам представлений можно получить много
вариантов конкретных представлений символов, но среди них есть
немногие, которые минимизируют таблицу декодировки.
	В обычной двоичной записи числа каждая единичка имеет вес
согласно своей позиции. Самая младшая весит 1, следующая 2 и т.д.
В итоге само число равно сумме весов единичек в его записи.
	Аналогично можно назначить веса в кодировке по Хаффману.
Но при переходе к очередной позиции вес не обязан возрастать
вдвое, он может даже уменьшиться. 

        

	    Рис.2. Принципиальное различие таблиц весов
	   для стандартного и специального представлений

	Для примера, с которого начато данное сочинение, далее символы
пронумерованы (начиная с 0) в порядке убывания и приведены искомые
представления:
			0) "1" - 00
			1) "2" - 10
			2) "3" - 01
			3) "4" - 110
			4) "5" - 111
Крайняя левая единичка хаффмановского представления весит 1 (и это
единственно возможное значение для любых текстов и любых наборов
длин). Следующая весит 2, последняя весит 1. Нетрудно проверить, что
номер любого символа равен сумме весов в представлении этого символа.
	Отсюда сразу видно преимущество: в декодировщике не нужно
для каждого символа хранить его битовое представление. При считывании
битов сжатого текста номер символа будет непосредственно вычисляться,
и достаточно хранить только веса (не более 16 байтов, общих для всех
символов исходного текста) и 256-байтовую таблицу соответствия символов
и их внутренних номеров (образованных сограсно убыванию частот).
Правда, при расшифровке сжатого текста надо еще вовремя понять,
что номер очередного символа сформирован, но для этого, как будет
видно, дополнительной информации не требуется.
	Для сведения приведем алгоритм, который без хитростей перебором
вычисляет битовые представления. Он хорош по объему (0.04 КБ), но не
лучший по скорости, хотя и она измеряется в сотых долях секунды, и
относительная неспешность выявляется только специальными экспериментами.
Он поможет понять суть более мощного алгоритма, который будет изложен
позже. Итак, для каждого символа, встречающегося в исходном тексте,
задана длина битового представления.
	1. Полагаем рабочее двубайтовое значение R = 0.
	2. Берем символ S с минимальной длиной представления L из
тех символов, что еще не получили представление. Если такого нет,
то процесс завершен.
	3. От R в качестве представления для S берем L младших битов.
	4. Увеличиваем R на 1. Если среди обслуженных есть символ
с некой длиной M, чье представление совпадает с M младшими битами
представления S, то переходим на п.3., иначе на п.2.
	Попутно можно вычислить веса битов, если заметить, что вес
старшей единички в представлении очередного символа S равен внутреннему
номеру символа S минус веса предыдущих единичек в его представлении.
(Полезно заметить, что при формировании битового представления
символа от R откидываются только нулевые биты. Если вдруг это не
так, то длины заданы неверно, и никакой кодировки не получится.)

	Перейдем к основному алгоритму данного раздела. Как и с 
судьбоносной идеей Хаффмана, начнем со словесного описания, которое
достаточно лаконично и сразу многое проясняет.
	Пусть символы упорядочены по неубыванию длин представлений.
	Возьмем символы с максимальной длиной представлений.
Их обязательно окажется четное число. Первой половине выбранных
символов назначим в старший разряд 0, остальным 1. Этим разрядом
в итоге и будут отличаться обе половины. Поэтому про вторую из
них можно временно забыть, как и про старший, уже назначенный бит.
а первая половина естественно присоединится к группе символов с
меньшей на единицу разрядностью. В результате получаем ситуацию,
идентичную исходной, но с меньшим количеством символов и меньшей
максимальной длиной. Повторяем указанную процедуру до тех пор,
пока не останутся 2 символа. Назначаем первому бит = 0 , второму 1.
Затем возвращаемся по пройденному пути, заполняя пробелы простым
дублированием.

        

	    Рис.3. Характерные фрагменты специального
	              представления символов

	Быстрый алгоритм попутно и легко выдает таблицу весов. Вес
старшего из используемых разрядов равен половине числа символов с
максимальной длиной представлений. И далее - согласно описанным
идентичным ситуациям.

	Мы не проводим отдельного теоретического исследования
затронутых вопросов, но все необходимые инструменты здесь даны.
Так, упрощенный вариант алгоритма вычисления представлений
проясняет, как устроены специальные представления, и фактически
доказывает их единственность (если не считать, конечно, что
символы с одинаковой длиной в принципе могут поменяться своими
представлениями). Этим строением пользуется второй вариант
алгоритма. Второй вариант в свою очередь обосновывает законность
понятия весов и дает один из способов их вычисления, который
вообще может быть принят за определение понятия весов.

	Как обычно, от хорошего принципиального описания еще далеко
до программы. Поэтому сейчас приведем более детальную редакцию
того же алгоритма. В ней назначения производятся за один проход.
	Первому символу назначаем в младший разряд 0, второму 1.
Далее всякий раз имеем ситуацию: заполнено L битов для каждого из
N символов. Из этих N только K последних символов (возможно и
совпадение K=N) имеют длину представлений больше L. Назначаем
0 в L+1 -й разряд каждому из N тех же символов, и 1 следующим за
ними K символам. Матрицу значений разрядов с 1 по L -й для символов
с N-K+1 -го по N -й дублируем для аналогичных разрядов символов
с N+1 -го по N+K -й. Конец по признаку K=0.
	K - это и есть вес очередного разряда.
	Полезное следствие: символ с максимальным внутренним номером
сплошь изображается единицами.
	Поясним, что алгоритм назначает некоторым символам больше
разрядов, чем надо (и тогда они нулевые). Но это не беда, так как
длины представлений известны.
	Перейдем к окончательному варианту алгоритма. (Его объем
в кодах менее 0.05 КБ). Кроме того, что символы упорядочены по
неубыванию заданных длин представлений, еще будем предполагать,
что на месте каждого из искомых представлений уже лежат 16 нулевых
битов, т.е. массив представлений M(i) обнулен. Это позволит не делать
в общем-то излишние (но многочисленные) операции по назначению нулей
в отдельные биты.

	АЛГОРИТМ ВЫЧИСЛЕНИЯ БИТОВЫХ ПРЕДСТАВЛЕНИЙ СИМВОЛОВ
	1. Полагаем Z=2, N=2, L=1, M(2)=1.
	2. Вычисляем K - количество символов из первых N штук, чьи
представления в итоге должны быть больше L. Если K=0, то конец алгоритма.
	3. Полагаем M(i) = M(i-K)+Z для i от N+1 по N+K .
	4. Увеличиваем N на K, увеличиваем L на 1, а Z удваиваем.
Переход на п.2. КОНЕЦ алгоритма.

	Напомним, что получаемые по ходу алгоритма величины K - это
важные для последующих действий веса разрядов, их надо запасти в
некоторый массив. Памяти теперь понадобится чуть больше, чем на этапе
вычисления длин. Хотя исходные данные можно поместить в 128 байтов,
но на выходе все равно желательно иметь те же 128 байтов с длинами
и 512 байтов с представлениями символов (по 2 байта на каждый из 256
символов), чтобы без лишних хлопот закодировать исходный текст.
При этом также можно использовать массив, в котором ранее поступили
ненужные теперь количества вхождений символов. Можно побороться и
здесь за экономию памяти, но для данного сочинения это не
первоочередная задача. К тому же по сравнению с не хаффмановскими
методами, используемая память микроскопически мала.

		    5. Расшифровка сжатого текста

	Следующий алгоритм дешифровки может быть размещен в 0.04 КБ
машинного кода. Он предполагает заданными: адрес сжатого текста,
адрес вывода, адрес таблицы соответствия, адрес весов. В таблице
соответствия не более 256 байтов. С ее помощью по формируемому в
процессе расчета нашему внутреннему номеру в нужной позиции мы
найдем общепринятое 8-битовое представление символа. В таблице весов
не более 17 байтов, здесь указаны веса, начиная с младших разрядов,
таблица должна завершаться нулем. Можно сказать, что указан и вес
первого из неиспользуемых битов. (Исходный текст в 16 МБ может
увеличить таблицу весов на 8 байтов и т.д.)
	Еще, вообще говоря, нужен объем сжатого или развернутого
текста, чтобы вовремя завершить процесс. Но иногда (скажем, при
развертывании загрузочного модуля в оперативной памяти) здесь можно
немного выгадать, если, например, разместить таблицу соответствия
сразу за сжатым текстом. Тогда мы будем знать и адрес конца текста.

	АЛГОРИТМ РАСШИФРОВКИ.
	1. Установим рабочий адрес A на начало таблицы весов и
обнулим однобайтовые счетчики P и R (беззнаковые числа от 0 до 255).
	2. Читаем вес V по адресу A, увеличиваем A на 1,
читаем вес W по адресу A.
	Считываем очередной бит сжатого текста. Если он не 0, то
увеличиваем P на V. Увеличиваем R на V.
	3. Если W+P > R , то переход на п.2.
	4. P - это и есть искомый внутренний номер символа.
Выводим символ согласно таблице соответствия. Переходим на п.1
для расшифровки очередного символа. КОНЕЦ алгоритма.

	Поясним, что алгоритм не требует проверок на исчерпание
таблицы весов при подсчете внутреннего номера очередного символа.
Наоборот, для большинства символов чтение не доходит до конца этой
таблицы. Но если уж алгоритм добрался до конца таблицы, то условие
W+P > R заведомо окажется невыполненным, поскольку в этом случае
W=0, в R просуммированы все веса, а в P - только часть из них
(для символа с максимальным внутренним номером окажется P=R).
	Отсюда, в частности, следует, что сумма W+P в процессе
вычислений никогда не может превзойти 255 и даже максимального
из внутренних номеров символов (тогда для нее тоже достаточно
однобайтовой ячейки).
	Соотношение W+P > R получается из длинных теоретических
выкладок, но его можно пояснить весьма просто. Если W+P не
превосходит R, то очередная (еще не прочитанная) единичка дала бы
двойное представление символа с номером W+P , поэтому для набранного
P чтение сжатого текста необходимо прекратить. При W+P > R мы,
наоборот, узнаем о существовании символа с внутренним номером W+P ,
который не укладывается в прочитанное количество разрядов, даже если
все их заполнить единичками. В этом случае чтение надо продолжить,
так как иначе мы заведомо не охватим все символы исходного текста,
а не считанный вовремя разряд безнадежно испортит результат.

	256-байтовая таблица соответствия допускает различные сжатия
и может разворачиваться только в оперативной памяти непосредственно
перед расшифровкой сжатого текста. В первые 4 бита положим длину
битового представления того символа, который в общепринятом 8-битовом
представлении имеет номер 0. В следующие 4 бита положим длину символа
номер 1 и т.д. Таблица сожмется до 128 байтов.
	Напомним, что мы ограничились текстами до 64 КБ. Так что
четырех битов вполне достаточно для изображения всех возможных длин.
А большинство реальных случаев охватывается диапазоном длин от 5 до
12, что позволяет ужать таблицу до 96 байтов. В ряде специфических
областей достаточно еще вдвое меньшего диапазона, что доводит
результат до 64 байтов.
	Понятно, что развертывание таблицы потребует дополнительного
времени и усложнения декодировщика. Но развертывание производится
однократно и занимает незначительную часть общего времени расшифровки.
А команды развертывания умещаются в 0.04 КБ, что делает выгодной такую
добавку, даже если ее вставлять в самораспаковывающиеся файлы.
	Таблица весов тоже допускает более компактные формы. Можно
использовать тот факт, что веса младших разрядов обычно геометрическую
прогрессию, например: 1, 2, 4, 8, 6, 2. Тогда по оставшейся части
таблицы, начинающейся с последнего члена прогрессии (в данном примере
по записи 8, 6, 2) легко восстановить недостающую часть таблицы.
Однако в отличие от таблицы соответствия здесь добавка машинных кодов,
как правило, превосходит выгоду от сокращения таблицы весов. Поэтому
добавка вполне уместна в дезархиваторе, являющемся отдельной программой,
но она не годится для самораспаковывающихся программ (если, разумеется,
они не вызывают программ дешифровки извне).
	Описанные ситуации показывают, что нередко именно минимизация
машинного кода, строящаяся не только на основе абстрактной математики,
но и на основе особенностей ЭВМ, в конечном счете решает вопрос о
пригодности того или иного алгоритма.

		     6. Пример программы в целом

	Прилагается программа H.COM объемом менее 0.5 КБ , сжимающая
файлы по методу Хаффмана. Процессор: 386 и выше. Ограничение на объем
файла: 64 КБ. По исходному файлу, например, с именем NAME, она выдает
загрузочный модуль NAME.COM, который при запуске разворачивает
находящийся в нем сжатый текст и таким образом создает копию
исходного файла. Пример запуска:
				H.COM NAME
	Создастся NAME.COM . Запустите его, указав в параметрах
имя нового файла. Например:
				NAME.COM Z
	Тогда файлы NAME и Z окажутся тождественны по содержимому.

	H.COM в указанном порядке размещает в выходном файле:
	1) машинные коды (69 байтов),
	2) сжатый текст,
	3) таблицу соответствия (не более 256 байтов),
	4) таблицу весов (не более 17 байтов).
	Из машинных кодов 34 байта идет чисто на декодировщик,
остальное - на файловые операции, на начальные установки параметров и
адресов других компонентов, на прочие технические детали.
	Если выходной файл не вписывается в предельный для COM-файлов
объем, то программа выдает файл нулевого объема. А если велик исходный
файл, то H.COM берет из него первые 65535 байтов.
	Если файл не может быть сжат (таковы, например, файлы, уже
сжатые некоторым архиватором), то H.COM все равно аккуратно добавляет
ненужную здесь таблицу соответствия и прочее. В результате якобы
сжатый файл получается больше исходного. Грамотные архиваторы в таком
случае обычно помещают в начале выходного файла признак (достаточно
одного бита), указывающий, сжат файл или оставлен неизменным. Здесь
это не делается, так как ставится цель продемонстрировать метод
Хаффмана, а не сервис архиваторов.
	Хотя здесь борьба шла в первую очередь за минимизацию
программы, а не за быстродействие, но скорость отнюдь не пострадала.
(В ущерб скорости можно добиться и меньшего объема, нежели здесь
достигнут.) По сравнению с мощными архиваторами (хотя сопоставление
не совсем корректное, поскольку они вооружены многими методами и
дают лучшее сжатие) время работы H.COM в 4-6 раз меньше и для файлов
максимального объема на самых старых Pentium равно 0.06 сек. Из них
2/3 уходит на чтение и запись файлов. И только 0.01 сек. тратится
на основной расчет: вычисление длин представлений символов.

			     7. Листинги

	Следующие фрагменты на ассемблере в основном соответствуют
модулю H.COM и не слишком расходятся с описаниями алгоритмов. Дело
в том, что минимальный объем частей еще не гарантирует минимума
программы в целом, потому что части еще надо состыковать. Чтобы не
озадачивать читателя проблемами стыковки, далее приводятся, может
быть, не самые короткие, но согласованные варианты блоков.
	Кроме того, память здесь расходуется несколько расточительнее,
поскольку и так используется лишь незначительная часть ресурсов ЭВМ.
Например, вместо полукилобайтного массива для количеств вхождений символов
используется килобайтный. На каждый из 256 символов отводится 4 байта.
Первый - на сам символ, второй - под длину представления, последние
два - под количество вхождений, а позже под вычисленное преставление.
Рабочий массив тоже вдвое больше, половина его не используется, но
это позволяет немного сократить машинные коды.
	И еще: особенности ЭВМ всегда открывают поле для применения
вычислительных примемов, отнюдь не вытекающих из алгоритма.
	К началу следующих операций предполагаются, что в указанных
четверках первый байт содержит общепринятое 8-битовое представление символа,
второй равен нулю, а два последних содержат количество вхождений символа
в заданный текст. Какая-либо упорядоченность четверок не нужна. (Но в
H.COM она на самом деле имеется, хотя далее не используется: по возрастанию
номеров символов, т.е. по значениям в первых байтах четверок. Так удобнее
было подсчитывать количества вхождений.)

	ВЫЧИСЛЕНИЕ ДЛИН ПРЕДСТАВЛЕНИЙ

	Эпап 1 (52 байта):

	mov di,1024	; Адрес рабочего массива
C1:	mov cx,2	; Количество минимизируемых вхождений
C2:	mov dx,-1	; Рабочее значение вхождений
	xor si,si	; Адрес исходного массива с символами и вхождениями
M3:	lodsw		; Увеличение текущего адреса на 2
	lodsw		; ax = количество вхождений очередного символа
	or ax,ax	; Проверка количества вхождений на 0
	je M4		; Символ уже обслужен, либо его нет в тексте
	cmp ax,dx	; Сравнение текущего значения с рабочим
	jae M4		; Текущее значение не представляет интереса
	xchg ax,dx	; Корректировка рабочего значения вхождений
	lea bx,[si-4]	; Запоминание адреса кандидата на минимум
M4:	cmp si,1024	; Проверка на исчерпание исходного массива
	jne M3		; На продолжение поиска при очередном адресе
	and word ptr [bx+2],0	; Обнуление кол-ва вхожд.найденного символа
	push dx		; Запоминание мин.значения вхождений
	push bx		; Запоминание адреса символа
	loop C2		; Конец поиска двух символов с мин.вхождениями
	pop si		; Извлечение адреса 2-го символа
	movsw		; Заполнение 1-го элемента пары
	pop bx		; Извлечение количества вхождений 2-го символа
	pop si		; Извлечение адреса 1-го символа
	pop ax		; Извлечение количества вхождений 1-го символа
	add ax,bx	; Суммирование найденных минимальных значений
	movsw		; Заполнение 2-го элемента пары
	mov [si],ax	; Сумма вхождений приписана ко 2-му символу 
	inc bx		; Анализ количества вхождений 2-го символа
	jne C1		; Снова на поиск двух символов

	В отличие от описания алгоритма здесь в рабочий массив заносится
еще одна пара, которая не отвечает никакому слиянию и формируется уже
после того, как уже в общем известно, что с ненулевой частотой остался
только один символ. Это позволяет избежать излишней передачи управления
из середины на выход из описанного выше блока и, как мы увидим, сократить
последующие операции.
	За последним, не приведшим к успеху, поиском минимального
ненулевого значения все равно идет обнуление [bx+2]. Это не ошибка,
так как в bx находится не случайное число, а адрес, по которому произошло
предыдущее вполне законное обнуление. Таким образом, в конце рабочего
массива оказывается дополнительная пара, в которой оба члена совпадают
с символом, последним подвергшимся обнулению своего количества вхождений,
причем дважды. Правда, тут же  mov [si],ax  возвращает ему бессмысленное
число, находящееся в ax, но для 2-го этапа оно не играет роли.
	От 1-го этапа остаются использующиеся далее значения регистров:
cx=0, bx=0.
	Этап 2 (33 байта):

	mov ch,1	; cx=256 = количество оборотов внешнего цикла
N1:	mov bp,[bx]	; bp = рабочее значение = текущий символ
	mov dl,-1	; dl = начальное значение счетчика
	mov si,1024	; si = начало рабочего массива
N2:	lodsw		; Чтение первого члена пары
	cmp ax,bp	; Сравнение символа с 1-м членом пары
	lodsw		; Чтение второго члена пары
	je N3
	cmp ax,bp	; Сравнение символа со 2-м членом пары
	jne N4
N3:	inc dx		; Увеличение счетчика
	xchg ax,bp	; Замена раб.значения на 2-й член пары
N4:	cmp si,di	; Проверка на исчерпание рабочего массива
	jne N2		; Возврат на начало внутреннего цикла
	mov [bx+1],dl	; Занесение результата во 2-й байт четверки
	add bx,4	; увеличение текущего адреса
	loop N1		; Возврат на начало внешнего цикла

	Поскольку рабочий массив у нас на одну пару больше, то
начальное значение счетчика взято на единицу меньше. Это небольшое
усложнение позволяет попутно присвоить длину -1 всем символам,
не участвующим в тексте, и по этому признаку исключить из
последующих расчетов.
	Затем H.COM упорядочивает четверки по возрастанию беззнаковых
двубайтовых чисел из первых половин четверок. Делается это простой
перестановкой соседних четверок (а точнее, только их первых слов, что
позволяет заметно сократить машинные коды). В результате неиспользуемые
символы (если они есть) оказываются в конце массива. Именно значения -1
для длин неиспользуемых символов помогают организовать упорядочение
за 30 байтов машинного кода.

	ВЫЧИСЛЕНИЕ ПРЕДСТАВЛЕНИЙ

	Реализация алгоритма заметно отличается от его описания выше.
Здесь вообще нет отдельного первого шага, нет начального назначения
нуля и единицы первым двум символам. Этот шаг проходится наряду с
остальными в едином цикле. Объяснять это в описании алгоритма
- столь же сомнительно, как рассказывать о математической индукции
и забыть о ее первом шаге (базе индукции). Здесь использованы разные
приемы при формировании адресов и прочие манипуляции, которыми
совершенно необязательно засорять принципиальное описание алгоритма.
	К началу вычисления вторые слова упоминавшихся выше четверок
(и составляющих массив в 1 КБ с адреса 0), должны быть обнулены, а
сами четверки упорядочены по неубыванию длин представлений (об этом
тоже говорилось). После 1-го этапа вычисления длин нужные слова уже
были обнулены, все, кроме одного. Чтобы обнулить и последнее,
достаточно добавить после этапа 1 двубайтовую команду mov [si],bx
	Следующий блок (47 байтов) дополнительно к представлениям
вычисляет и таблицу весов. Она формируется с адреса -100 (достаточно
произвольного).

	xor dx,dx	; dx = количество обслуженных символов
	xor bx,bx	; bx = номер текущего разряда
BEGIN:	xor cx,cx	; cx = счетчик символов с длиной более bx
	xor si,si	; si = адрес источника для переноса
	xor di,di	; di = адрес приемника
	mov bp,dx	; bp = количество оборотов цикла
CALC:	cmp bl,[di+1]	; Сравнение номера разряда с длиной символа
	jae M1
	inc cx		; Увеличение счетчика cx
	inc dx		; Корректировка dx на будущее
	jmp M2
M1:	lodsw		; Формирование адреса источника
	lodsw
M2:	add di,4	; Формирование адреса приемника
	dec bp		; Проверка на конец цикла
	jge CALC
	mov [bx-100],cl	; Заполнение массива весов
	jcxz FIN	; Если счетчик = 0, то конец
BIT1:	lodsw		; Начало перемещений
	lodsw		; Чтение представления обслуженного символа
	bts ax,bx	; Назначение 1 в разряд bx
	inc di		; Корректировка адреса приемника
	inc di
	stosw		; Размещение нового представления
	loop BIT1	; Конец цикла перемещений
	inc bx		; Очередной разряд
	jmp BEGIN
FIN:

	Из невошедших в листинги блоков упомянем еще один расчет в H.COM,
не обязательный по сути и даже удлинняющий программу, но ускоряющий
в дальнейшем кодировку исходного текста. Он формирует массив из 512
байтов, в котором позиция каждого двубайтого слова отвечает исходному
общеупотребительному номеру символа, а на этой позиции лежит адрес
соответствующей четверки в основном массиве. В таком случае после чтения
очередного символа из исходного текста не надо лазить по всем четверкам,
проверяя в какой из них в первом байте лежит искомый символ. А сразу
извлекается нужный адрес нового битового представления символа.
	Заманчиво было бы операцией сдвига по битам через флаг переноса
CF перекидывать представления символов в выходной массив. На это идет
более короткий машинный код, но работает он заметно дольше. В H.COM
представление очередного символа (точнее, 2 байта из соответствующей
четверки) помещается в ax, старшее слово в eax обнуляется. Затем eax
сдвигается соответственно заполнению последнего байта в выходном массиве
и операцией or вписывается в массив.

	ДЕКОДИРОВЩИК

	Строго говоря, в зависимости от исходного текста всякий раз
создаются разные декодировщики, так как в них заложены разные значения
параметров. Неизменной, за исключением одного адреса, является только
описанная ниже центральная часть (34 байта). Мы не приводим остальное
обрамление, в частности, файловые операции, поскольку все это может быть
либо чуть больше, либо чуть меньше в зависимости от важности ситуации и
необходимости дополнительных проверок, а главное, не имеет прямого
отношения к архивации.
	Центральная часть предполагает заполненными следующие регистры.
	cl = 1.
	bx = адрес таблицы соответствия, находящейся непосредственно
за сжатым текстом.
	bp = адрес сжатого текста.
	di = 0 - это начальный адрес выходного массива относительно
сегмента ES.
	CS=DS=SS - это получается автоматически при запуске COM-файла.
	ES = адрес свободного сегмента.

C1:	mov si, ...	; Рабочий адрес = впаянный адрес таблицы весов
	xor dx,dx	; Обнуление счетчиков P=dl и R=dh
C2:	lodsw		; Чтение весов V=al и W=ah
	dec si		; Корректировка адреса чтения весов
	test [bp],cl	; Проверка очередного бит сжатого текста
	je M
	add dl,al	; Добавление веса V к счетчику P
M:	add dh,al	; Добавление веса V к счетчику R
	rol cl,1	; Корректировка позиции читаемого бита
	adc bp,0	; Корректировка адреса чтения сжатого текста
	add ah,dl	; Добавление P к W
	cmp ah,dh	; Сравнение W и R
	ja C2		; Номер символа не собран
	xchg ax,dx	; Номер символа собран и пишется в al
	xlat		; Замена согласно таблице соответствия
	stosb		; Запись символа в выходной массив
	cmp bp,bx	; Проверка на конец сжатого текста
	jb C1		; Возврат на расшифровку очередного символа

	Последний байт сжатого текста может оказаться неполным, и
случайное содержимое довеска может чуть увеличить значение регистра di.
Поэтому это число не годится в качестве объема создаваемого файла.
Истинное значение объема можно впаять в декодировщик при формировании
сжатого текста.

			    8. Заключение

	На этом месте должен был бы стоять список литературы. Однако,
если не считать основополагающей идеи Хаффмана, то не удалось найти
ничего, что хотя бы отдаленно напоминало изложенные здесь соображения
и могло бы быть рекомендовано в плане их развития. Зато удалось найти
ученых мужей, неспешно ползающих по раскидистому дереву в поисках
нужного листочка (то бишь символа) при расшифровке сжатого текста.
Удалось найти массу явно избыточных расчетов, затем - поток
исследований этих расчетов и т.д.
	Конечно, было бы глупо изобретать велосипед в столь давней и
бородатой тематике. Во всяком случае копание в литературе утешило автора
тем, что он далеко не одинок в своем дилетантизме. Если эрудиты сообщат
имена подлинных первопроходцев, то в последующих версиях данного
сочинения будут названы эти славные имена вместе с именами эрудитов.
	Если сочинение даже не блещет новизной, то его значение прежде
всего в том, что сделана попытка выделить непреходящие основы, вокруг
которых могут и должны строиться бесконечные обобщения метода Хаффмана.
	Допуская всевозможные надстройки, предложенные алгоритмы
претендуют на невозможность движения в обратную сторону, т.е. что
из них нельзя ничего выкинуть и что нельзя придумать более компактные
преобразования (разумеется, без существенного ущерба для результатов
и скорости кодирования).
	Так ли это на самом деле? - это вопрос к читателям. Автор
(и, возможно, наука) будет благодарен даже за всякое улучшение на 1
байт машинных кодов (особенно по части декодировщика), а уж тем
более за новые, более короткие пути, ведущие к сжатому тексту под
флагом Хаффмана.

                                                      Невесенко Н.В.
                                                  22 октября 2002 г.

                         © 2002 Suncloud.Ru