Кодирование по методу Хаффмана

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

РАЗДЕЛ 1 ОБЗОР СУЩЕСТВУЮЩИХ ПРОГРАММ СЖАТИЯ ДАННЫХ БЕЗ ПОТЕРЬ

1.1 Основа всех методов сжатия без потерь

1.2 Методы сжатия

1.2.1 Алгоритмы группы KWE

1.2.2 Lossless JPEG

1.2.3Кодирование по методу Хаффмана

РАЗДЕЛ 2 РАЗРАБОТКА ПРОГРАММЫ

2.1 Обзор составляющих компонентов

2.2 Разработка кода программы

ВЫВОДЫ

СПИСОК ИСПОЛЬЗОВАНОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

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

Сжатие -- это процесс перекодирования информации, в результате которого уменьшается объем файла. Сжатие бывает без потерь («lossless compression») и с потерями («lossy compression»). В случае сжатия данных без потерь, восстановление файла из архива происходит без изменения качества первоначального файла, во втором -- с небольшими потерями качества. Самым простым видом сжатия без потерь является метод под названием «running», подсчитывающий количество последовательных, «идущих друг за другом» повторов. Но этот метод уже недостаточен в случае наличия повторов, встречающихся в разных местах текста.

Развитие программ - архиваторов позволило добиться не только сжатия без потерь, но также возможности создания многотомных архивов и архивов в различных форматах. Архивы бывают сложной структуры, то есть многотомными. Кроме того, они бывают самораспаковывающимися, то есть процесс извлечения файла в данном случае происходит автоматически. Самораспаковывающиеся архивы имеют, как правило, расширение.exe и называются SFX-архивами (от слова «self-extracting»). Архивы также бывают «непрерывными» («solid»). Непрерывный архив -- это архив в формате RAR, упакованный таким образом, что все его файлы представляют непрерывный поток информации. Непрерывная архивация применяется только для формата RAR, для ZIP она недоступна. Плюсом непрерывной архивации является увеличение такого параметра компрессии как степень сжатия, минусом является увеличение параметра скорости расжатия, то есть непрерывный архив будет распаковываться гораздо медленнее. Кроме того, процессы добавления в исходный архив файла или наоборот удаления имеющегося файла будут также происходить медленнее.

Наиболее распространенные программы: WinRAR, WinZIP, 7-ZIP.

WinRAR - данный формат сжатия был разработан нашим соотечественником Евгением Рошалом, соответственно название формата является аббревиатурой, включающей первую букву фамилии разработчика и первые две буквы термина архиватор. Формат RAR имеет большую историю: он изначально разрабатывался под DOS, а затем и для других операционных систем, включая позже Microsoft Windows. Так появилась программа WinRAR -- функциональный, многоформатный архиватор.

WinZIP. Архиватор WinZIP был создан в 1990 году для платформы Windows компанией Nico Mak Computing, которая позже стала называться WinZip Computing. Данная программа-архиватор работает в основном по алгоритму сжатия PKZIP.

7-ZIP. Архиватор WinZIP был создан в 1990 году для платформы Windows компанией Nico Mak Computing, которая позже стала называться WinZip Computing. Данная программа-архиватор работает в основном по алгоритму сжатия PKZIP.

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

В работе необходимо провести анализ нескольких существующих программ сжатия данных без потерь. Подробно рассмотреть и реализовать алгоритм Хаффмена. Создать программу-архиватор, работающую на основе алгоритма Хаффмена.

сжатие алгоритм хаффман архиватор

РАЗДЕЛ 1 ОБЗОР СУЩЕСТВУЮЩИХ ПРОГРАММ СЖАТИЯ ДАННЫХ БЕЗ ПОТЕРЬ

1.1 Основа всех методов сжатия

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент s_h вероятность появления которого равняется p(s,), выгоднее всего представлять -1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получается равным -log₂ p(s,) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей F= {pis,} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное.

Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.

Ни один компрессор не может сжать любой файл. После обработки любым компрессором размер части файлов уменьшится, а оставшейся части -увеличится или останется неизменным. Данный факт можно доказать исходя из неравномерности кодирования, т. е. разной длины используемых кодов, но наиболее прост для понимания следующий комбинаторный аргумент.

Существует 2^л различных файлов длины п бит, где л = 0, 1, 2,... Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2^л исходным файлам будет соответствовать самое большее 2^л-1 различающихся сжатых файлов. Тогда, по крайней мере, одному архивному файлу будет соответствовать несколько различающихся исходных, и, следовательно, его декодирование без потерь информации невозможно в принципе.

