Алгоритм Шеннона-Фано

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

Санкт-Петербургский государственный университет

Факультет ПМ-ПУ

Курсовая работа

По дисциплине: Дискретная математика

На тему: "Алгоритм Шеннона-Фано"

Санкт-Петербург

2013 г.



Введение

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

Рассматривая двойственность природы данных: с одной стороны, содержимое информации, а с другой - ее физическое представление. В 1950 году американский ученый и инженер Клод Шеннон Элвуд заложил основы теории информации, а так же идею, которая заключается в том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.

Энтропия - в естественных науках мера беспорядка системы, состоящей из множества элементов.

Энтропия в информатике -- степень неполноты, неопределённости знаний.

В качестве простого примера можно рассмотреть исследование понятия вероятности с помощью монеты. Подбрасывая монету множество раз, можно построить большую таблицу с результатами, а затем выполнить статистический анализ этого набора данных с целью формулирования или доказательства какой-то теоремы. Для построения данной таблица, результаты подбрасывания монеты можно записывать несколькими различными способами: можно записывать слова "орел" или "решка"; можно записывать буквы "О" или "Р"; или же можно записывать единственный бит (1 - "да" или 0 "нет", изначально объявив соответствие значений и результатов). Согласно теории информации, результат каждого подбрасывания монеты можно закодировать единственным битом, поэтому последний приведенный вариант является наиболее эффективным с точки зрения объема памяти, необходимого для кодирования результатов.

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



1. Постановка задачи на языке данной предметной области

Изучить принципы кодирования информации Шеннона-Фано.

Сжатие данных.

Сжатие данных (data compression) - это алгоритм эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio). Он вычисляется путем вычитания из единицы частного от деления размера сжатых данных на размер исходных данных и обычно выражается в процентах. Например, если размер сжатых данных равен 1000 бит, а несжатых - 4000 бит, коэффициент сжатия составит 75%, т.е. мы избавились от трех четвертей исходного количества битов.

Конечно, сжатые данные могут быть записаны в форме недоступной для непосредственного считывания и понимания человеком. Люди нуждаются в определенной избыточности представления данных, способствующей их эффективному распознаванию и пониманию. Применительно к эксперименту с подбрасыванием монеты последовательности символов "О" и "Р" обладают большей наглядностью, чем 8-битовые значения байтов. (Возможно, что для большей наглядности пришлось бы разбить последовательности символов "О" и "Р" на группы, скажем, по 10 символов в каждой.) Иначе говоря, возможность выполнения сжатия данных бесполезна, если отсутствует возможность их последующего восстановления. Эту обратную операцию называют декодированием (decoding).



2. Описание алгоритма

Алгоритм, который мы рассматриваем - кодирование Шеннона-Фано, назван в честь двух исследователей, которые одновременно, независимо друг от друга разработали данный способ сжатия данных. Алгоритм анализирует входные данные и на их основе строит бинарное дерево минимального кодирования. Используя это дерево, затем можно выполнить повторное считывание входных данных и закодировать их.

Алгоритм Шеннона-Фано работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.

2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается "1", для правой "0", таким образом мы получим листья дерева

3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок. Код:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace Shannon_Fano

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

public static string alph_str = "";

public int[] arr_alph;

string s_text= "";

int max_ind = 0;

//int size_alph = 0;

public static string[] bin_alph_str;

private void richTextBox1_TextChanged(object sender, EventArgs e)

{

//label2.Text = "";

s_text = richTextBox1.Text;

}

string cl_str = "";

private void button1_Click_1(object sender, EventArgs e)

{

if (s_text.Length != 0)

{

label2.Text = "";

richTextBox2.Text = "";

richTextBox3.Text = "";

max_ind = 0;

for (int i = 0; i < s_text.Length; i++)

{

if (Convert.ToInt32(s_text[i]) >= max_ind) max_ind = Convert.ToInt32(s_text[i]);

}

arr_alph = new int[max_ind];

for (int i = 0; i < s_text.Length; i++) arr_alph[Convert.ToInt32(s_text[i]) - 1]++;

//size_alph = 0;

//for (int i = 0; i < arr_alph.Length; i++) if (arr_alph[i] != 0) size_alph++;

for (int i = 0; i < arr_alph.Length; i++)

{

if (arr_alph[i] != 0) alph_str = String.Concat(alph_str, Convert.ToChar(i + 1));

}

bin_alph_str = new string[Form1.alph_str.Length];

Shannon_Fano_tree.Grow_Tree(alph_str, arr_alph);

}

int size_of_comp_text = 0;

int size_of_codes = 0;

for (int i = 0; i < bin_alph_str.Length; i++)

{

richTextBox2.Text += "' " + alph_str[i] + " '" + ": " + bin_alph_str[i] + "\n";

size_of_comp_text += arr_alph[Convert.ToInt32(alph_str[i]) - 1] * bin_alph_str[i].Length;

size_of_codes += bin_alph_str[i].Length + 8;

}

double perc1 = (double)size_of_comp_text / ((double)richTextBox1.Text.Length * 8);

double perc2 = (double)size_of_comp_text / ((double)(size_of_comp_text + size_of_codes));

label2.Text += "Размер исходного текста: " + "\n" + Convert.ToString(richTextBox1.Text.Length * 8) + " бит" + "\n" + "\n";

label2.Text += "Размер текста после сжатия: " + "\n" + Convert.ToString(size_of_comp_text) + " бит " + "~" + Convert.ToString((int)(perc1 * 100)) + "%" + " от исходного." + "\n" + "\n";

label2.Text += "+ коды символов (для расшифровки): " + "\n" + Convert.ToString(size_of_comp_text + size_of_codes) + " бит " + "~" + Convert.ToString((int)(perc2 * 100)) + "%" + " от исходного." + "\n" + "\n";

string tmp_3 = "";

for (int i = 0; i < s_text.Length; i++)

{

for (int j = 0; j < alph_str.Length; j++)

{

if (s_text[i] == alph_str[j]) tmp_3 += bin_alph_str[j];

}

}

richTextBox3.Text = tmp_3;

for (int i = 0; i < arr_alph.Length; i++)

{

arr_alph[i] = 0;

}

cl_str = alph_str;

alph_str = "";

s_text= "";

max_ind = 0;

//size_alph = 0;

}

