Стиснення даних по методу Лемпеля-Зіва

16

Стиснення даних по методу Лемпеля-Зіва

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

Одна з реалізацій цієї ідеї включає наступні операції. Спочатку кожному символу алфавіту привласнюється певний код (коди - порядкові номери, починаючи з 0). При кодуванні:

1. Вибирається перший символ повідомлення і замінюється на його код.

2. Вибираються наступні два символи і замінюються своїми кодами. Одночасно цій комбінації двох символів привласнюється свій код. Звично це номер, рівний числу вже використаних кодів. Так, якщо алфавіт включає 8 символів, що мають коди від 000 до 111, то перша двосимвольна комбінація одержить код 1000, наступна - код 1001 і т.д.

3. Вибираються з початкового тексту чергові 2, 3,...N символів до тих пір, поки не утворюється комбінація, що ще не зустрічалася. Тоді цій комбінації привласнюється черговий код, і оскільки сукупність А з перших N-1 символів вже зустрічалася, то вона має свій код, який і записується замість цих N-1 символів. Кожен акт введення нового коду назвемо кроком кодування.

4. Процес триває до вичерпання початкового тексту.

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

Скільки двійкових розрядів потрібно виділяти для кодування? Відповідь може бути наступною: число розрядів R на кожному кроці кодування дорівнює числу розрядів в найдовшому з використаних кодів (тобто числу розрядів в останньому використаному порядковому номері). Тому якщо останній використаний код (порядковий номер) дорівнює 13 = 1101, то коди А всіх комбінацій повинні бути чотирьохрозрядними при кодуванні аж до появи номера 16, після чого всі коди символів починають розглядатися як п'ятирозрядні (R = 5).

Приклад. Хай початковий текст є двійковим кодом (перший рядок таблиці 1), тобто символами алфавіту є 0 і 1. Коди цих символів відповідно також 0 і 1. Лемпеля-Зіва код (LZ-код), що утворюється по методу, показаний в другому рядку таблиці 1. У третьому рядку відмічені кроки кодування, після яких відбувається перехід на представлення кодів А збільшеним числом розрядів R. Так, на першому кроці вводиться код 10 для комбінації 00 і тому на наступних двох кроках R=2, після третього кроку R = 3, після сьомого кроку R = 4, тобто в загальному випадку R = K після кроку 2K-1-1.

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

Таблиця 1

Початковий текст	0.00.000. 01. 11. 111.1111. 110. 0000.00000. 1101. 1110.
LZ-код	0.00.100.001.0011.1011.1101.1010.00110.10010.10001.10110.
R	2 3 4
Коди, що вводяться	- 10 11 100 101 110 111 1000 1001 1010 1011 1100

У іншій відомій реалізації LZ-методу будь-яка послідовність, що раніше зустрічалася, в стислому тексті є сукупністю наступних даних:

номер першого символу в послідовності, що раніше зустрічалася;

число символів в послідовності;

наступний символ в поточній позиції кодованого тексту.

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

Важливим поняттям при роботі з інформацією є класифікація об'єктів.

Класифікація система розподілу об'єктів (предметів, явищ, процесів, понять) по класах відповідно до певної ознаки

Під об'єктом розуміється будь-який предмет, процес, явище матеріальної або нематеріальної властивості. Система класифікації дозволяє згрупувати об'єкти і виділити певні класи, які характеризуватимуться рядом загальних властивостей. Класифікація об'єктів ? то процедура групування на якісному рівні, направлена на виділення однорідних властивостей. Стосовно інформації як до об'єкту класифікації виділені класи називають інформаційними об'єктами.

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

інформація про студентів ? у вигляді інформаційного об'єкту “Студент”;

інформація про викладачів ? у вигляді інформаційного об'єкту “Викладач”;

інформація про факультети ? у вигляді інформаційного об'єкту “Факультет” і т.п.

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

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

Приклад. Інформація про кожного студента у відділі кадрів університету систематизована і представлена за допомогою однакових реквізитів:

прізвище, ім'я, по батькові;

стать;

рік народження;

місце народження;

адреса мешкання;

факультет, де проходить навчання студент, і т.д.

Всі перераховані реквізити характеризують властивості інформаційного об'єкту “Студент”.

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

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

Алгоритм обробки інформаційних об'єктів фірми дозволяє одержати інформацію про об'єми продажів, про прибуток, замовників, види вироблюваної продукції і т.д.

Алгоритми обробки в тому і іншому випадку переслідують різні цілі, обробляють різну інформацію, реалізуються різними способами.

При будь-якій класифікації бажано, щоб дотримувалися наступні вимоги:

1. Повнота обхвату об'єктів даної області;

2. Однозначність реквізитів;

3. Можливість включення нових об'єктів.

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

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

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

Приклад. Як ознака класифікації вибирається вік, який складається з трьох значень: до 20 років, від 20 до 30 років, понад 30 років.

Відомо три системи класифікації об'єктів: ієрархічна, фасетна, дескрипторна. Ці системи розрізняються різною стратегією застосування класифікаційних ознак. Розглянемо основні ідеї створення цих систем класифікації.