1.2 Методы сжатия

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

В настоящее время существует очень много алгоритмов сжатия данных без потерь. Наиболее распространенными являются такие, как: Lossless JPEG, алгоритм Хаффмена, алгоритмы группы KWE:

- алгоритм LZ (Лемпеля-Зива);

- алгоритм LZW (Лемпеля-Зива-Велча);

1.2.1 Алгоритмы группы KWE.

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зива (алгоритм LZ) и его модификация алгоритм Лемпеля-Зива-Велча (алгоритм LZW).Для алгоритма LZ основан на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. Когда происходит считывание очередного символа входной последовательности данных, то он прибавляется к текущей строке. Это будет продолжаться до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк, а новая фраза, состоящая из совпадающего индекса и следующего за ним символа - записывается в словарь. Если эта фраза появляется еще раз, то она может быть использована для построения более длинной фразы. Это способствует повышению сжатия информации.

Семейство LZ-подобных алгоритмов могут различаться, например, методом поиска повторяющихся цепочек. В таблице1 приведены примеры LZ- алгоритмов.

Таблица1 Основные LZ-алгоритмы

Имя	Авторы	Год	Отличия
LZ77	Ziv and Lempel	1977	Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZR	Roden et al.	1981	Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSS	Bell	1986	Указатели и символы различаются флажком- битом. Указатели адресуют подстроку среди предыдущих N символов.
LZB	Bell	1987	Аналогично LZSS, но для указателей применяется разное кодирование.
LZH	Brent	1987	Аналогично LZSS, но на втором шаге для указателей применяется кодирование Хаффмана.
LZ78	Ziv and Lempel	1978	Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZW	Welch	1984	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZC	Thomas et al.	1985	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZT	Tischer	1987	Аналогично LZC, но фразы помещаются в LRU- список.
LZMW	Miller and Wegman	1984	Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJ	Jakobsson	1985	Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFG	Fiala and Greene	1989	Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

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

Алгоритм сжатия выглядит следующим образом:

- инициализация таблицы из 256 символов ASCII;

- инициализация текущей строки пустой строкой;

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

- если в таблице содержится комбинации «текущая строка+символ (под "+" имеется в виду конкатенация строк)», то выполняется проверка на наличие в таблице более крупной цепочки, начинающаяся с данной, поэтому присоединяем символ к строке;

- иначе (если текущая строка+символ не содержится в таблице, но текущая строка при этом таблице);

- получаем код текущей строки в таблице;

- выводим код в выходной файл;

- добавляем комбинацию текущая строка+символ в таблицу;

- текущая строка теперь - последний считанный из потока символ (все, что было считано до него, уже выведено в выходной файл);

- после выхода из цикла текущая строка не пуста, ее код тоже нужно вывести в выходной файл;

- выводим код в выходной файл.

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

Функция InitTable() очищает таблицу и помещает в нее все строки единичной длины.

Пример InitTable() - функции:

InitTable();

CompressedFile.WriteCode(СlearCode);

CurStr=пустая строка;

while(не ImageFile.EOF()){ //Пока не конец файла

C=ImageFile.ReadNextByte();

if(CurStr+C есть в таблице)

CurStr=CurStr+С;//Приклеить символ к строке

else {

code=CodeForString(CurStr);//code-не байт!

CompressedFile.WriteCode(code);

AddStringToTable (CurStr+С);

CurStr=С; // Строка из одного символа

}

}

code=CodeForString(CurStr);

CompressedFile.WriteCode(code);

CompressedFile.WriteCode(CodeEndOfInformation);

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

Пример алгоритма декомпрессии:

code=File.ReadCode();

while(code != СodeEndOfInformation){

if(code = СlearСode) {

InitTable();

code=File.ReadCode();

if(code = СodeEndOfInformation)

{закончить работу};

ImageFile.WriteString(StrFromTable(code));

old_code=code;

}

else {

if(InTable(code)) {

ImageFile.WriteString(FromTable(code));

AddStringToTable(StrFromTable(old_code)+

FirstChar(StrFromTable(code)));

old_code=code;

}

else {

OutString= StrFromTable(old_code)+

FirstChar(StrFromTable(old_code));

ImageFile.WriteString(OutString);

AddStringToTable(OutString);

old_code=code;

}

}

}

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

1.2.2 Lossless JPEG

Этот алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений.

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

1.2.3 Кодирование по методу Хаффмана

Алгоритм основан на том, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие - реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов - длинные, то суммарный объем файла уменьшится. В результате получается систематизация данных в виде дерева («двоичное дерево»).