private void button2_Click(object sender, EventArgs e)

{

string bin_code_str = richTextBox3.Text;

string tmp = "";

string tmp_text = "";

string alph_str = cl_str;

for (int i = 0; i < bin_code_str.Length; i++)

{

for (int j = 0; j < bin_alph_str.Length; j++)

{

if (tmp == bin_alph_str[j])

{

tmp_text += alph_str[j];

tmp = "";

}

}

tmp += bin_code_str[i];

}

richTextBox1.Text = tmp_text;

}

}

class Shannon_Fano_tree

{

public static void Grow_Tree(string alph_str, int[] arr_alph)

{

int heap1 = 0, heap2 = 0;

string s_heap1 = "", s_heap2 = "";

for (int i = 0; i < alph_str.Length; i++)

{

if (heap1 >= heap2)

{

s_heap2 = String.Concat(s_heap2, alph_str[i]);

heap2 += arr_alph[Convert.ToInt32(alph_str[i]) - 1];

for (int j = 0; j < Form1.alph_str.Length; j++)

{

if (alph_str[i] == Form1.alph_str[j])

{

Form1.bin_alph_str[j] = String.Concat(Form1.bin_alph_str[j], "1");

}

}

}

else

{

s_heap1 = String.Concat(s_heap1, alph_str[i]);

heap1 += arr_alph[Convert.ToInt32(alph_str[i]) - 1];

for (int j = 0; j < Form1.alph_str.Length; j++)

{

if (alph_str[i] == Form1.alph_str[j])

{

Form1.bin_alph_str[j] = String.Concat(Form1.bin_alph_str[j], "0");

}

}

}

}

if (s_heap1.Length != 1)

{

Shannon_Fano_tr

}

if (s_heap2.Length != 1)

{

Shannon_Fano_tree.Grow_Tree(s_heap2, arr_alph);

}

}

}

}



3. Эксперименты

Для наглядной иллюстрации алгоритма, сделаем сжатие предложения "Карлсон, который живет на крыше.". Вычислим, сколько раз встречается каждый символ, и занесем данные в таблицу.

кодирование информация алгоритм сжатие

Таблица 1.1

Символ	Количество появлений
Пробел р о к а е т ы н К й л в и ш ж с . ,	4 3 3 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

Далее, разделив таблицу на две части, таким образом, чтобы число появлений символов в верхней половине таблицы примерно равнялось общему числу в нижней половине. В предложении 32 символа, а значит, верхняя часть таблицы должна содержать около 16 появлений. Мы можем получить этот результат, поместив разделительную линию(далее р.л.) между строками "е" и "т". В итоге верхняя часть будет содержать появление 16 символов, а нижняя, соответственно, оставшиеся 16. Получаем таблицу 1.2.



Таблица 1.2

Символ	Количество появлений
Пробел р о к а е т ы н К й л в и ш ж с . ,	4 3 3 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

Далее проделаем то же с каждой из частей таблицы: размесим линии так, чтобы разделить 2 полученные части на приблизительно равные по количеству появлений. Продолжаем процесс разделения до того момента, пока каждый символ не будет отделен от другого. Результирующее дерево Шеннона-Фано - Таблица 1.3.

Таблица 1.3.

Символ	Количество появлений
Пробел р о к а е т ы н К й л в и ш ж с . ,	4 3 3 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

Результирующее дерево в обычной ориентации.

Если принять, что перемещение влево эквивалентно нулевому биту, а вправо - единичному, можно создать таблицу кодирования.

Таблица 1.4

Символ	Кодировка
Пробел р о к а е т ы н К й л в и ш ж с . ,	000 001 0100 0101 0110 0111 1000 1001 1010 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

4. Результаты

Наша таблица содержит 137 бит, а оригинальная фраза "Карлсон, который живет на крыше." занимает 256 бит, следовательно, у нас получается коэффициент сжатия 53%.

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



Выводы

В данной работе были поставлены следующие цели и задачи: изучить принципы кодирования информации Шеннона-Фано. Преимуществом данного метода явлется его очевидная простота и, как следствие этого, высокая скорость кодирования и декодирования.



Заключение

Данный метод является простым в понимании, в реализации, а как следствие довольно эффективным. В настоящее время не используется, так как был усовершенствован Хаффманом, алгоритм которого в данный момент широко используется в связках с другими алгоритмами при кодировании/декодировании информации.

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

...