Утиліта стискання файлів за алгоритмом арифметичного кодування

 

3. Розробка програми

3.1. Вибір мови та середовища програмування

В якості мови програмування  я вибрав C#, оскільки ця мова є об’єктно- орієнтованою, має безпечну систему типізації і надає широкий вибір інструментів для розробника. Дане програмне забезпечення написано під платформу Microsoft .Net Framework 3.5 і вище.

Утиліта буде написана в середовищі програмуванні Microsoft Visual Studio 2010, оскільки дане середовище має зручний інтерфейс, широкий набір інструментів для створення графічного інтерфейсу користувача, інтерфейс для багатопотоковї розробки. Також дуже важливою особливістю даного середовища є легкість тестування та від лагодження програмних продуктів, які в ньому розробляються.

 

3.2. Бібліотеки, які  використовуються при написанні  програми

1. System.Collections.Generic - використовується для реалізації списку потоків.
2. System.ComponentModel - використовується для реалізації подій натискання на кнопки та зміни в формах наших вікон.
3. System.Data - містить класи для доступу до даних з різних джерел і для управління цими даними.
4. System.Drawing – використовується для настроювання вікна повідомлень яке викликається з вже існуючою форми.
5. System.Linq містить класи та інтерфейси, які підтримують запити, які використовують LINQ.
6. System.Text містить класи, що представляють кодування ASCII і Юнікод, абстрактні базові класи для перетворення блоків символів в блоки байтів і назад і клас підтримки, керуючий об'єктами String і форматує такі об'єкти без створення проміжних екземплярів String.
7. System.Windows.Forms – використовується для та під час створення нових форм, у тому числі і початкової форми вікна утиліти. Містить у собі опис всіх елементів які є у вікні(Button, Form, MessageBox, MessageBoxButtons, MessageBoxIcon, TextBox та ін.) та всіх параметрів вікон (розміри, положення на екрані, іконка, режим роботи та режим відображення, можливість нажаття на клавіші керування та ін.);
8. System.IO – використовується для створення потоків вводу та виводу текстових даних у файли
9. System.Diagnostics – в цьому просторі імен передбачені класи, які дозволяють здійснювати взаємодію з системними процесами
10. System.Threading – містить в собі класи і інтерфейси, які дають можливість використовувати потоки і багатопотоковість.
11. System.Runtime.InteropServices – використовується для завантаження DLL-бібліотек які не прив’язані до даної мови програмування, або створені не на даному комп’ютері (в проекті – більшість DLL-бібліотек використані для реалізації функцій виключення або перевантаження комп’ютера а також для роботи з привілегіями).

 

3.3. Розробка блок-схеми роботи програми кодування

Блок-схема роботи програми кодування наведена на Рис. 3.1

 

 

 

Рис. 3.1 Блок-схема роботи програми кодування

 

 

 

 

 

 Ні

 

Так

 

  

 

 

 

Рис. 3.1 «продовження»

 

 

 

 

 

Опис блок-схеми роботи програми кодування

1. InitializeComponent() – це внутрішня функція вікна, яка ініціалізує елементи, які є у формі. Іншими словами, ініціалізуються всі графічні елементи програми.
2. Вибір файлу, який потрібно стиснути:

Потрібний файл вибирається  за допомогою системного  виклику DialogResult result = openFileDialog1.ShowDialog().

Якщо файл був успішно  відкритий if (result == DialogResult.OK), то наступним кроком буде створення хендлу вхідного файлу, для подальшого визначення його розміру системною функцією GetFileSizeEx(handle, out fileSize).

3. Створення вихідного файлу:

Послідовність дій при  створенні вихідного файлу така сама, як і в пункті (2), тільки з  однією відмінністю: замість функції openFileDialog1.ShowDialog() використовується saveFileDialog1.ShowDialog().

4. Ініціалізація адаптивної моделі:

Програма повинна працювати  з моделлю, яка надає пару перекодованих таблиць index_to_char [] і char_to_index [], і масив накопичених частот cum_freq []. Причому до нього висуваються такі вимоги:

cum_freq [i-1]> = cum_freq [i];

ніколи не робиться спроба кодувати символ [i], для якого:

cum_freq [i-1] = cum_freq [i];

cum_freq [0] <= Max_frequency.

Якщо дані умови дотримані, значення в масиві не повинні мати зв'язку з дійсними значеннями накопичених  частот символів тексту.

public void start_model()

        {

            int i;

           

// Встановлення таблиць  перекодування

            for (i = 0; i < no_of_chars; i++)

            {

                char_to_index[i] = i + 1;

                index_to_char[i + 1] = i;

            }

           

// Встановлення лічильника  частот

            for (i = 0; i <= no_of_symbols; i++)

            {

                freq[i] = 1;

                cum_freq[i] = no_of_symbols - i;

            }

            freq[0] = 0;           

        }

5. Ініціалізація побітового виводу та коду перед початком стиснення:

В даному кроці встановлюються початкові значення для подальшого кодування.

public void start_outputing_bits()

        {

            buffer = 0;

            bits_to_go = 8;

        }

public void start_encoding()

        {

            // Повний кодовий інтервал

            low = 0L;

            high = top_value;

            bits_to_follow = 0L;

        }

6. Наступний крок  - безпосереднє кодування:

Спершу, завантажується перший символ файлу і передається на кодування.

Кодування одного символу  виконує функція encode_symbol();