Пусть сообщение M составлено из символов алфавита C. Эти символы могут быть представлены кодами некоторой фиксированной длины (для определенности 8 бит). Допустим, числа повторений символов A, B, C и D (Na, Nb, Nc и Nd соответственно) удовлетворяют неравенству

Na>Nc+Nd

Число повторений символа B произвольно. Назначим этим символам следующие коды:

A: 00000000

B: 00000001

C: 00000010

D: 00000011

Оставшиеся 252 кода произвольно распределим между оставшимися символами алфавита. Далее сделаем следующую замену кодов:

A: 0000000

B: 00000010

C: 000000110

D: 000000111

В результате получим экономию в Na-(Nc+Nd) бит.

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

РАЗДЕЛ 2 РАЗРАБОТКА ПРОГРАММЫ

2.1 Обзор составляющих компонентов

Сжатие Хаффмана - это статистический метод сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана может быть построен по следующему алгоритму:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов; в результате мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;

3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 0, налево - 1).

Рис. 2.1. Расположение элементов на форме

Для решения построения алгоритма, в своей задаче я использовал массив. На рис 2.1 видно расположение всех элементов окна. В поле Edit1 мы вводим сообщении, которое необходимо закодировать. В поле Edit2 отображается длина всего массива т.е индекс массива - это объединение двух символов с наименьшими вероятностями. Также индекс - это каждый узел дерева. В поле Memo1 отображается количество каждого символа вхождений в сообщение, Memo2 - отображается индекс нового узла (ячейки) массива и из каких элементов он состоит. Кнопка «Определить» запускает работу алгоритма построения дерева, а кнопка «Освободить» - освобождает весь массив и поля для дальнейшей работы с программой. Кнопка «Кодирование» - выводит закодированный символ. «Закрыть» - завершает работу программы.

2.2 Разработка кода программы

Для того, чтобы определить сколько повторяющихся символов в сообщении и какова все сообщения, я рассматривал введенные символы как единую строку «s», ввёл дополнительную переменную для подстроки «st» и создал цикл для которого условием выхода есть вся проверенная строка. С помощью стандартной функции «pos» находил одинаковую подстроку в строке т.е. одинаковые символы «st» в строке «s». После нахождения одинаковых символов удалял найденный, а количество удаленных инкрементировал. Инкремент и является количеством одинаковых символов.

Но каждый проверенный символ нужно опять добавить в массив с его числовым вхождением. Для этого был использован тот же самый массив, но он увеличивался на то количество, которое было проверено «setlength(a,KolSim)». В «Memo1» виден результат подсчета символов.

begin

Button2.Enabled:=true;

Button1.Enabled:=false;

Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

st:=s;

KolSim:=0;

while length(s)>0 do

begin

c:=s[1];

j:=0;

repeat

i:=pos(c,s);

if i>0 then

begin

inc(j);

delete(s,i,1);

end;

until not(i>0);

Memo1.Lines.Add(c+' -> '+inttostr(j));

inc(KolSim);

setlength(a,KolSim);

a[KolSim-1].Simvol:=c;

a[KolSim-1].Kolizestvo:=j;

a[KolSim-1].R:=-1;

a[KolSim-1].L:=-1;

a[KolSim-1].x:=1;

end;

Далее находим два наименьших элемента массива. Для этого были переменены две переменные Ind1 и Ind2 - исходные листья дерева. Им было присвоено значение «-1» т.е они пустые. Определил цикл прохождения по массиву, и ввел еще две переменных минимального значения: MinEl1 MinEl2. Эти элементы мы и находим, но для каждого создаём свой цикл нахождения:

repeat

MinEl1:=0;

MinEl2:=0;

Ind1:=-1;

Ind2:=-1;

for i:=0 to KolSim-1 do

if (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl1) or (MinEl1=0)) then

begin

Ind1:=i;

MinEl1:=a[i].Kolizestvo;

end;

for i:=0 to KolSim-1 do

if (Ind1<>i) and (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl2) or (MinEl2=0)) then

begin

Ind2:=i;

MinEl2:=a[i].Kolizestvo;

end;

После того, как нашли два минимальных элемента массива, складываем их и получаем новый индекс. При следующем прохождении по массиву учитываем лишь новый полученный индекс и сравниваем с оставшимися элементами. Такой цикл продолжается до тех пор, пока не останется одно значение - корень.

if (MinEl1>0) and (MinEl2>0) then

begin

inc(KolSim);

