МЕТОДИ СТИСКУ БАЗИ ДАНИХ

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

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

Тому один із широко застосовуваних методів стиснення полягає в тому, що кожне окреме значення даних замінюється деяким позначенням відмінності між ним і безпосередньо передує йому значенням У цьому полягає метод диференціального стиснення (Differential compression) Але слід зазначити, що для успішного застосування такого методу потрібно, щоб доступ до досліджуваних даних здійснювався послідовно, оскільки, щоб розпакувати будь конкретне значення, необхідно знати безпосередньо передує йому збережене значення Тому метод диференціального стиснення головним чином застосовується в таких ситуаціях, коли доступ до даних повинен завжди здійснюватися послідовно, як у випадку (наприклад) використання елементів одноуровневого індексу Однак необхідно враховувати, що саме у разі індексу може бути передбачено стиск не тільки даних, але і покажчиків, оскільки, якщо логічне впорядкування даних, яким характеризується індекс, є таким же або близьким до фізичного упорядкування файла з даними, то поспіль йдуть значення покажчиків в індексі будуть вельми аналогічними один одному, у звязку з чим може виявитися вигідним і стиснення покажчиків Насправді, індекси майже завжди дозволяють домогтися певного виграшу завдяки використанню стиснення, щонайменше, стосовно до даних, якщо не до покажчиків

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

Roberton Robertson Robertstone Robinson

Припустимо також, що поле прізвищ службовців має довжину 12 символів, тому кожна з цих прізвищ повинна розглядатись (у розпакованому вигляді) як доповнена праворуч відповідною кількістю пробілів Один із способів застосування диференціального стиснення до цього безлічі значень полягає в тому, що символи на початку кожного елементу, що збігаються з символами в попередньому елементі індексу, замінюються числом, що вказує кількість співпадаючих символів Такий метод стиснення називається префіксним стисненням (Front compression) В результаті застосування цього методу до зазначених вище даними, буде отримано наступне (тепер заключні прогалини показані явно за допомогою знаків +)

Про Roberton + + + +

6&nbsp son+++

7&nbsp tone+

3 inson++++

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

Про 7 Roberto

6&nbsp&nbsp&nbsp 2     so

7&nbsp&nbsp&nbsp 1     t

3  1     i

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

Roberto???

?

Robertso??

?

Robertst??

?

Robi??????

?

Безумовно, що така втрата інформації допустима, тільки якщо дані повністю зареєстровані десь в іншому місці (в даному прикладі – у відповідному файлі службовців)

Ієрархічні методи стиснення

Припустимо, що розглянутий файл впорядкований фізично (тобто кластеризувати) за значеннями деякого поля F, і припустимо також, що кожне окреме значення F зустрічається в кількох поспіль йдуть записах цього файлу Наприклад, файл постачальників може бути кластеризувати за значеннями поля міста в цьому випадку будуть зберігатися разом дані про всіх постачальниках з Лондона, з Парижа і тд У такій ситуації може виявитися, що багато всіх записів постачальників, що відносяться до конкретного місту, доцільно представити в стислому вигляді як одну ієрархічну запис, в якій назва розглянутого міста представлено тільки один раз, а за ним слід інформація про номер, імені і статус для кожного постачальника, який в даний час перебуває в цьому місті (Рис Г 18)

Рис Г 18 Приклад ієрархічного стиснення (внутріфайлового)

Записи, показані на рис Г18, складаються з двох частин – з постійної частини (а саме поля міста) і змінної частини (безлічі елементів з даними про постачальників)

Примітка Остання частина називається змінної, оскільки кількість містяться в ній елементів (тобто кількість постачальників в розглянутому місті) залежить від конкретної запису Як було зазначено в розділі 6, така безліч елементів з мінливих кількістю в записі іноді

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

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

