Матеріали для Нової української школи 1 клас - планування, розробки уроків, дидактичні та методичні матеріали, підручники та зошити

ОБРОБКА І ПЕРЕДАЧА ІНФОРМАЦІЇ. СУЧАСНІ КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ - Золота колекція рефератів - 2018

СТИСКАННЯ ІНФОРМАЦІЇ

ВСТУП

У процесі прискореної комп’ютеризації суспільства обсяги даних, збережених па машинних носіях, швидко зростають. Ще зовсім нещодавно вони вимірялися кілобайтами й мегабайтами, а тепер — гігабайтами й більшими одиницями. Природним є бажання зберігати ці дані гранично компактно. Причому цікавими є оборотні методи, що усувають надмірність інформації при стисканні й відновлюють її при розтискати. Описані в методичних вказівках методи оборотні.

Об’єктами стискання є:

— числові дані;

— упорядковані текстові дані (словники);

— спеціальні тексти формалізованими мовами;

— природно-мовні тексти загального виду;

— структуровані дані.

Як кількісна міра стискання використовується коефіцієнт стискання — відношення довжини первісного до стиснутого тексту, а також тривалість необхідних перетворень.

ТЕОРЕТИЧНА ЧАСТИНА

1.1 Стискання числових даних

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

Суть різницевого кодування полягає в зберіганні замість абсолютних значень різниць двох суміжних чисел або відхиленні чисел від їхнього середнього значення. Наприклад, для послідовності чисел 2, 14, 18, 27, 34 перший спосіб дасть послідовність 2, 12, 4, 9, 7. Другий спосіб породжує послідовність: -17, -5, -1, 8, 15 (середнє значення для вихідної послідовності — 19).

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

Кодування повторень полягає в заміні ланцюжка однакових символів кодом цього числа й числом повторень. Наприклад, для послідовності 5555 6666 888888 застосування цього способу дасть послідовність 5(4) 6(4) 8(6).

Видалення незначних нулів означає відкидання нулів у старших розрядах цілої частини числа й у молодших розрядах дробової частини. Наприклад, застосування цього способу стискання до послідовності 0010 01,100 011 011 дасть послідовність 10 1,1 1111.

1.2 Стискання словників

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

Наприклад, словник

обчислювач

обчислювальний

обчислювати у результаті розглянутого способу кодування буде замінений словником:

обчислювач

11ний

бять.

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

Наприклад, словник

зустрічаючись

замінюючи

за допомогою цього способу стискання заміниться на сукупність словників:

основний допоміжний

зустрічаїсь 1-ючи

заміню 1

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

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

1.3. Стискання спеціальних текстів

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

Для цього типу інформації придатні методи, описані в н. 1.5. Одночасно специфіка цих текстів дозволяє здійснити ощадливе зберігання, що грунтується на виділенні довгих часто повторюваних фрагментів. Наприклад, текст Фортран-нрограми

TYPE *,’ФОРТРАН’

TYPE ’ПРОГРАМА’

може бути представлений з використанням колового словника:

програма словник

1,’ФОРТРАН’ 1 - TYPE *

1, ’ ПРОГРАМА’

1.4. Стискання структурованих даних

Структуровані дані містять текстову й іншу інформацію й зберігаються в певному форматі, прийнятному для тих або інших прикладних завдань, наприклад для документального або фактографічного пошуку інформації. Приклад структурованих даних — бібліографічні описи.

Різнорідність даних структурованого типу обумовлює різні типи інформаційної надмірності, тому необхідно використовувати комбінацію методів, пристосованих до своїх підгруп даних. Так, для числових полів доцільно застосовувати методи п. 1.1, для текстових — описані в п. 1.5. За деякими оцінками комбінація цих методів дає скорочення обсягу даних в 1,5-4 рази, за іншими оцінками — навіть в 6 разів.

У структурованих даних поряд з типами інформаційної надмірності, характерними для текстових або нетекстових даних, існує особливий позиційний тип надмірності. Він пов’язаний з дублюванням інформації для ідентифікації структури даних.

Наприклад, якщо записи файлу мають структуру:

П. І. Б. студента

ставлення до військового обов’язку

домашня адреса

спеціальність

оцінки за сесію,

причому поля мають довжину, відповідного, 20,50,15,10 байт, то при різних значеннях тих або інших полів для конкретних студентів частина ділянки пам’яті, що відводиться під окремі поля, не буде використовуватися. Тоді, якщо поле «Ставлення до військового обов’язку» порожнє, його можна виключити з конкретного запису, і весь запис матиме такий вигляд:

(П. І. Б. студента)1 (домашня адреса)3 (спеціальність)4 (оцінки за сесію)5 де індекси означають приналежність того або іншого значення до відповідного поля.

1.5. Стискання текстової інформації загального виду

Принципова можливість стискання текстової інформації пов’язана з тим, що складники тексту — букви й словоформи — різняться за частотою вживання в тексті, тоді як їхні довжини слабко пов’язані з частотою.

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

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

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

Семантично незалежні методи стискання у свою чергу можна розділити на ті, які не використовують, і ті, які використовують апріорні відомості про статистику тексту. Відповідно до цього існують два типи алгоритмів стискання: одно- і двофазні, які будемо називати відповідно адаптивними й статистичними.

Семантично залежні методи не використовують для стискання ніяких апріорних відомостей про статистику тексту. Кодування здійснюється в процесі однократного сканування тексту. Воно зводиться до заміни ланцюжків символів тексту па убудовані покажчики, адресовані до тієї частини тексту, де такі ланцюжки вже зустрічалися. У цьому випадку кажуть про внутрішню адресацію, а самі методи називаються адаптивними.

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

