6. Ущільнення|стиснення| інформації

Ущільнення інформації є операцією, в результаті якої даному коду або повідомленню ставиться у відповідність коротший код або повідомлення¹⁶.

Ущільнення|стиснення| інформації має на меті - прискорення і здешевлення процесів механізованої обробки, зберігання і пошуку інформації, економія пам'яті ЕОМ. При стискуванні|стисненні| слід прагнути до мінімальної неоднозначності стислих код при максимальній простоті алгоритму ущільнення|стиснення|. Розглянемо|розглядуватимемо| найбільш характерні|вдача| методи ущільнення|стиснення| інформації.

Ущільнення інформації діленням коду на частини, менші деякої наперед заданої величини А, полягає в тому, що початковий код ділиться на частини, менші А, після чого отримані частини коду складаються між собою або за правилами двійкової арифметики, або по модулю 2. Наприклад, початковий код 101011010110; A = 4

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

Припустимо, початкове слово «газета» кодується кодом, в якому довжина кодової комбінації букви l = 8:

Грам - 01000111; а - 11110000; з - 01100011; е - 00010111; т - 11011000.

Повний|цілковитий| код слова «Газета»

010001111111000001100011000101111101100011110000.

Ущільнення|стиснення| здійснюється складанням за модулем 2 двійкових кодів букв|літер| стискуваного|стискати| слова з|із| побуквенным| зрушенням|зсувом| в кожному розряді.

рис.1

Допустима кількість розрядів ущільненого коду є|з'являється| цілком|сповна| визначеною величиною, залежною від способу кодування і від ємкості|місткості| ЗУ. Кількість адрес, а відповідно максимальна кількість слів у виділеній ділянці пам'яті машини визначається з|із| наступного|такого| співвідношення

(71)

де - максимально допустима довжина (кількість двійкових розрядів) стислої коди; N - можлива кількість адрес в ЗУ.

Якщо представити|уявляти| процес побуквенного| зрушення|зсуву| в загальному|спільному| вигляді|виді|, як показано на мал. 1, а, те довжина стислої коди

де до - число побуквенных зрушень; - довжина кодової комбінації букви.

Оскільки зрушуються всі букви, окрім першої, то і число зрушень де L - число букв в слові. Тоді

У російській мові найбільш довгі слова мають 23 - 25 букв. Якщо прийняти з умовою здійснення побуквенного зрушення з кожним кроком рівно на один розряд, для n і l можуть бути отримані наступні співвідношення

Якщо значення не задовольняє нерівності (71), можна кінцеві|скінченні| букви|літери| слова складати по модулю 2 без зрушення|зсуву| щодо|відносно| попередньої букви|літери|, як це показано на рис 1, би.

Наприклад, якщо для попереднього прикладу|зразка| із|із| словом “Газета”, стислий код матиме вигляд|вид|:

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

Дуже часто оброблювана інформація буває представлена|уявляти| у вигляді набору однорідних масивів, в яких елементи стовпців або рядків масивів розташовані|схильні| в наростаючому порядку|ладі|. Якщо вважати за старших розряди, розташовані|схильні| лівіше даного елементу, а молодшими - розташовані|схильні| правіше, то можна відмітити|помітити|, що у багатьох випадках рядки матриць відрізняються один від одного в молодших розрядах. Якщо при записі кожного подальшого|наступного| елементу масиву відкидати що все повторюються в попередньому елементи, наприклад в рядку варті підряд елементів старших розрядів, то масиви можуть бути скорочені від 2 до 10 і більш за розряди.

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

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

Згорнутий масив матиме вигляд|вид|:

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

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

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

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

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

Якщо в рядку масиву декілька ділянок, що повторюються, то можна замість вставляти спеціальні символи, вказуючі|показуючі| на необхідне число пропусків.

Наприклад, якщо позначити кількість пропусків, відповідно, Х - 2; Y - 3; Z - 5, то початковий і згорнутий масиви матимуть вигляд:

Процес розгортання масиву здійснюється таким чином: довжина рядка відома, кількість пропусків визначається символами X, Y, Z

Пропущені цифри заповнюються по аналогічних розрядах попереднього рядка. Умовою переходу на наступний|такий| рядок є|з'являється| заповнення попереднього рядка.

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

Для розміщення в пам'яті ЕОМ М код, в яких найбільше з кодованих чисел рівне N, необхідний об'єм пам'яті

Із зростанням N довжина кодової комбінації ростиме як . Для економії об'єму пам'яті Q, число де вираз в дужках - закруглене значення до найближчого цілого числа, розбивають на L рівних частин. Максимальне число в отриманому інтервалі чисел буде не більше . Величина визначає розрядність чисел, що зберігаються, об'єм пам'яті для їх зберігання буде не більший . Якщо в пам'яті ЕОМ зберігати адреси меж відрізань і порядкові номери чисел, що зберігаються, відлічуваних від чергової межі, то визначає розрядність чисел для виразу номера межі (у останньому інтервалі має бути хоч би одне число); об'єм пам'яті для зберігання номерів меж буде _

(72)

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

¹⁷ (73)

Якщо підставити значення у вираз (72), то отримаємо. значення об'єму пам'яті при оптимальній кількості зон, на, які розбиваються числа, що зберігаються в пам'яті ЕОМ

(74)

Для значень при обчисленнях|підрахунках| можна користуватися наближеною формулою

(75)

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

Потім визначають, в якому саме з інтервалів знаходиться шукане число х

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

Завдання 7.1:. Визначити допустиму кількість слів, адреси яких можуть зберігати в ЗУ, якщо максимальна довжина кодованих слів L=15, а двійковий код букв – п'ятизначний.

Рішення|розв'язання|:

Завдання 7.2:. Визначити допустиму кількість зрушень при стискуванні восьмирозрядних кодових комбінацій, якщо допустима довжина стислої коди n_макс=12.

Рішення|розв'язання|:

Завдання 7.3. Використовуючи знак розділу р, скрутити наступний масив чисел:

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

Рішення|розв'язання|:

1 9 7 1 1 3 7 4 3 0

1 2 0 1 2