Із зазначеного вище випливає, що ієрархічне стиснення в тій формі, яка тут описана, застосовно, тільки якщо файл організований за принципом внутріфайловой кластеризації Але, як уже міг здогадатися читач, аналогічного роду стиснення може також застосовуватися і в разі междуфайловой кластеризації Припустимо, що кластерізовани дані про постачальників і постачаннях, як було вказано наприкінці розділу Г2 це означає, що дані про поставки постачальника S1 безпосередньо слідують за записом з даними про постачальника S1, дані про постачання постачальника S2 – за даними про постачальника S2 і тд А саме, припустимо, що інформація про постачальника S1 і поставки постачальника S1 зберігається на сторінці pi, інформація про постачальника S2 і поставки постачальника S2 – на сторінці р2 і тд У такому випадку може бути застосований метод междуфайлового стиснення, як показано на рис Г 19

Рис Г 19 Приклад ієрархічного стиснення (междуфайлового)

Примітка Хоча метод, що розглядається в даному прикладі, визначений як междуфайловий, фактично він зводиться до обєднання файлів постачальників і поставок в один файл з наступним застосуванням внутріфайлового стиснення до цього єдиного файлу Таким чином, цей варіант фактично не відрізняється від того варіанту, який був показаний на рис Г 18

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

Кодування за методом Хаффмена

Кодування за методом Хаффмена (Huffman coding) [Г39] являє собою метод символьного кодування, який дозволяє в принципі досягти значної ступеня стиснення даних, якщо в них різні символи зустрічаються з різними частотами (що, безумовно, зазвичай і відбувається на практиці), хоча цей метод рідко застосовується в сучасних системах Основна його ідея полягає в наступному: використовується кодування із застосуванням бітових рядків для представлення символів

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

В якості простого прикладу припустимо, що в кодованих даних зустрічаються тільки символи А, в, С, D і Е, а також припустимо, що відносна частота появи цих пяти символів характеризується наведеної нижче таблицею

Символ Е має максимальну частоту і тому йому присвоюється найкоротший код, що складається з одного біта, скажімо, біта 1 Тому всі інші коди повинні починатися з біта 0 і мати довжину не менш 2 бітів (єдиний біт 0 не можна використовувати як коду, оскільки його неможливо буде відрізнити від початкової частини будь-якого іншого коду) Символ А присвоюється код з довжиною на одиницю більше порівняно з найкоротшим кодом, скажімо, 01, тому всі інші коди повинні починатися з 00 Аналогічним чином, символам D, С і в присвоюються коди, відповідно, 001, 0001 і 0000

Вправа Які англійські слова закодовані в наведених нижче рядках

00110001010011

010001000110011

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

0, 3 5 * 1 + 0, 3 0 * 2 + 0, 2 0 * 3 + 0, 1 0 * 4 + 0, 0 5 * 4 = 2, 1 Травня бітів

Якби кожному символу було призначено однакову кількість бітів, як у звичайній схемі кодування символів, то треба було б 3 біта в розрахунку на символ (щоб можна було охопити всі ці пять варіантів)

Г 8 РЕЗЮ МО

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

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

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Індекси (І деякі їх варіанти, включаючи, зокрема, В-дерева) і їх використання як для послідовного, так і для прямого доступу

■ Методи хешування (Включаючи, зокрема, розширюване хешування) та їх застосування для

прямого доступу

Ланцюжки покажчиків (Звані також батьківсько-дочірніми структурами) і їх численні варіанти

У цьому додатку був також описаний цілий ряд методів стиснення

На закінчення слід ще раз підкреслити, що для більшості користувачів цей матеріал найчастіше не представляє (або не повинен представляти) особливого інтересу Єдиним користувачем, який повинен досить докладно вивчити ці відомості, є адміністратор бази даних, що відповідає за фізичне проектування, контроль і налаштування продуктивності Що стосується решти користувачів, то бажано, щоб у процесі роботи у них не виникало потреби в ознайомленні з викладеним тут матеріалом, хоча й не можна не відзначити, що користувачі краще справляються зі своїми обовязками, якщо мають певне уявлення про те, як організовано внутрішнє функціонування системи З іншого боку, що стосується розробників СУБД, то для них, безумовно, стає бажаним або навіть обовязковим оволодіння викладеним тут матеріалом (до того ж знання з цієї теми мають бути у даних фахівців набагато глибшими)

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


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

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*