setLength(a,KolSim);

a[KolSim-1].Simvol:='';

a[KolSim-1].Kolizestvo:=MinEl2+MinEl1;

a[KolSim-1].R:=Ind1;

a[KolSim-1].L:=Ind2;

a[Ind1].x:=-1;

a[Ind2].x:=-1;

end;

until not((MinEl1>0) and (MinEl2>0));

Теперь всю информацию выведем в « Memo2 », а длину всего сообщения в « Еdit2» (Рис. 2.2).

for i:=0 to KolSim-1 do

begin

Memo2.Lines.Add(' s-> '+a[i].Simvol);

Memo2.Lines.Add('Veroat -> '+inttostr(a[i].Kolizestvo));

Memo2.Lines.Add('R -> '+inttostr(a[i].R));

Memo2.Lines.Add('L -> '+inttostr(a[i].L));

Memo2.Lines.Add('------------------------');

end;

Edit2.Text:=inttostr(KolSim);

Рис. 2.2. Отображение информации в полях

Теперь осталось лишь закодировать каждый введённый символ. Для этого использована была рекурсия.

Индексами были помечены все правые и левые ветви дерева. Рекурсия будет просматривать всё дерево, начиная с корня. Если будем идти по правой ветви, то расстоянию от уза до узла присвоим 0, по левому - 1. Ветви буду просматриваться до тех пор пока не будет достигнуто исходных листьев «-1 » (символов).

После достижения «-1» рекурсия заканчивает работу и выводит полученный результат в Memo3 (рис. 2.3).

Рис. 2.3. Полученный результат кодирования

Memo3.Lines.Add(a[Ind].Simvol+' -> '+s);

exit;

end;

if a[Ind].R<>-1 then

f(a[Ind].R,s+'0');

if a[Ind].L<>-1 then

f(a[Ind].L,s+'1');

ВЫВОДЫ

Во время разработки приложения мной было изучено множество литературы и статей о различных методах сжатия. Поэтому важным решением во время разработки приложения было простота и лёгкость в его использование и понимания выходной информации.

Был проведён анализ нескольких существующих алгоритмов кодирования без потерь. На основе полученных знаний можно сделать вывод, что все алгоритмы достаточно универсальны и покрывают все типы изображений, с другой у них, по сегодняшним меркам, слишком маленький коэффициент архивации. Используя один из алгоритмов сжатия без потерь, можно обеспечить архивацию изображения примерно в два раза. В то же время алгоритмы сжатия с потерями оперируют с коэффициентами 10-200 раз.

Помимо возможности модификации изображения, одна из основных причин подобной разницы заключается в том, что традиционные алгоритмы ориентированы на работу с цепочкой. Они не учитывают, так называемую, когерентность областей в изображениях. Идея когерентности областей заключается в малом изменении цвета и структуры на небольшом участке изображения. Все алгоритмы, о которых речь пойдет ниже, были созданы позднее специально для сжатия графики и используют эту идею.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Описание архиватора Narc фирмы Infinity Design Concepts, Inc

2. Чарльз Сейтер, 'Сжатие данных', "Мир ПК", N2 1991

3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. "Методы сжатия данных" - 2003г.

4. Балашов К.Ю. "Сжатие информации: анализ методов и подходов" - Минск, 2000г.

5. Мастрюков Д. "Алгоритмы сжатия информации"

6. Потапов В.Н. "Арифметическое кодирование вероятностных сточников"

7. Потапов В.Н. "Обзор методов неискажающего кодирования дискретных источников"

8. Семенова Ю.А. "Телекоммуникационные технологии"

9. Шелвин Е. "Алгоритм арифметического кодирования"

10. Фомин А.А. "Основы сжатия информации" - Санкт-Петербург, 1998г.

11. [9] С.В. Яблонский “Введение в дискретную математику”. // М. “Наука”, 1986. Раздел “Теория кодирования”.

12. [10] А.С. Климов “Форматы графических файлов”- “ДиаСофт” 1995.

13. [11] Д.С. Ватолин “Сжатие статических изображений” // Открытые системы сегодня. Номер 8 (29) Апрель 1995

14. [12] Д.С. Ватолин “MPEG - стандарт ISO на видео в системах мультимедиа” // Открытые системы. Номер 2. Лето 1995

15. http://artpro.nm.ru/ai14/11/g11.htm

16. http://www.victoria.lviv.ua/html/informatika/lecture9.htm

17. http://www.compression-pointers.ru/compress_141.html

18. http://www.alexlesson.ru/kategoriya_2/dlya_chego_nuzhen_archivator