Ієрархічна система класифікації

Ієрархічна система класифікації рис. 11 будується таким чином:

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

кожен клас 1-го рівня відповідно до свого, характерного для нього класифікаційною ознакою ділиться на підкласи, які утворюють 2-й рівень;

кожен клас 2-го рівня аналогічно ділиться на групи, які утворюють 3-й рівень і т.д.



Ієрархічна система класифікації

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

Звернемо увагу на те, що у ієрархічній системі класифікації через жорстку структуру особлива увага слідує приділити вибору класифікаційних ознак.

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

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

Достоїнства ієрархічної системи класифікації:

1. Простота побудови;

2. Використання незалежних класифікаційних ознак в різних гілках ієрархічної структури.

Недоліки ієрархічної системи класифікації:

1. Жорстка структура, яка приводить до складності внесення змін, оскільки доводиться перерозподіляти всі класифікаційні групування;

2. Неможливість групувати об'єкти по наперед не передбачених поєднаннях ознак.

Приклад. Поставлена задача створити ієрархічну систему класифікації для інформаційного об'єкту “Факультет”, яка дозволить класифікувати інформацію про всіх студентів по наступних класифікаційних ознаках: факультет, на якому він вчиться, віковий склад студентів, підлога студента, для жінок наявність дітей. Система класифікації представлена на рис. 12 і має наступні рівні:

0-й рівень. Інформаційний об'єкт “Факультет”;

1-й рівень. Вибирається класифікаційна ознака ? назва факультету, що дозволяє виділити декілька класів з різними назвами факультетів, в яких зберігається інформація про всіх студентів;

2-й рівень. Вибирається класифікаційна ознака ? вік, який має три градації: до 20 років, від 20 до 30 років, понад 30 роки. По кожному факультету виділяються три вікові підкласи студентів;

3-й рівень. Вибирається класифікаційна ознака ? стать. Кожен підклас 2-го рівня розбивається на дві групи. Таким чином, інформація про студентів кожного факультету в кожному віковому підкласі розділяється на дві групи - чоловіків і жінок;

4-й рівень. Вибирається класифікаційна ознака ? наявність дітей у жінок: є, ні.

Створена ієрархічна система класифікації має глибину класифікації, рівну чотирьом.



Приклад ієрархічної системи класифікації для інформаційного об'єкту “Факультет”

Фасетна система класифікації

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

Приклад. Фасета колір містить значення: червоний, білий, зелений, чорний, жовтий.

Фасета спеціальність містить назви спеціальностей.

Фасета освіту містить значення: середнє, середнє спеціальне, вище.

Схема побудови фасетної системи класифікації у вигляді таблиці відображена на рис. 13. Назви стовпців відповідають виділеним класифікаційним ознакам (фасетам), позначеним Ф1, Ф2,..., Фi,..., Фn. Наприклад, колір, розмір одягу, вага і т.д. Вироблена нумерація рядків таблиці. У кожній клітці таблиці зберігається конкретне значення фасета. Наприклад, фасета колір, позначена Ф2, містить значення: червоний, білий, зелений, чорний, жовтий.

Фасетна система класифікації

Фасети
Значення фасет		Ф1	Ф2	Ф3	...	Фі	...	Фn
	1	.	.	.	...	.	...	.
	2	.	.	.	...	.	...	.
	...	...	...	...	...	...	...	...
	k	.				.

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

Ks = (Ф1, Ф2,..., Фi,..., Фn), де Фi i-й фасет; n кількість фасет.

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

Достоїнства фасетної системи класифікації:

1. Можливість створення великої місткості класифікації, тобто використовування великого числа ознак класифікації і їх значень для створення груп;

2. Можливість простої модифікації всієї системи класифікації без зміни структури існуючих груп.

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

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

Згрупуємо і представимо у вигляді таблиці (рис. 14) всі класифікаційні ознаки по фасетах:

фасета назва факультету з п'ятьма назвами факультетів;

фасета вік з трьома віковими групами;

фасета стать з двома градаціями;

фасета діти з двома градаціями.

Приклад фасетної системи класифікації для інформаційного об'єкту “Факультет”

Структурну формулу будь-якого класу можна представити у вигляді:

Kс = (Факультет, Вік, Стать, Діти)

Привласнюючи конкретні значення кожному фасету, одержимо наступні класи:

К1 = (Радіотехнічний факультет, вік до 20 років, чоловік, є діти);

K2 = (Комерційний факультет, вік від 20 до 30 років, чоловік, дітей немає);

К3 = (Математичний факультет, вік до 20 років, жінка, дітей немає) і т.д.

Дескрипторна система класифікації

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

Суть дескрипторного методу класифікації полягає в наступному:

відбирається сукупність ключових слів або словоз'єднань, що описують певну наочну область або сукупність однорідних об'єктів. Причому серед ключових слів можуть знаходитися синоніми;

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

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

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