1.5.1. Адаптивні алгоритми

Будують код постійної довжини для фрагментів змінної довжини.

Стискають текст у процесі однократного його сканування. Кодування полягає в знаходженні повторюваних ділянок тексту й заміні кожної ділянки покажчиком, адресованим до тієї частини тексту, де така ділянка вже зустрічалася. Для декодування в цьому випадку кодової таблиці не потрібно. Як покажчик може використовуватися структура (т, n), де т — кількість символів назад або вперед по тексту, перемістившись на які можна знайти подібний фрагмент тексту; n — довжина фрагмента в символах.

Існує два типи убудованих покажчиків, що вказують на попередні або наступні ділянки. Алгоритми, що використовують покажчики «назад», можуть працювати з безперервним вхідним потоком даних, генеруючи безперервний вихідний потік стиснутої інформації. На кожному кроці алгоритму вхідний текст заповнює буфер фіксованої довжини, усередині якого здійснюється ідентифікація однакових підрядків максимально можливої довжини. При знаходженні двох таких підрядків другий заміняється покажчиком, адресованим у початок першої.

Алгоритми з покажчиками вперед «можуть» працювати лише з текстами фіксованої довжини, оскільки вимагають зворотного скапування тексту. Тут також використовується пошук однакових підрядків у буфері змінної довжини з уже закодованим текстом.

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

Коефіцієнт стискання текстових даних цим методом лежить у межах 1,8-2,5.

1.5.2. Статистичні алгоритми

1.5.2.1. Кодування фрагментів фіксованої довжини

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

пробіл 0,174 и 0,016

о 0,080 з 0,016

е,ë 0,071 ъ 0,014

а 0,061 ь 0,014

и 0,061 б 0,014

т 0,052 г 0,013

м 0,052 ч 0,012

с 0,045 й 0,010

р 0,040 у 0,009

в 0,038 ж 0,007

л 0,035 ю 0,006

к 0,028 ш 0,006

н 0,026 ц 0,003

д 0,025 щ 0,003

п 0,023 э 0,003

у 0,021 ф 0,002

я 0,018 х 0,002

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

Надлишковість інформації полягає в кореляції між символами (словами). Метод Хаффмена зберігає цю надлишковість. Існують модифікації методу, що дозволяють урахувати взаємозалежності. Найпростіша з них використовується, коли всі символи можна розділити на невелику кількість груп із сильною кореляцією усередині груп і слабкою — між ними. Це іноді має місце для числових і буквених символів тексту.

До інших недоліків хаффменівських методів належить відносна складність декодування — необхідність аналізу бітової структури префіксних кодів, що сповільнює процес декодування.

Подальшим розвитком методу Хаффмена є арифметичні коди. Вони походять із так званих конкатенацій них, або блокових, кодів. Суть їх полягає в тому, то вихідний код генерується для ланцюжка вхідних символів фіксованої довжини без урахування міжсимвольних кореляцій. В основі методу лежить представлення ймовірності кожного ланцюжка К вхідних символів (А1, А2,... Ак) у вигляді числа, одержуваного як сума К доданків виду

р(А,)р(А2)...р(А1-2)Р(А1), і = = 1, 2, 3…k, S = А1 + А2K, де p(S) - ймовірність символу S.

P(S) — кумулятивна ймовірність символу S, то дорівнює сумі ймовірностей усіх символів Аі, для яких р(Аі) більше p(S).

1.5.2.2. Кодування фрагментів змінної довжини

Іншою формою словника може бути словник фрагментів змінної довжини. Словники фрагментів змінної довжини будуються зі словоформ, які виділяються в тексті за природними роздільниками — пробілами і знаками пунктуації. Потім розраховуються частоти кожної словоформи як відношення кількості її повторень до загальної кількості словоформ. Використовуючи ці частоти, застосовують метод Хаффмена або Шеннона-Фано для кодування словоформ кодом змінної довжини.

1.6. Методи стискання даних

1.6.1. Метод Шеннона-Фано

Знаки впорядковуються у порядку зростання їхніх частот і утворюють часткові суми Si = Σpj (j = 1, 2, 3,……і), де pj — частота j-гo знака. Далі процес розбивається на кілька кроків. У першому кроці стовпчик знаків розсікається на дві частини гак, щоб часткова сума перетину була близька до 0,5. Процес розподілу підстовпчиків повторюється так, щоб щоразу часткова сума в точці перетину виявлялася ближче до середнього арифметичного часткових сум на нижньому й верхньому краях поділюваного підстовпчика. При кожній розбивці елементам верхньої частини ставиться у відповідність 1, нижній — 0.

Наприклад: нехай

1.6.2. Метод Хаффмена

Знаки впорядковуються у порядку зростання частоти. Два найбільш рідкісні знаки об’єднуються в один клас, і їхні частоти складаються. Отримані частоти перевпорядковуються, і процес повторюється доти, поки всі знаки не будуть об’єднані в один клас.

Наприклад:

Тоді коди вихідних символів (вони «збираються» з часткових кодів додаткових позначень — F, G, Н — у зворотному щодо ходу кодування порядку):

Вихідні

символи

Коди

Пояснення

А

100

(А ввійшов у F з кодом 0; F увійшов у Н з кодом 0; в Н код 1. Тоді зворотний порядок — 100)

В

101

(В увійшов у F з кодом 1; F увійшов у Н з кодом 0; в 11 код 1. Тоді зворотний порядок — 101)

С

00

(С увійшов у G з кодом 0; у G код 0)

D

01

(D увійшов у G з кодом 1; у G код 0. Тоді зворотний порядок — 01)

Е

11

(Е увійшов у Н з кодом 1, у Н код 1)









загрузка...