Анотація Горох Б. “Оптимальне кодування. Код Шеннона-Фано”. Курсова робота. – НУ “Львівська політехніка”, каф.: ПЗ, дисципліна: “Методи та засоби комп`ютерних інформаційних технологій”, 2007. Курсова робота складається з 32 сторінок, 5 таблиць і 8 рисунків. В даній курсовій роботі спроектовано та розроблено програму, яка реалізовує кодування текстової інформації методом Шеннона-Фоно. Програмний продукт надає можливості користувачу кодувати текст введений у вікні програми або відкритий з текстового файлу. Розкодовувати закодований текст та переглядати його, зберігати закодований текст у файл. Є зручним та ефективним у використанні. Зміст Технічне завданя Анотація ……………………………………………………………….....3 Вступ 5 1. Огляд методів оптимального кодування…...................................................... 6 1.1. Кодування Хаффмена..................................................................6 1.2. Кодування Шенона-Фано……....................................................9 1.3. Алгоритм Шеннона-Фано…………………………..…………13 2. Постановка задачі та обґрунтування вибраного напряму проектування.....16 3. Програмна реалізація алгоритму......................................................................20 3.1 Програмна реалізація кодування методом Шеннона-Фано………...21 3.1.1 Вибір та обрахунок ймовірність появи символів в тексті.…21 3.1.2 Впорядкування ймовірностей………………………..…..…..21 3.1.3 Поділ множини повідомлень на дві частини………..…....…22 3.1.4 Присвоєння значення символу………………………..….…..22 3.1.5 Визначення значення наступного розряду коду…………….22 3.3 Процедура декодування методом Шеннона-Фано………………......23 3.4 Реалізація запису у файл……………………………………….……...23 3.5 Розробка інтерфейсу…………………………………………..……….24 4. Тестування програми Шеннона-Фано...............................................................27 5. Інформація користувачу…………….................................................................30 Висновки..................................................................................................................31 Література............................................................... ................................................32 Вступ Фундаментальне поняття теорії інформації – ентропія, яку можна розглядати як міру кількості інформації в повідомленні. Під вартістю мається на увазі середня довжина кодового слова (в бітах) на один символ вихідного тексту. Надлишковість кодування дорівнює різниці між вартістю кодування та ентропією вихідного повідомлення з розрахунку на один символ. Надлишковість також можна розглядати як відношення кількості надлишкових символів до кількості корисних: за таких визначень очевидно, що надлишковість завжди є невід’ємною. Ефективний алгоритм стискання має мінімізувати надлишковість (в ідеальному випадку – звести до нуля). Фундаментальна теорема Шеннона про кодування джерел стверджує, що вартість кодування завжди не менша, ніж ентропія джерела, хоча й може бути як завгодно близька до неї. Це твердження встановлює теоретичні границі стискання даних. 1. Огляд методів оптимального кодування Кодування (encoding) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи. Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена. Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена. 1.1. Кодування Хаффмена Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ. Нехай вхідний алфавіт складається з чотирьох символів: a, b, c, d, частоти яких відповідно дорівнюють 1/2, 1/4, 1/8, 1/8. Кодування Хаффмена для цього алфавіта подається таблицею 1. Символ Частота Вхідне кодування Вихідне кодування
A 1/2 00 0
B 1/4 01 10
C 1/8 10 110
D 1/8 11 111
Таблиця 1.1. Кодування Хаффмена
Рисунок 1.1. Дерево Хаффмена. Наприклад, кодом ланцюжка abaaacb, поданого на вході як 00 01 00 00 00 10 01 буде 0 10 0 0 0 110 10 (проміжки додано для зручності читання). Отже, 14 біт на вході дали 11 біт на виході – стискання очевидне! На мал. 1 подано двійкове дерево Хаффмена для наведеного коду. При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці. Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація). Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}. Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2! Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду “ab”, “abc”,..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам’яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання). Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно. 1.2. Кодування Шенона-Фано Кодування Шеннона-Фано є одним з найперших алгоритмів стиснення. Даний метод стиснення має велику схожість з кодуванням Хаффмана, яке з'явилося на декілька років пізніше. Алгоритм Шеннона-Фано використовує надмірність повідомлення, увязнену в неоднорідному розподілі частот символів його (первинного) алфавіту, тобто замінює коди частіших символів короткими двійковими послідовностями, а коди рідших символів - довшими двійковими послідовностями. Коди Шеннона-Фано префіксні, тобто, ніяке кодове слово не є префіксом будь-якого іншого. Ця властивість дозволяє однозначно декодувати будь-яку послідовність кодових слів. Алгоритм був незалежно один від одного розроблений Шеноном (публікація "Математична теорія зв'язку", 1948 рік) і, пізніше, Фано (опубліковано як технічний звіт). Таким чином, алгоритм ґрунтується на кодах змінної довжини. Для того, щоб декомпресор згодом зміг розкодувати стислу послідовність, коди Шеннона-Фано повинні володіти унікальністю, тобто, не дивлячись на їх змінну довжину, кожен код унікально визначає один закодований символ і не є префіксом будь-якої іншого коду. Код Шеннона-фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає Кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковою сумарною вірогідністю. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковою сумарною вірогідністю. Їм відповідають вершини третього рівня. Якщо підмножину містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Так само поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0, як в разі коду Хаффмана. При побудові коду Шеннона-Фано розбиття безлічі елементів може бути проведене, взагалі кажучи, декількома способами. Вибір розбиття на рівні n може погіршити варіанти розбиття на наступному рівні (n+1) і привести до неоптимальності коду в цілому. Іншими словами, оптимальна поведінка на кожному кроці шляху ще не гарантує оптимальності всієї сукупності дій. Тому код Шеннона-фано не є оптимальним в загальному сенсі, хоча і дає оптимальні результати при деяких розподілах вірогідності. Для одного і того ж розподілу вірогідності можна побудувати, взагалі кажучи, декілька кодів Шеннона-Фано, і всі вони можуть дати різні результати. Якщо побудувати всі можливі коди Шеннона-Фано для даного розподілу вірогідності, то серед них знаходитимуться і всі коди Хаффмана, тобто оптимальні коди. Приклад кодового дерева. Початкові символи: A (частота тієї, що зустрічається 50), B (частота тієї, що зустрічається 39), C (частота тієї, що зустрічається 18), D (частота тієї, що зустрічається 49), E (частота тієї, що зустрічається 35), F (частота тієї, що зустрічається 24).
Рисунок 1.2.1 Дерева. Розподіл кодів. Отриманий код: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010. Дерева і коди діляться на префіксні і непрефіксні: В префіксних кодах повідомлення відповідають тільки кінцевим вершинам дерева. Для непрефісних кодів повідомлення можуть розташовуватись в проміжних вузлах. Префіксні коди можна розтиснути, непрефіксні неможливо однозначно розтиснути. Кодування Шеннона-фано є достатньо старим методом стискування, і на сьогоднішній день воно не представляє особливого практичного інтересу. В більшості випадків, довжина стислої послідовності, по даному методу, дорівнює довжині стислої послідовності з використанням кодування Хаффмана. Але на деяких послідовностях все ж формуються неоптимальні коди Шеннона-фано, тому стискування методом Хаффмана прийнято вважати за ефективніше. Для прикладу, розгледимо послідовність з таким змістом символів: 'a' - 14, 'b' - 7, 'c' - 5, 'd' - 5, 'e' - 4. Метод Хаффмана стискує її до 77 біт, а ось Шеннона-Фано до 79 біт. Таблиця 1.2.1 Порівняння коду Шеннона-Фано, Хафмена Символ код Хаффмана код Шеннона-фано
а 0 00
b 111 01
з 101 10
d 110 110
e 100 111
До речі, в одному джерелі (не указуватиму якому), цю послідовність стискували методом Шеннона-Фано до 84 біт, а методом Хаффмана до тих же 77. Такі відмінності в ступені стискування виникають із-за нестрогого визначення способу ділення символів на групи. Як же ми ділили на групи? Досить просто: імовірність першої групи (p1) і другої (p2) дорівнює нулю; p1 <= p2 ? - так: додати в першу групу символ з початку таблиці; - ні: додати в другу групу символ з кінця таблиці; Якщо всі символи розділені на групи, то завершити алгоритм, інакше перейти до кроку 2. 1.3 Алгоритм Шеннона-Фано Символи первинного алфавіту m1 виписують в порядку спадання вірогідності. Символи отриманого алфавіту ділять на дві частини, сумарна вірогідність символів яких максимально близька один одному. У префіксному коді для першої частки алфавіту привласнюється двійкова цифра "0", другій частці - "1". Отримані частки рекурсивно ділятся і їх часткам призначаються відповідні двійкові цифри в префіксному коді. Коли розмір підалфавіту стає рівний нулю або одиниці, то подальшого подовження префікснго коду для відповідаючого йому символу первинного алфавіту не відбувається, таким чином, алгоритм привласнює різним символам префіксні коди різної довжини. На кроці ділення алфавіту існує неоднозначність, оскільки різниця сумарної вірогідності p0, p1 може бути однакова для двох варіантів розділення (враховуючи, що всі символи первинного алфавіту мають вірогідність, більшу нуля). Розглянемо алгоритм обчислення коду Шеннона-Фано детальніше: (для наочності візьмемо як приклад послідовність 'Aa bbb cccc ddddd'). Для обчислення коду, необхідно створити таблицю унікальних символів повідомлення(ь) і їх вірогідності p(с(i)), і відсортувати її в порядку спадання. Таб.1.3.1 Ймовірності символів с(i) p(с(i))
d 5 / 17
з 4 / 17
space 3 / 17
b 3 / 17
а 2 / 17
Далі, таблиця символів ділиться на дві групи так, щоб кожна з груп мала приблизно однакову частоту по сумі символів. Першій групі встановлюється початок коду в '0', другий в '1'. Для обчислення наступних біт кодів символів, дана процедура повторюється рекурсивно для кожної групи, в якій більше одного символу. Таким чином для нашого випадку отримуємо наступні коди символів: Таб.1.3.2 Коди символів Символ Код
d 00
з 01
space 10
b 110
а 111
Довжина коду s(i) в отриманій таблиці рівна int(-lg p(с(i))), якщо символи вдалося розділити на групи з однаковою частотою, інакше, довжина коду рівна int(-lg p(с(i)))+ 1. int(-lg p(с(i))) <= s(i) <= int(-lg p(с(i)))+ 1 Використовуючи отриману таблицю кодів, кодуємо вхідний потік - замінюємо кожен символ відповідним кодом. Природно для розтиснення отриманої послідовності, дану таблицю необхідно зберігати разом із стиснутим потоком, що є одним з недоліків даного методу. У стиснутому вигляді, наша послідовність набирає вигляду: 111111101101101101001010101100000000000 завдовжки в 39 біт. Враховуючи, що оригінал мав довжину рівну 136 біт, отримуємо коефіцієнт стискування ~28% - не так вже і погано. Дивлячись на отриману послідовність, виникає питання: " А як же тепер це розтискати? ". Ми не можемо, як в разі кодування, замінювати кожні 8 біт вхідного потоку, кодом змінної довжини. При розтиснені нам необхідно все зробити навпаки - замінити код змінної довжини символом завдовжки 8 біт. В даному випадку, краще всього використовувати бінарне дерево, листям якого будуть символи (аналог дерева Хаффмана).
Рис. 1.3.1. Дерева. Префіксні входи Недоліком такого методу кодування є крихкість коду – його нестійкість до спотворень, завад. 2. Постановка задачі та обґрунтування вибраного напряму проектування Оскільки дискретне представлення інформації має в цілому більш загальний характер широко застосовуються дискретні способи уявлення. Застосовується цифровий код заснований на позиційній системі числення з підставою 10, 8, 16, 2. Двійкова система застосовується оскільки вимагає найменшої кількості розрядів. Прикладом дискретних пристроїв являются нейрони головного мозку. Вибір оптимальної системи числення. Для оптимального запису даних необхідно, щоб запис досягався найменшою кількістю символів при найменшій же кількості розрядів. Ці умови є суперечливими. Припустимо, що оптимальною системою є та, яка дозволяє обійтися найменшою кількістю апаратури. Кількість апаратури слід покласти пропорційним створення числа символів s на число розрядів N. Найбільше число символів, яке можна записати M= sN - 1 (K.1) Наприклад в десятковій системі за допомогою трьох розрядів запишемо: M= 103-1=999 З (K.1) знайдемо N= ln(M+1) /ln s Кількість апаратури пропорційна Ns = s ln(M+1)/ ln s Умовою мінімуму аппартури є рівність нулю похідної правої частки даного рівняння, отже Lns -1=0, отже S=e (2.71) Відзначимо, що основа системи числення має бути цілим числом. Вивід Якнайкращої по критерію мінімуму апаратури є трійкова система числення. Проте з ряду причин технічного характеру застосовується двійкова система, яка дає декілька гірший результат. Двійкова система добре узгоджується з двійковою логікою і двійковим кодуванням. Аналогії з живої природи. Мозок і його робота. Нервова система і мозок складаються з нейронів. Будова нейрона наступна - декілька дендридів по яких приймається інформація і єдиний аксон по якому імпульс передається наступним нейронам при збудженні останнього через синапси. Враховуючи, що на силу імпульсу впливає аксон (який з'єднується з нейроном через синапси) можна сказати, що в простому випадку система зможе приймати три стани - немає сигналу, гальмування і збудження (сигнал видається наступним нейронам). Підстава системи числення або логарифма при обчисленні обємів інформації визначає одиницю виміру інформації і ентропії. Двійкова система- біт Натуральна (е=2,718) - ніт (1 ніт= 1,44269 біт) 10 - діт (1 дит= 3, 32193 біт) Ефективне кодування. Вибір оптимального коду. Простий варіант - застосування рівномірного коду, в якому кожен символ кодується одинковим числом розрядів. Приклад A - 00, B - 01, C- 10, D-11. Середня довжина повідомлення залежить від вірогідності появи символів коду. S = S Pi Li Припустим Pa=1/2 Pb=1/4 Pc=1/8 Pd=1/8 При рівній довжині коду (2) - середня довжина повідомлення складе - 2 Закодуємо повідомлення інакше A - 0, B - 10, C- 110, D-111 (Відзначимо, що повідомлення можна повністю відновити з його початкової форми). Тоді S= 1*1/2+2*1/4+3*1/8+3*1/8=1,75 Отже оптимальний код відповідає ентропії, розрахованої для вірогідності появи символів PI Фрагмент коду приведений вище називається кодом Шеннона-Фано. Таблиця 2.1 Код Шеннона-Фано Розставимо символи в порядку убування вірогідності
Підсумок
A Pa=1/2 0
0
B Pb=1/4 1 0
10
C Pc=1/8 1 1 0 110
D Pd=1/8 1 1 1 111
Під час виконання курсової роботи було поставлено задачу програмно реалізувати алгоритм кодування Шеннона-Фано. Даний програмний продукт повинен бути призначений для кодування тексту різного типу, та збереження його у зменшеному форматі. Програма повина працювати в віконному режимі. Інтерфейс повинен бути досить простий і легкий до розуміння та використання. Вхідними даними повинен бути текст введений користувачем у відповідному вікні програми, або текстовий файл відкритий засобами програми. Вихідною повина бути інформація представлена після певного кроку виконання алгоритму у відповідному елементі програми а саме: 1. Вірогідності появи символів; 2. Впорядковані символи за спаданням вірогідності; 3. Алфавіт кодів; 4. Закодований текст. Програма повинна працювати з текстовими файлами, які знаходяться в будь-якій директорії. Також програма повинна виконувати збереження закодованого тексту в файл з розширенням byt та розкодованого тексту в файл з розширенням txt. 3. Програмна реалізація Курсовий проект розроблявся в середовищі Delphi 7. Це дозволило швидко реалізувати зручний користувацький інтерфейс, опрацювання відкривання та закривання файлів. Для роботи з відкриттям та збереженням файлів Delphi надає діалогові компоненти: TOpenDialog відображає модальні діалогові вікна Windows для відкриття (збереження) файлів. Компоненти TOpenDialog і TSaveDialog працюють з файлами будь-якого типу. Відкриття відповідного діалогу здійснюється методом Execute. Якщо в діалозі користувач натискуватиме кнопку Відкрити (Зберегти), діалог закривається, метод Execute повертає true і вибраний файл відображається у властивості компоненти-діалогу FileName. Якщо ж користувач відмовився від діалогу (натиснув кнопку Відміна або клавішу Esc), то метод Execute повертає false. Значення властивості FileName можна задати і перед зверненням до діалогу. Тоді воно з'явиться в діалозі як значення за замовчуванням у вікні Ім'я файла. Таким чином виконання команди Зберегти як ..., по якій у файлі з вибраним користувачем ім'ям треба зберегти текст вікна редагування Memo5, може мати вигляд: if savedialog1.Execute then memo5.Lines.SaveToFile(savedialog1.FileName); Також інтегроване середовище програмування Delphi 7 надає Багато процедур і функцій обробки файлів, на які вказують дескриптори. FileWrite(Handle: Integer; const Buffer; Count: Integer): Integer Записує у файл, вказаний своїм дескриптором Handle з Buffer число байтів Count. Повертає число дійсно записаних байтів. FileRead(Handle: Integer; var Buffer; Count: Integer): Integer Читає з файлу, вказаного своїм дескриптором Handle (FileCreate і FileOpen) в Buffer число байтів Count. Повертає число дійсно прочитаних байтів. 3.1 Програмна реалізація кодування методом Шеннона-Фано 3.1.1 Вибір та обрахунок ймовірність появи символів в тексті В даному розділі описується реалізація одиного з кроків алгоритму Шеннона-Фано, а саме, обрахунок ймовірності появи символів у вибраному тексті. Для цього потрібно, спочатку, визначити загальну кількість символів у тексті. Далі, визначити кількості появ кожного символу, та поділити кожне з цих значень на кількість символів у тексті. Для реалізації даного кроку був використаний цикл <while do > та стандартні функції length та copy: begin s:=Edit2.Text; ds:=length(s); for i:=1 to ds do begin s2:=Edit1.Text; search:=''+s[i]; kilk:=0; while (pos(search,s2) <> 0) do begin kilk:=kilk+1; s2:=copy(s2, pos(search,s2)+1,length(s2)- pos(search,s2)); end;//while imov[i]:=kilk/length(Edit1.Text); Memo1.Lines.Add(s[i]+' '+IntToStr(kilk)+' '+FloatToStr(imov[i])); end;//i end; 3.1.2 Впорядкування ймовірностей Фрагмент коду описаний нижче призначений для впорядкування ймовірностей появи символів у слові за спаданням. Для цього виконується порівняння кожної ймовірності з наступною і більша з них переміщується на початок: for j:=1 to ds-1 do for i:=1 to ds-j do if imov[i] < imov[i+1] then begin temp:=imov[i]; imov[i]:=imov[i+1]; imov[i+1]:=temp; temp2:=s2[i]; s2[i]:=s2[i+1]; s2[i+1]:=temp2; end; В циклі формується масив ймовірностей і виводить у Мемо: for i:=1 to ds do begin Memo2.Lines.Add(s2[i]+' '+FloatToStr(imov[i])); end; 3.1.3 Поділ множини повідомлень на дві частини Поділ множини повідомленнь здійснюєтся наступним чином: береться перша (найбільша) вірогідність і порівнюється із сумою всіх решта, що під нею. Якщо вона менша, то до неї додається наступна, і ця вірогідність віднімається від «нижньої» суми результати знову порівнюються. Порівнюється різниця між цими сумами. for i:=2 to ds do begin sum2:=sum2+imov[i]; end; min:=abs(sum1-sum2); for i:=2 to ds do begin sum1:=sum1+imov[i]; sum2:=sum2-imov[i]; if (abs(sum1-sum2) < min) При найменшій різниці ставить умовна риска – змінній присвоюється номер ймовірності, після якої слідує риска: then begin min:=abs(sum1-sum2); riska:=i; end; 3.1.4 Присвоєння значення символу Присвоєння реалізуєтся так : Всі значення символів зберігаються у масиві, який у циклі виводиться як результат у Мемо, до нього дописується масив кодів, який повертає вище описана функція: for i:=1 to length(Edit2.Text) do begin edit3.Text:=edit3.Text+codes2[i]; memo4.Lines.add(codes[i]); end; 3.1.5 Визначення значення наступного розряду коду Визначення реалізує функція: getRiska, яка визначає кожне наступне значення відповідним кроком циклу. Вона отримує як параметри номер першої ймовірності та довжину алфавіту повідомлень: for i:=1 to length(Edit2.Text) do begin codes2[i]:=codes[i]; codes[i]:=letters[i]+' = '; end; Label2.Caption:=intTostr(getRiska(1,length(Edit2.Text))); 3.3 Процедура декодування методом Шеннона-Фано Процедура декодування бере кожен код з масиву кодів і за допомогою функції pos шукає відповідний йому символ. Якщо відповідність знайдена, то за допомогою функції copy формується результат (рядок символів що відповідають кодам) procedure TForm1.Button2Click(Sender: TObject); var s,search:string; i:word; ls,ll: integer; begin Edit4.Text:=''; s:= Edit3.Text; ls:= length(s) ; while length(s) > 0 do begin ll:=length(sortedSymbols); for i:=1 to length(sortedSymbols) do begin search:=codes[i]; if pos(search,s)=1 then begin Edit4.Text:=Edit4.Text+sortedSymbols[i]; s:=copy(s, pos(search,s)+length(codes[i]),length(s)-length(codes[i])); break; end; end; end; Memo5.Text:=Edit4.Text; end; 3.4 Реалізація запису у файл Запис у файл реалізований за допомогою стандартної процедури SetLength, що встановлює довжину NewLength змінни S типу рядка або динамічного масиву. Та, процедури GetByte. Наведена нижче процедура реалізує перекодування бітів у байти, запис байтів у масив aFileArray та запис їх в файл з розширенням BYT. procedure TForm1.Button7Click(Sender: TObject); var i:integer; s:string; l:integer; begin //--------------------------------- s:=edit3.Text; if (l mod 8)<>0 then for i:=1 to 8-(l mod 8) do s:=s+'0'; l:=Length(s); SetLength(aFileArray,0); SetLength(aFileArray,l div 8); for i:=0 to High(aFileArray) do begin aFileArray[i]:=GetByte(Copy(s,1+8*i,8)); end; //запис у файл if SaveDialog1.Execute then aSaveFile(SaveDialog1.FileName); end; end. 3.5 Розробка інтерфейсу В реалізації інтерфейсу програми використовувались такі елементи: Edit. В компоненті TEdit текст, що вводиться і виводиться, міститься у властивості Text. Цю властивість можна встановлювати в процесі проектування або задавати програмно. Вирівнювання тексту неможливе. Перенесення рядків теж неможливе. Текст, що не поміщається по довжині у вікно, просто зсовується і користувач може переміщатися по ньому за допомогою курсора. Властивість AutoSize дозволяє автоматично підстроювати висоту (але не ширину) вікна під розмір тексту. Button Компонент TButton є стандартною кнопкою Windows, що ініціює якусь дію. Основна з погляду зовнішнього вигляду властивість кнопки - Caption (напис). В написах кнопок можна передбачати використовування клавіш прискореного доступу, виділяючи для цього один з символів напису - ставлячи перед ним символ амперсанта "&". Цей символ не з'являється в написі, а наступний за ним символ виявляється підкресленим. Тоді користувач може замість клацання на кнопці натискувати у будь-який момент клавішу Alt спільно з клавішею виділеного символу. Основна подія кнопки - OnClick, виникаюче при натисненні на ній. В обробнику цієї події записуються оператори, які повинні виконуватися при натисненні користувача на кнопці. TMemo - багаторядковий текстовий редактор, що дозволяє редагувати текст вікна, в яке можна вводити на відміну від компоненту TEdit не одну, а безліч рядків. Виконує функції більшості редакторів, має "гарячі" клавіші для швидкого редагування. Формат всього тексту однаковий і визначається властивістю Font. Властивість Lines, доступна як під час проектування, так і під час виконання, має безліч властивостей і методів типу TStrings, які звичайно використовуються для формування і редагування тексту. Весь текст міститься у властивості Text. TMainMenu відображає на формі головне меню. Проектування меню проводиться за допомогою конструктора меню, що викликається подвійним клацанням на цьому компоненті. Команди контекстного меню конструктора Create Submenu дозволяє ввести підміню у виділений розділ. Властивості і методи TMainMenu забезпечують об'єднання меню головної і допоміжної форм і зв'язок з меню OLE контейнера. Властивість Items містить масив розділів меню типу TMenuItem, що володіють своїми властивостями, методами, подіями. Властивість Caption позначає напис розділу, властивість Name - ім'я об'єкту розділу, властивість ShortCut визначає клавіші швидкого доступу до розділу. Також були використані засоби для роботи з діалоговими вікнами та стандартні процедури: Метод Execute здійснює виклик діалогових вікон у всіх компонентах-діалогах. Якщо користувач здійснив в діалозі необхідний вибір, метод повертає true. Якщо ж користувач відмовився від вибору (натискував Esc або кнопку Відмінити), то повертається false. Таким чином, виклик будь-якого діалогу здійснюється звичайно наступним оператором: (имя компонента диалога.Execute) then <оператор обробки відповіді пользователя> else <оператор, виконуваний при відмові користувача від диалога>; Основна властивість, в якій повертається у вигляді рядка вибраний користувачем файл, - FileName. Значення цієї властивості можна задати і перед зверненням до діалогу. Тоді воно з'явиться в діалозі як значення за умовчанням у вікні Ім'я файла Типи шуканих файлів, що з'являються в діалозі у випадаючому списку Тип файлау, задаються властивістю Filter. В процесі проектування ця властивість простіше всього задати за допомогою редактора фільтрів, який викликається натисненням кнопки з багатокрапкою біля імені цієї властивості в Інспекторі Об'єктів. При цьому відкривається вікно редактора. В його лівій панелі Filter Name ви записуєте той текст, який побачить користувач у випадаючому списку Тип файла діалогу. А в правій панелі вікна редактора записуються розділені крапками з комою шаблони фільтру. 4. Тестування Програми «Алгоритм Шеннона-Фано» Для оцінки роботи програми було проведено тестування програми. Було введено текст безпосередньо в програму з клавіатури і закодовано:
Рисунок 4.1 Шифрування тексту введеного користувачем. Після того як текст був закодований його збережено у файл з розширенням BYT.
Рисунок 4.2 Запис BYT -файлу. Після цього було розкодовано та збережено результат в текиовий файл і проглянуто результати:
Рис.4.3 Розкодування тексту.
Рис.4.0.4. Збереження результату.
Рис.4.5 Перегляд результату. Так само було протестовано реалізацію кодування тексту відкритого з файлу результати задовільні. Отже за результатами тестування можна зробити висновок, що програма ефективна і може застосовуватись для кодування текстової інформації. 5. Інформація користувачу Дана програма працює в віконному режимі, тому немає необхідно знати набір команд для її використання. Для кодування тексту необхідно в полі введення, яке знаходитися під кнопкою «Відкрити TXT» ввести текс або за допомогою вікна яке з’явиться після натиснення кнопки «Відкрити TXT» вказати текстовий файл який потрібно. Після того як текст введено натиснення кнопки «Закодувати текст» зреалізує алгоритм кодування і відповідний код зявится під даною кнопкою. Для реалізації розкодування призначена кнопка «Розкодувати». Для запису розкодованого тексту у файл скористайтесь кнопкою «Зберегти TXT». Для запису коду у файл з розширенням BYT скористайтесь кнопкою «Записати код у файл». Для виходу з програми потрібно натиснути у правому верхньому куті на червоний хрестик. Висновки В процесі виконання курсової роботи було засвоєно матеріал по темі: Оптимальне кодування. Код Шеннона-Фано. Даний метод виділяється своєю простотою. Беруться початкові повідомлення m(i) і їх вірогідність появи P(m(i)). Цей список ділиться на дві групи з приблизно рівною інтегральною імовірністю. Кожному повідомленню з першої групи привласнюється 0 як перша цифра коду. Повідомленням з другої групи ставляться у відповідність коди, що починаються з 1. Кожна з цих груп ділиться на дві аналогічним чином і додається ще одна цифра коду. Процес продовжується до тих пір, поки не будуть отримані групи, що містять лише одне повідомлення. Кожному повідомленню в результаті буде привласнений код x з довжиною -lg(P(x)). Це справедливо, якщо можливе ділення на підгрупи з абсолютно рівною сумарною імовірністю. Якщо ж це неможливо, деякі коди матимуть довжину -lg(P(x))+1. Алгоритм Шеннона-фано не гарантує оптимального кодування. При тестуванні програми було виявлено, що програма є досить ефективною. До переваг програмного продукту можна віднести: Простий і зручний інтерфейс. Висока швидкість кодування/розкодування (розмір файлів до 100Кб). Невеликий розмір програми, та малі системні вимоги. Простота у використанні та керуванні. Можливість стиснення інформації до 30% До недоліків програми належать: Відсутність можливості відкриття збереженого BYT файлу. Літературні джерела Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.М.:Мир, 1978. Антонью А. Цифровые фильтры: Анализ и проектирование: Пер с англ. - М.: Радио и связь, 1983. Цифровая обработка сигналов. Справочник / Л.М.Гольденберг, Б.Д.Матюшкин, М.И.Поляк.- М. Радио и связь,1985. Мочульський Ю. Аналогова і цифрова обробка сигналів: Навчально-методичний посібник.-Львів:ЛНУ імені Івана Франка,1999. http://aforge.ibd.lv/?8 А. М. Яглом, И. М. Яглом Вероятность и информация. — М.: «Наука», 1973. Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.М.:Мир, 1978. http://ravil.astersoft.net/Students/Cybernetics/cybernetics.htm http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html Кохманюк Д. “Сжатие информации: как это делается”, Index PRO, 1993 К., №№ 1-2. Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989. Рябко Б.Я. Сжатие информации спомощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. – IEEE Transactions, IT-24. – No.5 (Sept.1978), pp. 530-536.