public void encode_symbol(int symbol)

        {

            // Ширина поточного кодового інтервалу

            long range;

            range = (long)(high - low) + 1;

            // Перерахування границі

            high = low + (range * cum_freq[symbol - 1]) / cum_freq[0] - 1;

            low = low + (range * cum_freq[symbol]) / cum_freq[0];

            // Вивід бітів

            for (; ; )

            {

                // Якщо в нижній половниі

                if (high < half)

                    output_bit_plus_follow(0); // виводиться поточний  біт і ті, які були     //відкладені раніше

                // Якщо в верхній

                else if (low >= half)

                {

                    output_bit_plus_follow(1); // біт відкладається

                    low -= half;

                    high -= half;

                }

                /* якщо поточний інтервал в середині, то вивід біта також відкладається */

                else if (low >= first_qtr && high < third_qtr)

                {

                    bits_to_follow += 1;

                    low -= first_qtr;

                    high -= first_qtr;

                }

                else

                    break;

                // Розширюється кодовий інтервал

                low = 2 * low;

                high = 2 * high + 1;

            }

        }

Після цих кроків робиться перевірка на кінець файлу

if (ch == -1)

     break;

Якщо файл ще не закінчився, то попередні дії виконуються ще раз

7. Останнім кроком є очистка буфера побітового вводу dataout.WriteByte((byte)(buffer >> bits_to_go)), і закриття вхідного та вихідного файлів

dataout.Close();

   datain.Close();

а також визначається розмір вихідного файлу за допомогою функції GetFileSizeEx(), якій у параметри передаєть хендл вихідного файлу та змінна, у яку буде збережно розмір файлу.

 

 3.4. Розробка блок-схеми роботи програми декодування

Блок-схема роботи програми декодування наведена на Рис. 3.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

         Ні

 

      Так

 

Рис. 3.2 Блок-схема роботи програми декодування

 

 

 

 

 

 

 

 

Рис. 3.2 «продовження»

Опис блок-схеми роботи програми декодування

1. InitializeComponent() – це внутрішня функція вікна, яка ініціалізує елементи, які є у формі. Іншими словами, ініціалізуються всі графічні елементи програми.
2. Вибір файлу, який потрібно стиснути:

Потрібний файл вибирається  за допомогою системного  виклику DialogResult result = openFileDialog1.ShowDialog();

Якщо файл був успішно  відкритий if (result == DialogResult.OK), то наступним кроком буде створення хендлу вхідного файлу, для подальшого визначення його розміру системною функцією GetFileSizeEx(handle, out fileSize).

3. Створення вихідного файлу:

Послідовність дій при  створенні вихідного файлу така сама, як і в пункті (2), тільки з  однією відмінністю: замість функції openFileDialog1.ShowDialog() використовується saveFileDialog1.ShowDialog().

4. Ініціалізація адаптивної моделі:

Програма повинна працювати  з моделлю, яка надає пару перекодованих таблиць index_to_char [] і char_to_index [], і масив накопичених частот cum_freq []. Причому до нього висуваються такі вимоги:

cum_freq [i-1]> = cum_freq [i];

ніколи не робиться спроба кодувати символ [i], для якого:

cum_freq [i-1] = cum_freq [i];

cum_freq [0] <= Max_frequency.

Якщо дані умови дотримані, значення в масиві не повинні мати зв'язку з дійсними значеннями накопичених  частот символів тексту.

public void start_model()

        {

            int i;

           

// Встановлення таблиць  перекодування

            for (i = 0; i < no_of_chars; i++)

            {

                char_to_index[i] = i + 1;

                index_to_char[i + 1] = i;

            }

           

// Встановлення лічильника  частот

            for (i = 0; i <= no_of_symbols; i++)

            {

                freq[i] = 1;

                cum_freq[i] = no_of_symbols - i;

            }

            freq[0] = 0;           

        }

5. Ініціалізація побітового вводу виконується функцією start_inputing_bits(). Дана функція задає початкові параметри для декодування.

void start_inputing_bits()

        {

            bits_to_go = 0;

            garbage_bits = 0;

        }

6. Наступним кроком є вже безпосередньо декодування. Починається декодування із завантаженням першого символу стиснутої інформації

buffer = datain.ReadByte(), який згодом передається на вхід функції decode_symbol(), яка виконує декодування і запис вже декодованого символу у вихідний файл.

int decode_symbol()

        {

            // Ширина інтервалу

            long range;

            // Накопичена частота

            int cum;

            // символ, який декодується

            int symbol;

            int a;

            // Визначення поточної частоти

            range = (long)(high - low) + 1;

            // Знаходження значення накопиченої частоти

            cum = (int)((((long)(value - low) + 1) * cum_freq[0] - 1) / range);

            // пошук відповідного символу в таблиці частот

            for (symbol = 1; cum_freq[symbol] > cum; symbol++) ;

            // Перерахунок граниь

            high = low + (range * cum_freq[symbol - 1]) / cum_freq[0] - 1;

            low = low + (range * cum_freq[symbol]) / cum_freq[0];

            // Видалення чергового символу з вхідного потоку

            for (; ; )

            {

                // Розширення нижньої половини

                if (high < half)

                {

                }

                // Розширення верхньої половини

                else if (low >= half)

                {

                    value -= half;

                    low -= half;

                    high -= half;

                }

                // Розширення середини

                else if (low >= first_qtr && high < third_qtr)

                {

                    value -= first_qtr;

                    low -= first_qtr;

                    high -= first_qtr;

                }

                else

                    break;

                // Збільшення інтервалу

                low = 2 * low;

                high = 2 * high + 1;

                // Завантажити новий біт

                a = input_bit();

                value = 2 * value + a;

            }

            return symbol;

        }

Після цих кроків виконується  перевірка на кінець файлу. Якщо файл ще не закінчився, то цей крок повторюється знову, якщо файл закінчився, то переходимо до наступного етапу.