Проблема від’ємного переповнення розглядається тільки відносно кодувальника, тому що при декодуванні кожного символу процес крокує за операцієй кодування, і від’мне переповнення не виникне, якщо виконується таке саме масштабування з тими ж самими умовами.
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 () буде просто пустою.
Строгою моделлю є така модель, в якій частоти символів тексту точно відповідають специфікації моделі. Наприклад, фіксована модель з програми близька до строгої моделі для деякого фрагмента з Свода Брауна, звідки її було взяти. Однак, для того, щоб бути істино строгою, її символи в цьому фрагменті, які не з’являються, повинні мати лічильники, що дорівнюють 0, а не 1 (і при цьому “жертвувати” можливостями вхідних текстів, які містять ці символи). Крім того, лічильники не повинні масштабуватися до заданої накопиченої частоти, як це зроблено в програмі. Взагалі, строга модель повинна бути вирахована й передана перед пересиланням власне тексту. Клірі і Уітнен показали, що при загальних умовах це не дасть загального покращення стиску порівняно з описаним нижче адаптивним кодуванням.
8.2 Адаптивна модель.
Вона змінює частоти вже знайдених в тексті символів. Спочатку всі лічильники можуть бути рівними, що відображує відсутність початкових даних, але при перегляді кожного вхідного символу вони змінюються, наближуючись до спостережуваних частот. І кодувальник, і декодувальник використовують однакові початкові значення (наприклад, рівні лічильники) і один і той самий алгоритм оновлення, що дозволить їх моделям завжди залишатися на одному рівні. Кодувальник отримує наступний символ, кодує його та змінює модель. Декодувальник з’ясовує наступний символ на основі своєї поточної моделі, а потім оновлює її.
Програма демонструє таку адаптивну модель, що рекомендується для використання при стиску та відновленні, оскільки на практиці вона є кращою ніж фіксована модель за ефективністю стиску. Ініціалізація проводиться таким саме чином, як для фіксованої моделі, за виключенням того, що всі частоти встановлюються в нулі. Процедура update_model (symbol), викликається з encode_symbol () та decode_symbol () після обробки кожного символу.
Оновлення моделі є досить дорогим з причини необхідності підтримки накопичених сум. В програмі використані лічильники частот, які оптимально розміщені в масиві в порядку зменшення своїх значень, що є ефективним видом самоорганізованого лінійного пошуку. Процедура update_model () спочатку перевіряє нову модель на предмет перевищення нею обмежень за величиною накопиченої частоти, і якщо воно присутнє, то зменшує всі частоти діленням на 2, зважаючи при цьому на те, щоб лічильники не перетворилися в 0, і переобчислює накопичені значення. Потім, якщо це необхідно, update_model () перевпорядковує символи для того, щоб розмістити поточний в його вірній категорії відносно частотного порядку, чергуючи для відображення змін перекодувальні таблиці. В результаті, процедура збільшує значення відповідного лічильника частоти і впорядковує відповідні накопичені частоти.
9. Ефективність стискання.
Взагалі, при кодуванні тексту аріфметичним методом, кількість бітів в закодованому рядку дорівнює ентропії цього тексту відносно використаної для кодування моделі. Три чинника викликають погіршення цієї характеристики: видатки на завершення тексту; використання арифметики з кінцевою точністю; таке масштабування лічильників, що їх сума не перевищує Max_frequency.
Як було показано, жоден з них не є значним. В порядку виділення результатів арифметичного кодування, модель буде розглядатися як сувора (в визначеному вище сенсі).
Арифметичне кодування повинне досилати додаткові біти в кінець кожного тексту, здійснюючи таким чином додаткові зусилля на завершення тексту. Для ліквідації непорозуміння з останнім символом процедура done_encoding () посилає два біти. В випадку, коли перед кодуванням поток бітів має блокуватися в 8-бітові символи, буде необхідно завершувати до кінця блоку. Таке комбінування може додатково потрібувати 9 бітів.
Видатки при використанні арифметики з обмеженою точністю проявляються в зменшені залишків при діленні. Це видно при порівнянні з теоретичною ентропією, яка виводить частоти із лічильників, які таким саме чином масштабуються при кодуванні. Тут видатки незначні – порядку 10^-4 бітів / символ. Додаткові видатки на масштабування лічильників дещо більші, але все одно досить малі. Для коротких текстів (менших 2^14 байт) їх немає. Але навіть з текстами в 10^5 – 10^6 байтів накладні видатки, підраховані експериментально, складають менше 0,25% від рядка, шо кодується.
Завантажити реферат