ОЦІНКА ЕФЕКТИВНОСТІ ПРАВИЛЬНОСТІ ВИЗНАЧЕННЯ ЛОГІЧНОЇ СТРУКТУРИ ДОКУМЕНТА



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

Ключові слова: корпоративний документообіг, пошук структурованої інформації, $\delta $-дерево.

EVALUATION OF CORRECTNESS DETERMINATION OF THE LOGICAL DOCUMENT STRUCTURE

Andrii Osidach

Aspirant

National University "Lviv Polytechnic"

Ukraine, Lviv

Abstract

The reportproposes a methodology and multi-criteria assessment of the effectiveness ofinformation storage and retrieval of structured information, which allows for amore adequate assessment of the functioning of the real system. The reportproposed as a criterion for assessing the quality of recognition of the logicalstructure of the documents used $\delta $-tree which size is directly relatedto the time-consuming manual editing of the document structure.

Key words: corporate document management, electronic document, retrievalof structured information, δ-tree.

Розглянемо деякий документ D$\in$ Ɗ. Припустимо, що ми маємо два впорядковані дерева ${{T}_{1}}$ і ${{T}_{2}}$, що описують логічну структуру документа D. При цьому нехай дерево ${{T}_{1}}$ описує логічну структуру, отриману в результаті автоматизованого розбору, а дерево ${{T}_{2}}$ представляє ідеальну логічну структуру. Визначимо певним чином відмінності між деревами ${{T}_{1}}$ і ${{T}_{2}}$. Поставимо у відповідність вузлам обох дерев деякий набір унікальних ідентифікаторів.

Визначення 1. Два вузли ${{t}_{1}}\in{{T}_{1}}$ і ${{t}_{2}}\in {{T}_{2}}$ називаються ізоморфними, якщо вони розрізняються тільки ідентифікаторами, а їх значення і контекст рівні.

Визначення2. Два впорядковані дерева ${{T}_{1}}$ і ${{T}_{2}}$ називаються ізоморф­ними, якщо для кожного вузла водному дереві знайдеться єдиний ізоморф­ний вузол в іншому дереві, тобто$\forall{{t}_{1}}\in {{T}_{1}}\exists $ єдиний ізоморфний ${{t}_{2}}\in {{T}_{2}}$і $\forall {{t}_{2}}\in{{T}_{2}}\exists $ єдиний ізоморфний ${{t}_{1}}\in {{T}_{1}}$.

Визначення 3. Назвемо відображенням повної відповідності ${{M}_{F}}:{{T}_{1}}\to {{T}_{2}}$ таке бієктивне відображення, яке кожному вузлу ${{t}_{1}}\in {{T}_{1}}$ однозначно ставить у відповідність ізоморфний йому вузол ${{t}_{2}}\in {{T}_{2}}$.

Очевидно, що повна відповідність можлива тільки в тому випадку, коли дерева ${{T}_{1}}$ і ${{T}_{2}}$ ізоморфні.

Припустимо тепер, що дерева ${{T}_{1}}$ і ${{T}_{2}}$ не є ізоморфними. Тоді виділимо вдереві ${{T}_{1}}$ підмножину вузлів ${{T}_{1}}\subseteq{{T}_{1}}$, що мають ізоморфні їм вузли в дереві ${{T}_{2}}$, аналогічно, вузли дерева ${{T}_{2}}$, що мають ізоморфні їм вузли в дереві ${{T}_{1}}$ можутьбути об'єднані в підмножину ${{T}_{2}}\subseteq {{T}_{2}}$. Тоді, якщо під­множина ${{T}_{1}}$ і ${{T}_{2}}$ не порожні, можна дати наступне визначення.

