Осідач Андрій Олегович

Аспірант,

кафедра екології та екоінформаційних систем

Національний університет “Львівська політехніка”

Опис моделі класу документів за допомогою граматик

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

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

Автором запропонована математична модель електронного документу заснована на застосуванні логічних областей, що дозволяє розробляти методи обробки різнокласових електронних документів в сучасних системах електронного документообігу. Математична модель описує кожен окремо взятий документ. Щоб описати загальну структуру деякої безлічі однорідних документів, званого також класом документів, вимагається використання граматик.

Припустимо, що задана деяка безліч документів
D = {D₁, D₂, …, D_n). Тоді кожному з цих документів D_i, i =1,...,n, можна поставити у відповідність його структуру S_i, що є сукупністю логічної структури Sl_i і фізичної структури Sp_i.

Позначимо безліч логічних структур документів з класу D через:

S_L = {S_L1, S_L2, …, S_Ln},

де S_Li = (C_i, R_i), причому C_i: Z_i →∑^*_i і R_i: Z_i × Z_i → Θ_i,

де Z_i - сукупність всіляких логічних областей документу D_i,

∑^*_i - алфавіт символів в документі D_i,

Θ_i, - безліч роздільників можливих в документі D_i.

Тоді S_L= (С, R), де C: Z →∑^*; R: Z×Z → Θ,

- всілякі логічні області заданого класу документів D;

- алфавіт символів в класі документів D;

- безліч роздільників в класі документів D.

Розглянемо тепер ієрархічні грати Z. Задамо на розбиття J,
суміжними класами якого є елементи, що мають загальну точну верхню грань A, причому ніяка двоелементна підмножина великої кількості Z_,
у яке входить хоч б один елемент цього суміжного класу, не має такої точної верхньої грані А', що А'zА. Іншими словами, для усіх lZ
вірно, що lZ⁽ⁱ⁾ тоді і тільки тоді, коли:

(a) sup(l⁽ⁱ¹⁾, l⁽ⁱ²⁾, … l^(im)),

де Z⁽ⁱ⁾ = (l⁽ⁱ¹⁾, l⁽ⁱ²⁾, … l^(im)) – i-й суміжний клас розбиття J і

(b) для будь-кого mZ і lZ⁽ⁱ⁾ sup (m_, i) = A' причому А'zА.

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

Розглянемо тепер спосіб представлення загальної логічної структури документів із заданого класу D у вигляді контекстно-вільної граматики.

Припустимо, що така граматика G_D = {N_D, T_D, Р_D, ∆_D} існує.
Тут N_D - безліч нетермінальних символів, T_D - безліч термінальних символів, Р_D - безліч продукції і ∆_DN_D - початковий символ граматики.

Тоді множина T_D співпадає з множиною ∑ - алфавітом, прийнятому в області D; безліч нетермінальних символів N_D співпадає з безліччю логічних областей, що становлять грати Z. Початковий символ ∆_D є загальний максимальний елемент структур Z_i, i =1,...,n,.

Накінець, безліч продукцій Р_D може бути побудовано з чинник-множини Z/J і відображень С і R. Дійсно, чинник-множина Z/J у сукупності з відображенням R дозволяє отримати правила для нетермінальних елементів; відображення С зв'язує в правилах нетермінальні і термінальні символи. Структура чинник-множини Z/J гарантує, що в лівій частині отриманих правил стоятиме тільки один нетермінальний символ, а права частина правил може складатися з ланцюжка термінальних і нетермінальних символів. Отже, граматика G_D є контекстно-вільною.

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

Нині є важливою проблема розмітки логічної структури електронних документів в класі документів із змінюваною структурою. Електронні документи, що відносяться до цього класу, мають постійну структуру, що змінюється; крім того, сам склад цих документів може постійно мінятися. Проте, в кожен момент часу усі ці документи мають строгу логічну структуру, яка може бути описана явним чином. Наприклад, в СALS- технологіях (Continuous Acquisition and Life-cycle Support) рекомендується приміняти стандартизовані інтерактивні електронні технологічні керівництва (ІЭТК), які є організованими в базу даних набір документів у форматі SGML. Введення стандартів для структуризації документів забезпечує можливість передачі даних між різними організаціями, централізоване управління даними і можливість автоматизації процесу розробки структурованих документів.

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

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

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

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

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

Позначимо через М – безліч всіляких логічних міток заданого документу D.

Визначення 1. Припустимо, що т М - мітка, що визначає тип логічного об'єкту і О – область, обмежена межею логічною об'єкту. Тоді пара (m, О) називається логічною областю заданого об'єкту.

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

Визначення 2. Логічні області (m₁, О₁)і (m₂, О₂) називаються рівними, тобто: (m₁, О₁) = (m₂,О₂), якщо m₁ = m₂ і О₁ = О₂.

Визначення 3. Логічна область (m₁, О₁) називається вкладеною в логічну область (m₂, О₂), тобто: (m₁, О₁) (m₂, О₂), якщо О₁ О₂, причому О₁ = О₂ тоді і тільки тоді, коли (m₁, О₁) = (m₂, О₂).

Нехай Z - безліч усіх логічних областей документу D. Визначимо відношення z таким чином:

(m₁, О₁) z (m₂, О₂) (m₁, О₁) (m₂, О₂) и (m₁, О₁), (m₂, О₂) Z.

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

Рисунок 1 – Приклад зображення логічної структури документу у вигляді вкладених логічних областей

Таким чином, за результатами дослідження можливо зробити наступні висновки:

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

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

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