2 Ручной просчет построения дерева хаффмана
Строка для кодирования: "Сжатие Хаффмана".
Необходимо подсчитать количество вхождений каждого символа в тексте:
Таблица 2.1 – Таблица частот
С |
ж |
а |
т |
и |
е |
|
Х |
ф |
м |
н |
1 |
1 |
4 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
Узел дерева будет образован набором символов и числом – суммарным количеством вхождений данных символов в тексте – вес узла.
Листьями дерева – узлы, образованные одним символом:
Рисунок 2.1 – Листья дерева
Циклически выполняется следующие действия:
1) среди узлов, не имеющих родителя, выбираются два узла, имеющих в сумме наименьший вес;
2) создается новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.
Рисунок 2.2 – Построение дерева
Рисунок 2.2 – Построение дерева (продолжение)
Рисунок 2.2 – Построение дерева (продолжение)
Рисунок 2.2 – Построение дерева (продолжение)
Для каждого узла, имеющего потомков, помечаются дуги, идущие вниз, на одной 0, на другой 1.
Рисунок 2.3 – Дерево Хаффмана
Для того чтобы получить код символа, осуществляется, проход по дереву, начиная с корня, вниз до листа соответствующего данному символу.
Получается следующий результат (таблица 2.2).
Таблица 2.2 – Кодов и символов
С |
0000 |
ж |
0001 |
а |
01 |
т |
1000 |
и |
0001 |
е |
1010 |
|
1011 |
Х |
1100 |
ф |
111 |
м |
1101 |
н |
001 |
Заметно, что код является префиксным, т. е. ни один код символа не является префиксом кода другого символа. Также видно, что для часто встречающихся символов коды короче.
Как будет выглядеть закодированная строка (таблица 2.3).
Таблица 2.3 – Закодированная строка
С |
ж |
а |
т |
и |
е |
|
Х |
а |
ф |
ф |
м |
а |
н |
а |
0000 |
0001 |
01 |
1000 |
0001 |
1010 |
1011 |
1100 |
01 |
111 |
111 |
1101 |
01 |
001 |
01 |
Т. е.
0000000101100000011010101111000111111111010100101
3 Программная реализация алгоритма
3.1 Общая структура программы
Программа написана на языке Java и состоит из главной функции main и функций отвечающих за реализацию основных задач программы:
интерфейс (createGUI);
архивацию (Archiver);
декодирование (UnArchiver);
обработку файлов:
открытие файла (InFile);
обработка имени файла (Name);
дополнительных функций для кодирования данных:
построение дерева (Mas1);
преобразование символа в код (Coding).
На рисунке 3.1 приводится схема взаимосвязи функций.
Главная функция (main)
Функция отвечающая за интерфейс (createGUI)
Архивация
(Archiver)
Разархивация
(UnArchiver)
Обработка файлов
(Archiver)
Построение дерева (Mas1)
(Archiver)
Преобразование символа в код (Coding)
Открытие файла
(InFile)
Обработка имени файла (Name)
Рисунок 3.1 – Схема взаимосвязи функций
3.2 Описание логической структуры программы
Логическая структура программы, представленная на рисунке 3.2, даёт полное представление о последовательности работы программы.
Сначала появляется главное меню программы, в котором можно получить детальное описание о построении дерева Хаффмана, заархивировать, декодировать файл и выйти из программы.
После выбора архивации или декодирования осуществляется ввод данных - открывается проводник для выбора файла и в зависимости от выбранного действия выполняются определенные функции. По окончании работы осуществляется вывод результатов и выход в главное меню.
Главное меню программы
Система помощи
Архивация
Декодирование
Выход
Ввод данных
Работа алгоритма
Вывод результатов
Рисунок 3.2 – Схема логической структуры программы
3.3 Основные функции программы
3.3.1 Интерфейс (createGUI())
Функция реализует главное меню программы с возможностью выбора архивации, декодирования, справки и выхода из программы.
public void createGUI() {
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
final JPanel panel = new JPanel();
panel.setLayout(null);
JLabel k = new JLabel ("Выберите действие:");
k.setBounds(35,25,200,30);
panel.add(k);
JButton button1 = new JButton("Архивация файла");
button1.setBounds(30, 80, 200, 40);
panel.add(button1);
JButton button2 = new JButton("Декодирование файла");
button2.setBounds(265, 80, 200, 40);
panel.add(button2);
JButton button3 = new JButton("?");
button3.setBounds(420, 160, 45, 35);
panel.add(button3);
button1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
JFileChooser fileopen = new JFileChooser();
int ret = fileopen.showDialog(null, "Открыть файл");
if (ret == JFileChooser.APPROVE_OPTION) {
File file = fileopen.getSelectedFile();
String label;
label = file.getName();
float[] sum = Archiver(label);
JLabel k = new JLabel ("Вес исходного файла: " +String.valueOf(sum[0]));
k.setBounds(35,210,300,30);
panel.add(k);
k = new JLabel ("Вес сжатого файла: " +String.valueOf(sum[1]));
k.setBounds(35,230,300,30);
panel.add(k);
k = new JLabel ("Сжатие в " +String.valueOf(100-100*sum[1]/sum[0]) +"%");
k.setBounds(35,250,300,30);
panel.add(k);
}
}
});
button2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
JFileChooser fileopen = new JFileChooser();
int ret = fileopen.showDialog(null, "Открыть файл");
if (ret == JFileChooser.APPROVE_OPTION) {
File file = fileopen.getSelectedFile();
String label;
label = file.getName();
UnArchiver(label);
}
}
});
button3.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
InFile("Huffmanручнойпросчет.doc");
}
});
getContentPane().add(panel);
setPreferredSize(new Dimension(500, 350));
}
3.3.2 Архивация (Archiver)
Изначально необходимо выбрать файл для архивирования данных. Функция считывает текст из файла и обрабатывает – считает количество раз вхождения каждого символа. После чего вызывается функция Mas1, для построения дерева Хаффмана и функция Coding для преобразования символа в код. Создается файл с расширением «.kbk» с текстом как и в исходном, где каждый символ заменен кодом, соответствующим ему символом и таблицей частот. В конце программы выводятся данные с информацией о размере файлов и процентом сжатия.
public static float[] Archiver(String file)
{
int i = 0, j = 0;
float []sum = {0, 0};
ArrayList<Character> chars = new ArrayList();
ArrayList<String> a = new ArrayList <String>();
ArrayList< Integer > b = new ArrayList< Integer >();
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(new File(file)));
int c;
while ((c = reader.read()) != -1) {
chars.add((char) c);
}
reader.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
sum[0] = chars.size()*8;
for(i=0; i<chars.size(); i++)
{
a.add(String.valueOf(chars.get(i)));
}
for(i=0; i<a.size(); i++)
{
b.add(1);
for(j = i+1; j<a.size(); j++)
{
if(a.get(i).equals(a.get(j)))
{
b.set(i, b.get(i)+1);
a.remove(j);
j--;
}
}
}
String [][]mas = new String [a.size()+1][a.size()+1];
int [][]mas1 = new int [a.size()+1][a.size()+1];
int size1=a.size();
for(i=0; i<size1; i++)
{
mas[0][i] = String.valueOf(a.get(i));
mas1[0][i] = b.get(i);
mas[1][i] = String.valueOf(a.get(i));
mas1[1][i] = b.get(i);
}
int size2 = size1;
for (i=2; i<size1+1; i++)
{
Mas1(mas1[i-1], mas[i-1], size2);
for(j=0; j<size2-1; j++)
{
mas[i][j] = String.valueOf(mas[i-1][j]);
mas1[i][j] = mas1[i-1][j];
}
size2--;
}
size2 = size1;
String []dz; //двоичный код символа
dz = new String[chars.size()];
String []fgh; //динамический массив а в статическом виде
fgh = new String[chars.size()];
for(i=0; i<size1; i++)
{
fgh[i] = String.valueOf(a.get(i));
}
for(i=0; i<size1; i++)
{
Coding(dz, fgh, mas, size1);
}
String nfile = "";
nfile = Name(file)+".kbk";
try
{
PrintWriter pw = new PrintWriter(new File(nfile));
for(i=0; i<chars.size(); i++)
{
for(j=0; j<size1; j++)
{
if(String.valueOf(chars.get(i)).equals(a.get(j)))
{
byte rg;
for(int k = 0; k<dz[j].length(); k++)
{
rg = 0;
rg = Byte.parseByte( String.valueOf(dz[j].charAt(k)) );
pw.print(rg);
}
sum[1] = sum[1] + dz[j].length();
}
}
}
sum[1] = sum[1] + a.size()*8;
for(i=0; i<size1; i++)
{
pw.print("|/" +a.get(i));
byte hj;
for(int k = 0; k<String.valueOf(b.get(i)).length(); k++)
{
hj = 0;
hj = Byte.parseByte(String.valueOf((String.valueOf(b.get(i)).charAt(k))));
pw.print((byte) hj);
sum[1] += 1;
}
pw.print("/|");
byte rg;
for(int k = 0; k<dz[i].length(); k++)
{
rg = 0;
rg = Byte.parseByte( String.valueOf(dz[i].charAt(k)) );
pw.print((byte)rg);
}
}
pw.close();
}
catch(Exception e)
{
e.printStackTrace();
}
return sum;
}
3.3.3 Декодирование (UnArchiver())
Изначально необходимо выбрать файл для декодирования данных формата «.kbk». Функция считывает текст из файла и обрабатывает, разбивая текст на части: код исходного файла и таблица частот. После чего по таблице частот расшифровывается закодированный текст. Создается файл с расшифрованным текстом и выводится на экран.
public static void UnArchiver(String file)
{
int i = 0, j = 0, k = 0, g = 0, n = 0;
ArrayList<Character> chars = new ArrayList();
ArrayList<String> a = new ArrayList <String>();
ArrayList<String> d = new ArrayList <String>();
ArrayList<String> r = new ArrayList <String>();
ArrayList< Integer > b = new ArrayList< Integer >();
BufferedReader reader1 = null;
try {
reader1 = new BufferedReader(new FileReader(new File(file)));
int c;
while ((c = reader1.read()) != -1) {
chars.add((char) c);
}
reader1.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader1 != null) {
try {
reader1.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
i=0;
String str = new String();
str = "";
while(chars.get(i)=='0'||chars.get(i)=='1')
{
str+=String.valueOf(chars.get(i));
i++;
}
i += 2;
j = 0;
g = 0;
k = 0;
n = chars.size();
a.add(String.valueOf(chars.get(i)));
j++; i++;
while(i!=n-1)
{
if((chars.get(i)>= '0' && chars.get(i) <= '9'))
{
d.add("");
b.add(0);
while((chars.get(i)>= '0' && chars.get(i) <= '9'))
{
d.set(g, d.get(g)+String.valueOf(chars.get(i)));
b.set(g, Integer.parseInt(d.get(g)));
if (i!=n-1)
i++;
}
g++;
}
else
{
if(chars.get(i)=='/')
{i++;
if(chars.get(i)=='|')
{
if (i!=n-1)
i++;
r.add("");
while((chars.get(i)== '0' || chars.get(i) == '1'))
{
r.set(k, r.get(k)+String.valueOf(chars.get(i)));
if (i!=n-1)
i++;
else break;
}
k++;
}
}
else
{
if(chars.get(i)=='|')
{
i++;
if(chars.get(i)=='/')
{
if (i!=n-1)
i++;
a.add(String.valueOf(chars.get(i)));
if (i!=n-1)
i++;
}
}
}
}
}
String wer = new String();
String str1 = new String();
str1 = "";
while(str.length()>0)
{
for(i=0; i<a.size(); i++)
{
wer = "";
wer = r.get(i);
if(str.startsWith(wer)==true)
{
b.set(i, b.get(i)-1);
str1 += a.get(i);
str = new StringBuffer(str).
delete(0, wer.length()).toString();
}
else
{
for(j=0; j<i; j++)
{
if(b.get(j)!=0)
{
wer = r.get(j);
if(str.startsWith(wer)==true)
{
b.set(j, b.get(j)-1);
str1 += a.get(j);
str = new StringBuffer(str).
delete(0, wer.length()).toString();
}
}
}
}
}
}
String nfile = Name(file)+".txt";
try
{
PrintWriter pw = new PrintWriter(new File(nfile));
pw.print(str1);
pw.close();
}
catch(Exception e)
{
e.printStackTrace();
}
InFile(nfile);
}
ВЫВОДЫ
В ходе выполнения курсовой работы были изучены различные методы сжатия данных и методы их реализации. Также изучено сжатие информации путем построения дерева Хаффмана и реализация ручного просчета.
В программной реализации алгоритмов представлены взаимосвязи между основными функциями программы и подробно расписаны их выполняющие процессы.
Результатом реализации стал программный продукт, архивирующий и декодирующий файл методом Хаффмана.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Чарльз Сейтер, 'Сжатие данных', "Мир ПК", N2 1991г.
Мастрюков Д. "Алгоритмы сжатия информации".
Ватолин Д., Ратушняк А., Смирнов М., Юкин В. "Методы сжатия данных" - 2003г.
http://algolist.manual.ru/compress/standard/huffman.php
http://gorkoff.ru/wp-content/FoAT/FoAT_10.pdf
http://mindspring.narod.ru/alg/huffman.html
http://entropyware.info/HuffmanCode/huffcode.html
http://www.compression-pointers.ru/compress_24.html
Приложение А
ТЕХНИЧЕСКОЕ ЗАДАНИЕ
А.1 Общие сведения
Полное наименование создаваемого программного продукта: «Деревья Хаффмана».
Программный продукт проектируется студенткой II-го курса группы ПОС-12б Кузьменко Екатериной Борисовной.
Основанием для создания программного продукта является задание, выданное кафедрой программного обеспечения интеллектуальных систем.
Плановый срок начала работы по созданию программного продукта: 09 сентября 2013 года и срок окончания: 10 декабря 2013 года.
А.2 Назначение и цели создания программы
Программа предназначена для архивации файлов методом построения деревьев Хаффмана.
Основной целью проекта является программная реализация архиватора по алгоритму Хаффмана.
А.3 Характеристика объекта автоматизации
А.3.1 Сведения об объекте автоматизации
Объектом автоматизации является процесс сжатия и декодирования файлов.
А.3.2 Сведения об условиях эксплуатации программного продукта
Проектируемая программа может быть использована учащимися и студентами для архивации файлов.
А.4 Требования к программному продукту
А.4.1 Требования к проекту в целом
К программному продукту предъявляются следующие требования:
ввод данных из файла;
хранение данных в памяти компьютера;
вывод результатов в файл;
обеспечить дружественный интерфейс, включающий теоретическую справку по данному методу.
А.4.2 Требования к задачам и функциям, выполняемым программой
Система должна обеспечивать решение таких задач:
построение оптимального кодового дерева;
построение отображения кода-символа на основе построенного дерева;
построение исходных данных на основе кода-символа;
предоставление информационной справки о методе архивации.
А.4.3 Требования к видам обеспечения
А.4.3.1 Требования к техническому обеспечению
Для нормального функционирования проектируемого продукта:
достаточно ПК с процессором на базе Intel Pentium 4;
необходимо наличие ОС: Windows XP/Vista/Windows 7/Windows 8/ Windows 8.1;
А.4.3.2 Требования к информационному обеспечению
Информационная модель должна охватывать следующие аспекты:
организация структуры данных для хранения исходных данных (в оперативной памяти и в файле);
организация структуры данных для хранения результатов.
А.4.3.3 Требования к программному обеспечению
Программный продукт создается для операционных систем Windows XP/Vista/7/8/8.1. Разработка проекта предусматривается на языке Java.
А.4.3.4 Требования к организационному обеспечению
В программную документацию должны входить:
пояснительная записка;
приложения:
а) техническое задание;
б) листинг программы;
в) экранные формы (результаты, тесты);
г) руководство пользователя.
Таблица А.1 - Стадии и этапы разработки программного продукта
Этапы работы |
Срок выполнения |
1 Постановка задачи (определений требований к ПП, формулировка постановки задачи: исходные данные, ограничения, результаты, связь) |
1-2 недели |
2 Составление технического задания |
2-я неделя |
3 Сбор и изучение информации по заданному алгоритму |
3-я неделя |
4 Техническое проектирование (разработка методов решения задачи и модульный анализ: определение структуры программы, выделение модулей, организация или взаимосвязи) |
4-5 недели |
5 Рабочее программирование: определение структур входных и выходных данных, алгоритмов работы модулей, оценки структур данных и алгоритмов, описание входных и выходных данных |
6-я неделя |
6 Разработка самого алгоритма функционирования программы, составление спецификаций модулей |
7 неделя |
7 Написание программы:
|
8-10 недели 11-12 недели 12-13 недели 11-14 недели |
8 Защита курсового проекта |
14-16 недели |