Між дескрипторами встановлюються зв'язки, які дозволяють розширити область пошуку інформації. Зв'язки можуть бути трьох видів:

3. Синонімічні, які вказують деяку сукупність ключових слів як синонімів;

4. Родо-видові, що відображають включення деякого класу об'єктів в більш представницький клас;

3. Асоціативні, які сполучають дескриптори, що мають загальні властивості.

Приклад. Синонімічний зв'язок: студент-той, що навчається. Родовидовий зв'язок: университет-факультет-кафедра. Асоціативний зв'язок: студент-экзамен-профессор-аудиторія.

Система класифікаційного кодування

Класифікаційним кодуванням називається процедура привласнення об'єкту кодового позначення.

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

Система класифікаційного кодування сукупність правил кодового позначення об'єктів.

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

довжиною число позицій в коді;

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

Можна виділити дві групи методів, використовувані в системі класифікаційного кодування (рис. 15), які утворюють:

власне класифікаційну систему кодування, орієнтовану на проведення попередньої класифікації об'єктів або на основі ієрархічної системи, або на основі фасетної системи;

реєстраційну систему кодування, яка не вимагає попередньої класифікації об'єктів. Розглянемо представлені на рис. 15 системи кодування у відповідності до різних методів, які використовуються при цьому.

Власне класифікаційне кодування застосовується після проведення класифікації об'єктів. Розрізняють послідовне і паралельне кодування.

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

Система кодування, яка використовує різні методи кодування

Послідовна система кодування володіє тими ж достоїнствами і недоліками, що і ієрархічна система класифікації.

Приклад. Проведемо кодування інформації, класифікованої за допомогою ієрархічної схеми (див. рис. 14). Кількість кодових груп визначатиметься глибиною класифікації і дорівнює 14, Перш ніж почати кодування, необхідно визначитися з алфавітом, тобто які використовуватимуться символи. Для більшої наочності виберемо десяткову систему числення 10 арабських цифр. Аналіз схеми на рис. 4 показує, що довжина коду визначається 4 десятковими розрядами, а кодування груп на кожному рівні можна робити шляхом послідовної нумерації зліва направо. У загальному вигляді код можна записати як ХХХХ, де Х значення десяткового розряду. Розглянемо структуру коду, починаючи із старшого розряду:

1-й (старший) розряд виділений для класифікаційної ознаки “назва факультету” і має наступні значення: 1 комерційний; 2 інформаційні системи; 3 для наступної назви факультету і т.д.;

2-й розряд виділений для класифікаційної ознаки “вік” і має наступні значення: 1 до 20 років; 2 від 20 до 30 років; 3 понад 30 роки;

3-й розряд виділений для класифікаційної ознаки “стать” і має наступні значення: 1 чоловіки; 2 жінки;

4-й розряд виділений для класифікаційної ознаки “наявність дітей у жінок” і має наступні значення; 1 є діти; 2 немає дітей, 0 для чоловіків, оскільки подібної інформації не вимагається.

Прийнята система кодування дозволяє легко розшифрувати будь-який код групи, наприклад:

1310 студенти комерційного факультету, понад 30 роки чоловіки;

2221 студенти факультету інформаційних систем, від 20 до 30 років, жінки мають дітей.

Паралельне кодування використовується для фасетної системи класифікації. Суть методу полягає в наступному: всі фасети кодуються незалежно один від одного; для значень кожного фасета виділяється певна кількість розрядів коду. Паралельна система кодування має ті ж достоїнства і недоліки, що і фасетна система класифікації.

Приклад. Проведемо кодування інформації, класифікованої за допомогою фасетної схеми (див. рис. 15). Кількість кодових груп визначається кількістю фасетів і дорівнює 4. Виберемо десяткову систему числення як алфавіт кодування, що дозволить для значень фасетів виділити один розряд і матиме довжину коду, рівну 4. На відміну від послідовного кодування для ієрархічної системи класифікації в даному метолі не має значення порядок кодування фасетів. У загальному вигляді код можна записати як ХХХХ, де Х значення десяткового розряду. Розглянемо структуру коду, починаючи із старшого розряду:

1-й (старший) розряд виділений для фасета “стать” і має наступні значення: 1 чоловіки; 2 жінки;

2-й розряд виділений для фасета “наявність дітей у жінок” і має наступні значення: 1 є діти; 2 немає дітей; 0 для чоловіків, оскільки подібної інформації не вимагається;

3-й розряд виділений для фасета “вік” і має наступні значення: 1 до 20 років; 2 від 20 до 30 років; 3 понад 30 роки;

4-й розряд виділений для фасета “назва факультету” і має наступні значення 1 радіотехнічний, 2 інформаційної безпеки, 3 авіа будівельний; 4 льотний; 5 навігаційний і т.д.

Прийнята система кодування дозволяє легко розшифрувати будь-який код групи, наприклад:

2135 жінки у віці понад 30 роки, що мають дітей і є студентами математичного факультету;

1021 чоловіки віку від 20 до 30 років, що є студентами радіотехнічного факультету.