19. http://prokovalya.narod.ru/kurs/index/format/algoritm/upoter.html

20. http://www.winsov.ru/delphi055.php

ПРИЛОЖЕНИЕ 1

1.1 Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TXafman=record

Simvol:string;//char;

Kolizestvo:integer;

R,L,x:integer;

end;

TForm1 = class(TForm)

Edit1: TEdit;

Memo1: TMemo;

Button1: TButton;

Memo2: TMemo;

Edit2: TEdit;

Label1: TLabel;

Label2: TLabel;

Button2: TButton;

Button3: TButton;

Memo3: TMemo;

Button4: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure f(Ind:integer;s:string);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var a:array of TXafman;

KolSim:integer;

Form1: TForm1;

implementation

{$R *.dfm}

//----------------Поиск и подсчет одинаковых элементов массива-----------

procedure TForm1.Button1Click(Sender: TObject);

var s,st:string;

c:char;

j,i,MinEl1,MinEl2,Ind1,Ind2:integer;

begin

Button2.Enabled:=true;

Button1.Enabled:=false;

Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

st:=s;

KolSim:=0;

while length(s)>0 do

begin

c:=s[1];

j:=0;

repeat

i:=pos(c,s);

if i>0 then

begin

inc(j);

delete(s,i,1);

end;

until not(i>0);

Memo1.Lines.Add(c+' -> '+inttostr(j));

inc(KolSim);

setlength(a,KolSim);

a[KolSim-1].Simvol:=c;

a[KolSim-1].Kolizestvo:=j;

a[KolSim-1].R:=-1;

a[KolSim-1].L:=-1;

a[KolSim-1].x:=1;

end;

// -------------------- процедура построения массива(дерева)--------------------

repeat

MinEl1:=0;

MinEl2:=0;

Ind1:=-1;

Ind2:=-1;

for i:=0 to KolSim-1 do

if (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl1) or (MinEl1=0)) then

begin

Ind1:=i;

MinEl1:=a[i].Kolizestvo;

end;

for i:=0 to KolSim-1 do

if (Ind1<>i) and (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl2) or (MinEl2=0)) then

begin

Ind2:=i;

MinEl2:=a[i].Kolizestvo;

end;

if (MinEl1>0) and (MinEl2>0) then

begin

inc(KolSim);

setLength(a,KolSim);

a[KolSim-1].Simvol:='';

a[KolSim-1].Kolizestvo:=MinEl2+MinEl1;

a[KolSim-1].R:=Ind1;

a[KolSim-1].L:=Ind2;

a[Ind1].x:=-1;

a[Ind2].x:=-1;

end;

until not((MinEl1>0) and (MinEl2>0));

//---------------------- Просмотр массива построения ---------------------------

for i:=0 to KolSim-1 do

begin

Memo2.Lines.Add(inttostr(i)+' - элемент');

Memo2.Lines.Add(' s-> '+a[i].Simvol);

Memo2.Lines.Add('Veroat -> '+inttostr(a[i].Kolizestvo));

Memo2.Lines.Add('R -> '+inttostr(a[i].R));

Memo2.Lines.Add('L -> '+inttostr(a[i].L));

Memo2.Lines.Add('------------------------');

end;

Edit2.Text:=inttostr(KolSim);

end;

//------------------------- Обнуление всех полей -------------------------------

procedure TForm1.Button2Click(Sender: TObject);

begin

a:=nil;

Edit1.Text:='';

Edit2.Text:='';

Memo1.Text:='';

Memo2.Text:='';

Memo3.Text:='';

Button2.Enabled:=false;

Button1.Enabled:=true;

end;

//-------------------------- кодирование дерева --------------------------------

procedure TForm1.f(Ind:integer;s:string);

begin

if (a[Ind].R=-1) and (a[Ind].L=-1) then

begin

Memo3.Lines.Add(a[Ind].Simvol+' -> '+s);

exit;

end;

if a[Ind].R<>-1 then

f(a[Ind].R,s+'0');

if a[Ind].L<>-1 then

f(a[Ind].L,s+'1');

end;

//--------------------- просмотр закодированного дерева -------------------------

procedure TForm1.Button3Click(Sender: TObject);

begin

Memo3.Clear;

f(KolSim-1,'');

end;

//--------------------- кнопка закрытия программы ------------------------------

procedure TForm1.Button4Click(Sender: TObject);

begin

Close;

end;

end.

ПРИЛОЖЕНИЕ 2

Пример построения дерева

Размещено на Allbest.ru