WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Реалізація ідеї арифметичного кодування - Реферат

Реалізація ідеї арифметичного кодування - Реферат

На жаль, цей псевдокод значно спрощений, тоді як в практичному застосуванні існує декілька чинників, які ускладнюють і кодування, і декодування.

3.1 Алгоритм арифметичного кодування.

/*З кожним наступним символом тексту звертатися */

/*до процедури encode_symbol() */

/*Перевірити, що термінальний символ закодований останнім*/

/*Вивести одержане значення інтервалу [low; high) */

encode_symbol(symbol, cum_freq)

range = high – low

high = low + range*cum_freq[symbol - 1]

low = low + range*cum_freq[symbol]

3.2 Алгоритм арифметичного декодування.

/* Value – це число, яке одержано на вхід*/

/*Звертання до процедури decode_symbol() до того моменту*/

/*поки вона не поверне термінальний символ*/

decode_symbol(cum_freq)

пошук такого символу, що

cum_freq[symbol] <= (value - low) / (high - low) < cum_freq[symbol - 1]

/*це забезпечує розміщення Value в межах нового інтервалу*/

/*[low; high], що відображено в завершенні програми*/

range = high – low

high = low + range*cum_freq[symbol - 1]

low = low + range*cum_freq[symbol]

return symbol

Рисунок 1. Псевдокод арифметичного кодування та декодування.

4. Зауваження до реалізації.

4.1 Прирощувані передача і отримання інформації.

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

4.2 Бажане використання цілочисленої арифметики.

Потрібна для представлення інтервалу [low; high] точність зростає разом з довжиною тексту. Поетапне виконання допомагає вирішити цю проблему, але вимагає при цьому уважного обліку можливого переповнення та від'ємного переповнення.

4.3 Ефективна реалізація моделі.

Реалізація моделі повинна мінімізувати час визначення наступного символу алгоритмом декодування. Крім того, адаптивні моделі повинні також мінімізувати час, який вимагається для підтримання накопичених частот.

5. Реалізація моделі.

Сама реалізація буде обговорюватися в наступному розділі, а тут треба лише торкнутися тільки інтерфейсу з моделлю. Як відомо, байт представляє собою ціле число від 0 до 255 (тип char). Тут ми представляємо байт як ціле число від 1 до 257 включно (тип index), де EOF трактується як 257-й символ. Було б добре відсортувати модель в порядку зменшення частот для мінімізації кількості виконання циклу декодування. Перетворення з типу char в index, та навпаки, реалізовано за допомогою двох таблиць – index_to_char[] i char_to_index[]. В адаптивній моделі виконується перекодування, яке присвоює найчастішим символам маленькі індекси.

Ймовірності представляються в моделі як цілочиселені лічильники частот, а накопичувані частоти зберігаються в масиві cum_freq[]. Як і в попередньому випадку, цей масив – "зворотній", і лічильник загальної частоти, який використовується для нормалізації всіх частот, розміщується в cum_freq[0]. Накопичувані частоти не повинні перевищувати встановленний в Max_frequency максимум, а реалізація моделі повинна запобігати переповненню відповідним маштабуванням. Необхідно також принаймні на 1 забезпечити різницю між двома сусідними значеннями cum_freq[], в противному випадку символ, що переглядається, не буде переданий.

6. Доведення правильності декодування.

Перевіримо правильність визначення процедурою decode_symbol() наступного символу. З псевдокоду на рисунку 1 зрозуміло, що decode_symbol() повинна використовувати Value для пошуку символа, який при кодуванні скоротив робочий інтервал так, що він продовжує включати в себе Value. В робочій програмі в decode_symbol() визначається такий символ, для якого:

cum_freq [symbol]  ((value – low +1)*cum_freq [0]–1)/(high – low + 1)  < cum_freq [symbol - 1], де   означає операцію взяття цілої частини – ділення з відкиданням дробової частини. Показано, що це передбачає:

low +  ((high - low + 1)*cum_freq [symbol]) / cum_freq [0]   value  low +  ((high – low +1)*cum_freq [symbol - 1]) / cum_freq [0], таким чином, що value належить новому інтервалу, який вираховується процедурою decode_symbol(). Це гарантує коректність визначення кожного символу операцієй декодування.

7. Проблема переповнення і завершення кодування.

7.1 Від'ємне переповнення.

Як показано в псевдокоді, аріфметичне кодування працює за допомогою масштабування накопичених ймовірностей, які надаються моделю в інтервалі [low; high] для кожного символу, що передається. Припустимо, що low i high так близькі один до одного, що операція масштабування призводить одержані від моделі різні символи до одного цілого числа, яке входить в [low; high]. В такому випадку подальше кодування продовжувати неможливо. Тому кодувальник повинен слідкувати за тим, щоб інтервал [low; high] завжди був досить широким. Найпростішим засобом для цього є забезпечення ширини інтервалу не меншей Max_frequency – максимального значення суми всіх накопичуваних частот.

Проблема від'ємного переповнення розглядається тільки відносно кодувальника, тому що при декодуванні кожного символу процес крокує за операцієй кодування, і від'мне переповнення не виникне, якщо виконується таке саме масштабування з тими ж самими умовами.

7.2 Переповнення.

Тепер розглянемо можливість переповнення при цілочисленому множенні. Переповнення не виникне, якщо добуток range*Max_frequency вміщується в ціле слово, бо накопичені частоти не можуть перевищувати Max_frequency. Range має найбільше значення в Top_Value + 1, тому максимально можливий добуток є 2^16*(2^14 – 1), яке менше 2^30. Для визначення code_value та range використаний тип long, щоб забезпечити 32-х бітову точність арифметичних обчислень.

7.3 Завершення кодування.

При завершені процесу кодування необхідно послати унікальний термінальний символ (EOF-символ), а потім послати достатню кількістьбітів для гарантії того, що закодований рядок потрапить в підсумковий робочий інтервал. Через те, що процедура done_encoding() може бути "впевнена", що low i high обмежені або так, що:

low < First_qtr < Half  high, або

low < Half < Third_qtr  high,

то значенню треба передати 01 або 10 відповідно, для видалення невизначеності, яка залишилась. Таким чином EOF унікально визначається останніми переданими бітами.

8. Моделі для арифметичного кодування.

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

  • сum_freq [i – 1]  cum_freq [i];

  • Ніколи не робиться спроба кодувати символ і, для якого сum_freq [i – 1] = cum_freq [i];

  • сum_freq [0]  Max_frequency.

Якщо ці умови виконуються, значення в масиві не повинні мати зв'язку з дійснтми значеннями накопичених частот символів тексту. І декодування, і кодування будуть працювати коректно, при чому останньому буде треба менше місця, якщо частоти точні.(Згадаємо успішне кодування "еаіі!" у відповідності до моделі з таблиці 1, як, взагалі, не відображає справжньої частоти в тексті).

8.1 Фіксовані моделі.

Найпростішою моделлю є така модель, в якій частоти символів постійні. Модель з таблиці 1 задає постійні частоти символів для алфавіту {a, e, i, u, o, !}. Для стиску англійських текстів можна використати частоти з частини Свода Брауна. Процедура ініціалізації start_model () просто підраховує накопичену версію цих частот, спочатку ініціалізувавши таблиці перекодування. Швидкість виконання процесу кодування та декодування можна прискорити, якщо ці таблиці перевпорядкувати так, щоб найвживаніші символи розміщувалися на початку масиву cum_freq []. Через те, що модель є постійною, процедура update_model () буде просто пустою.

Loading...

 
 

Цікаве