А.Ф. Оськін, В.І. Зграєю
Нинішній етап розвитку історичної науки, як і науки взагалі, характеризується все зростаючим потоком інформації. Обробку великих обсягів інформації за допомогою комп'ютера не можна ефективно організувати тільки шляхом вдосконалення технічних засобів - збільшуючи обсяги пам'яті, скорочуючи час звернення до зовнішніх носіїв, тощо. Необхідно удосконалювати також і методи організації інформації, розробляючи ефективні алгоритми її кодування.
Що ж таке інформація? Одне з можливих визначень цього поняття розглядає інформацію, як "зміст зв'язку між взаємодіючими матеріальними об'єктами, що проявляється в зміні стану цих об'єктів" [1].
Цікаво відзначити, що в теорії інформації відсутня суворе визначення поняття "інформація". Необхідною і достатньою умовою побудови цієї теорії виявилося введення поняття кількості інформації.
Як же визначають кількість інформації? У класичній теорії інформації ігноруються цінність, терміновість і смисловий зміст інформації, тобто не приймаються в розрахунок якісні характеристики повідомлень. Коли ж не враховуються якісні характеристики, то має сенс говорити не про кількість інформації, а про її обсяг. Слід зазначити, що з цієї точки зору історична інформація має ряд особливостей. Для історика досить важливим є завдання створення і збереження в машиночитаному архіві найбільш повної електронної копії наративного джерела. Якщо врахувати складність і неоднорідність інформації, характерні для історичного джерела, а також швидко збільшується кількість архівів, що зберігають інформацію в електронній формі, актуальною стає задача розробки принципів зберігання інформації. При цьому вельми важливим є пошук шляхів якісного поліпшення методів кодування і зберігання інформації.
Розгляду одного з таких методів і присвячена ця стаття. Надалі під інформацією ми будемо розуміти набори числових даних, оскільки збереженим чином будь-якого джерела може бути число або безліч чисел. При цьому під кількістю інформації ми будемо мати на увазі її обсяг, тобто кількість байтів пам'яті, необхідних для запису елементів числових множин.
Більшість використовуваних в даний час методів кодування грунтується на обліку статистичної інформації про кодованої множині. У роботі В.А. Амелькін [2] наведена одна з можливих класифікацій методів кодування. Відповідно до цієї класифікації, виділяються такі групи методів:
упаковки (код Бодо);
статистичні методи;
алгоритмічне та комбінаторне кодування.
Методи упаковки.
Як показано в тій же роботі, для кодування множини A, що складається з p елементів, при використанні рівномірного двійкового коду, довжина S кодових повідомлень дорівнює:
S = [log (p)] + 1 (1)
При кодуванні інформації за методом Бодо у вихідній матриці X = відшукується максимальний елемент, для якого відповідно до формули (1)
So = [log (max (xi, j))] + 1 (2)
розраховується необхідний для його зберігання число двійкових розрядів. При цьому, для зберігання кожного елементу таблиці xi, j відводиться So двійкових розрядів. Для зберігання всієї таблиці необхідно (n * m * So) двійкових одиниць. (Тут n-число рядків, а m-число стовпців початкової матриці).
Існують модифікації цього методу, що дозволяє підвищити ступінь упаковки. До недоліків методу слід віднести те, що він ефективний лише на матрицях спеціального виду з незначними відмінностями за абсолютним значенням всередині рядка і значного - всередині стовпців (або навпаки).
Статистичні методи.
У цю групу входять методи, засновані на обліку статистичних даних про кодованої множині. Історично першим у цій групі був код Морзе.
У 1948-49 р.р. відразу двома дослідниками Шенноном і Фано незалежно один від одного був запропонований метод кодування, заснований на обліку умовних ймовірностей появи повідомлень. При цьому повідомленнями, що має більшу ймовірність ставилися у відповідність більш короткі кодові повідомлення, ніж сполученні, мають меншу ймовірність.
Ідеї статистичного кодування отримали свій подальший розвиток у роботах Хаффмена. Код Хаффмена більш ефективний ніж Шеннона-Фано і в даний час широко використовується при побудові різноманітних программупаковщіков.
Алгоритмічне і комбінаторне кодування.
Основна ідея комбінаторного кодування полягає в завданні безлічі кодованих повідомлень не шляхом перерахування всіх елементів множини, а шляхом визначення процедури обчислення номери для деякого повідомлення.
Описувані нижче методи нумеруються кодування відносяться саме до цієї групи.
В основі запропонованого нами методу кодування лежить метод поліадіческіх чисел, описаний в книзі В.І. Амелькін [3]. Метод поліадіческіх чисел використовує поліадіческую систему числення, тобто таку позиційну систему числення, в якій в якості підстави прийняті не постійні числа p, а набір деяких цілих чисел l1, l2, ..., lm, на різницю яких не накладається ніяких обмежень, тобто li - lj при i = j може бути більше нуля, дорівнює нулю або менше нуля [4].
У такій системі числення число L1, a2, ..., am можна представити у вигляді:
L = a1 * l2 * l3 * ... * Lm + a2 * l3 * l4 * ... * Lm + am-1 * lm + am (3)
При цьому кожна цифра ai <li, а кожен i-ий розряд має ваговий коефіцієнт:
У роботі В.І. Амелькін [5] сформульована теорема існування та єдиності такого розкладу.
Використання поліадіческой системи числення дозволяє побудувати наступний алгоритм упаковки. Нехай задана цілочисельна матриця A = ai, j, i = 1, .., m, j = 1, .., n.
За допомогою перетворення
де
цю матрицю можна замінити двома векторами N = nj і L = li, причому існує зворотне перетворення
ai, j = [nj / ri] - [nj / (lj * ri)] * li, (6)
дозволяє по N і L відновити будь-який елемент ai, j з похибкою E = 0. (Квадратними дужками тут позначена операція виділення цілої частини). Так як для зберігання векторів N і L потрібно менше двійкових одиниць, ніж для зберігання споконвічної матриці, коефіцієнт стиснення
виявляється більше одиниці. Тут So-число двійкових одиниць, необхідних для зберігання вихідної матриці, Si-число двійкових одиниць, необхідних для зберігання елементів векторів N і L.
Як показали наведені нами чисельні експерименти, описаний вище алгоритм не володіє високою ефективністю. До його недоліків можна також віднести труднощі, які виникають при реалізації програм-пакувальників на його основі.
У зв'язку з цим, ми поставили перед собою завдання вдосконалення описаного алгоритму з метою підвищення його ефективності та створення таких його версій, які легко реалізовувалися б у вигляді програм.
У нашому алгоритмі кодована інформація представляється у вигляді безлічі значень змінних байтового типу. Значення об'єднані в групи по чотири числа. Нехай таких груп у вихідному інформаційному масиві виділено m (m>> 4).
Виконавши для зазначеного масиву описану вище процедуру кодування, отримаємо два вектори - N з m елементами і L, що складається з 4-х елементів.
Для підвищення ефективності алгоритму (а під ефективністю ми тут і надалі розуміємо, в першу чергу, підвищення коефіцієнта стиснення), виконаємо наступне перетворення.
Кожен з елементів отриманого вектора N представимо у вигляді 4-х розрядного двухсотпятидесятишестиричного числа і до отриманої 4-х рядкової матриці знову застосуємо процедуру поліадііческого кодування.
Багаторазово повторивши описану послідовність кроків, можна істотно підвищити коефіцієнт стиснення вихідної інформації. У наведених нижче таблицях показані етапи стиснення вихідної інформації, що представляє собою деякий набір латинських літер.
Таблиці розраховувалися за допомогою табличного процесора з інтегрованого пакету Works 2.0.
Наведений приклад підтверджує високу ефективність описаного алгоритму.
Очевидно також, що на базі описуваного підходу можуть бути реалізовані швидкі і ефективні програми-пакувальники.
Таблиця 1. Приклад нумераційного кодування
Вихідний масив Компоненти вектора L
87 89 .................................. 79 89 90
90 85 .................................. 85 66 91
85 66 .................................. 78 79 86
94 80 .................................. 70 72 95
65425359 66869630 59435990 66715627