Визначення4. Назвемо відображенням часткової відповідності ${{{M}'}_{p}}:{{T}_{1}}\to{{T}_{2}}$ таке бієктивне відображення, яке кожному вузлу ${{t}_{1}}\in{{{T}'}_{1}}$ ставить в однозначну відповідність ізоморфний йому вузол ${{t}_{2}}\in{{{T}'}_{2}}$.

Очевидно, що для оцінки відмінностей між двома деревами ${{T}_{1}}$ і ${{T}_{2}}$ необхідно спочатку визначити деяку часткову відповідність між деревами, а потім знайти таку послідовність елементарних операцій, яка до­зволяє перетворити дерево ${{T}_{1}}$ в дерево ${{T}_{2}}$.

Визначимо чотири операції, які використовуватимуться для редагування дерев:

a. Вставка. Вставка нового вузла t в дерево ${{T}_{1}}$.

b. Видалення. Видалення вузла t з дерева ${{T}_{1}}$. Виконання цієї операції можливе тільки у тому випадку, якщо вузол t не має нащадків.

c. Модифікація. Модифікація значення вузлаt в дереві ${{T}_{1}}$.

d. Переміщення. Переміщення піддерева з коренем вузла t в дереві ${{T}_{1}}$.

Усі вищезгадані операції є стандартними операціями редагування дерев, за винятком операції переміщення. Ця операція виконується не лише стосовно окремо взятих вузлів, але і до цілих під­дерев, які утворюють нащадки переміщуваного вузла.

Розглянемо тепер послідовність операцій редагування, яка перетворює одне дерево в інше.

Визначення 5. Сценарієм редагування S дерева ${{T}_{1}}$ відносно де­рева ${{T}_{2}} $називається така кінцева послідовність елементарних операцій (1) - (4), якапереводить дерево ${{T}_{1}}$ в деяке дерево ${{{T}'}_{1}}$таке, що дерево ${{{T}'}_{1}}$ ізоморфно ${{T}_{2}}$.

Наприклад, для дерев, представлених на рис. 1, сценарій редагування S для дерева ${{T}_{1}}$ відносно ${{T}_{2}}$ має наступний вигляд:

В результаті застосування сценарію редагування (1) до початкового дерева ${{T}_{1}}$ отримуємо дерево ${{{T}'}_{1}}$, ізоморфне кінцевому дереву ${{T}_{2}}$.

Очевидно, що для двох дерев ${{T}_{1}}$ і ${{T}_{2}}$ може існувати більш за один сценарій редагування. Тому необхідно ввести поняття вартості редагування. Вартість операцій редагування залежить від типу операції і вузлів, залучених в операцію. В цілях простоти тут усі операції (а)-(d) вважаються операціями одиничної вартості. Проте, вартості можуть бути відкориговані згідно з вагою різної ваги змін в ланцюгах уточнення відмінностей між ними. Загальна вартість сценарію редагування є сумою вартостей його окремих операції.

Рисунок 1. Дерева логічної структури ${{T}_{1}}$і ${{T}_{2}}$ документа D

Припустимо тепер, що задано два впорядковані дерева ${{T}_{1}}$ і ${{T}_{2}}$і безліч сценаріїв редагування ${{S}_{1}},{{S}_{2}},...,{{S}_{k}}$, дерева ${{T}_{1}}$ відносно дерева ${{T}_{2}}$. Припустимо також, що кожен сценаріїв редагування ${{S}_{i}}$ має вартість редагуванні ${{C}_{i}}$, і = 1, 2, …, k.

Визначення 6. Сценарій редагування ${{S}_{opt}}$, що має мінімальну вартість $C=\underset{1\le i\le k}{\mathop\min }\,{{C}_{i}}$ називається оптимальним сценарієм редагування, а мінімальна вартість С називається відстань $d\left({{T}_{1}},{{T}_{2}} \right)$ між впорядкованими деревами ${{T}_{1}}$ і ${{T}_{2}}$.

Таким чином,метою порівняння впорядкованих дерев є отримання оптимального сценарію редагування і відстані між деревами в сенсі визначення (1). У [5] запропонований алгоритм EditScript для знаходження оптимального сценарію редагування ${{S}_{opt}}$ за час O(n-r), де n – загальна кількість вузлів і r - кількість невирівняних вузлів у редагованому дереві (зазвичай n набагато перевищує r).

У [5] під невирівняними вузлами розуміються вузли, для яких вірно твердження. Нехай для дерев ${{T}_{1}}$ і ${{T}_{2}}$ задане відображення часткової відповідності ${{M}_{p}}$. Тоді якщо вузол ${{t}_{1}}\in{{{T}'}_{1}}$, то ${{t}_{2}}={{M}_{p}}\left( {{t}_{1}} \right)$ відповідний йому вузол в дереві ${{T}_{2}}$. Припустимо, що вузли g і h - діти вузла ${{t}_{1}}$ в дереві ${{T}_{1}}$ і вузол g - лівий брат вузла h. Згідно [5], вузли g і h є невирівняними, якщо вузли ${{M}_{p}}\left( g \right)$ і ${{M}_{p}}\left(h \right)$ - діти вузла ${{t}_{2}}$ в дереві ${{T}_{2}}$, і ${{M}_{p}}\left(g \right)$ є правим братом ${{M}_{p}}\left( h \right)$.

Відстань між деревами в даному випадку обчислюється просто як число операцій в оптимальному сценарії редагування:

\[d\left({{T}_{1}},{{T}_{2}} \right)=\left| {{S}_{opt}} \right|.\quad\quad\quad(2)\]

Іншим наочним представленням відстані між впорядкованими деревами є $\delta $-дерева. Використання $\delta $-дерев дозволяє відмовитися від ідентифікаторів вузлів, які є обов'язковими при побудові сценаріїв редагування і можуть тільки ускладнювати перегляд і пошук. Окрім того, δ-дерева є більш наглядним представленням сценаріїв редагування.

δ-дерева є узагальненням на ієрархічні структури δ-відношень, що використовуються в реляційних СУБД для визначення змін в кортежах, що входять в базу даних відношень. Для кожного відношення R тоді обчислюється набір δ-відношень, що містять відповідно кортежі, які були вставлені і видалені з відношення R, а також старі і нові значення тих кортежів, які були змінені [5].

Аналогічно $\delta$-відношенням, $\delta $-дерева повинні представляти ієрархічні структури обох дерев, а також описувати набір елементарних операцій редагування, необхідних для переведення одного впорядкованого дерева в інше, що складають сценарій редагування. Припустимо, що ${{T}_{1}}$ і ${{T}_{2}}$ - два впорядкованих дерева, $\delta $-дерево для ${{T}_{1}}$по відношенню до ${{T}_{2}}$ - це дерево, в якому вузли окрім власних значень, мають також відмітку про визначену до цього вузла елементарну операцію редагування.

Визначення 7. δ-дерево для дерева ${{T}_{1}}$ відносно дерева ${{T}_{2}}$ називається правильним, якщо воно має такий відповідний сценарній редагування S, що S трансформує дерево ${{T}_{1}}$ до дерева ${{T}_{2}}$.

Визначення 8. δ-дерево для дерева ${{T}_{1}}$ відносно дерева ${{T}_{2}}$називається оптимальним, якщо воно є правильним і відповідний йому сцена­рій редагування S є оптимальним, тобто $S={{S}_{opt}}$.

На рис.2 показане $\delta $–дерево, яке є правильним відносно сценарію S, представленого формулою (1). Слід зазначити, що представлене $\delta $-дерево є також оптимальним, а відстань між де­ревами $d\left( {{T}_{1}},{{T}_{2}}\right)=3$.

Рисунок 2. δ-дерево сценарію редагування (1)

Для побудови оптимального $\delta $-дерева може бути використаний згаданий алгоритм EditScript. Для цього необхідно тільки додати операцію, яка при кожному додаванні операції редагування до оптимального сценарію редагування додаватиме відповідну вершину і мітку в $\delta $-дерево.

Існує безліч критеріїв оцінки інформаційних систем збереження та пошуку структурованої інформації, проте чотири наступні критерії прийнято вважати основними [6]:

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

b. Часовий інтервал, тобто середній інтервал часу між заданням запиту і отриманням відповіді.

c. Повнота системи, тобто відсоток релевантних документів, знайдених у відповідь на пошуковий запит.

d. Точність системи, тобто відсоток релевантних документів у видачі.

Список літератури.

  1. Осідач А.О. Математична модель електронного документа /А.О. Осідач. – Технічні науки ітехнології. – №1 (1). – Чернігів, 2015. – С. 146-152.

  2. Осідач А.О. Опис елементів електронного документообігу та зв’язків між ними / А.О. Осідач. – East European Scientific Journal. –2016. – № 3. – Vol. 4 – P. 69-72.

  3. Осідач А.О. Методи подання різнотипної інформації всистемі електронного документообігу / А.О. Осідач. – East European Scientific Journal. – 2016. – № 5. –Vol. 5 – P. 96-101.

  4. Осідач А.О. Опис моделі класу документів за допомогою граматик / А.О. Осідач – Збірник матеріалів науково-практичної конференції “Найновіші досягнення європейської науки – 2015”. – Софія: “Бял ГРАД-БГ”, 2015.– Т.13 – С. 65-69.

  5. Chawalhe S. Managing change in heterogeneous autonomousdatabases. Phd thesis, Stanford University, Stanford, USA, 2009. – 308 p.

  6. Солтон Дж. Динамические библиотечно-информационные системы: Пер. с англ. – М.: Мир, 2009. – 558 с.
  • Рецензент: д.т.н., проф, Інститут комп'ютерних наук та інформаційних технологій Шаховська Н.Б.
May 31, 2016