Обобщение модели документа

Введем следующее определение. Будем считать, что граф документа G_D описывается шаблонным графом G_T, если существует отображение:

X:V (G_T) > V'(G_D),.

где такое, что для любых вершин v и u и их образов v' и u' выполняются условия:

• 1. id (v) = id (v'), т. е. идентификаторы вершин совпадают.
• 2. Объект, заданный вершиной v', входит в множество объектов, заданное описанием description метки вершины v.
• 3. Метка l ребра e = (v, u) является обобщением метки l' ребра e' = (v', u'), в том смысле, что интервалы distance метки l входят в интервалы distance метки l'.

Отметим, что из условия 1 следует, что некоторый шаблонный граф может описывать только подмножества множества документов одного типа, т. е. имеющих одинаковый набор полей.

Построение шаблонного графа будем проводить, последовательно обобщая его на документы из обучающей выборки. Пусть имеется шаблонный граф G_T, построенный на некотором наборе документов и граф очередного документа G_D. Шаблонный граф может быть обобщен с графом G_D, так чтобы в множество описываемых документов входил очередной документ, следующим образом. Необходимо построить отображение подмножества вершин шаблонного графа на подмножество вершин графа документа:

Y:V'(G_T) > V'(G_D),.

где, , такое что идентификаторы вершин-образов и вершин-прообразов совпадали. После этого метки вершин из множества V'(G_T) должны быть обобщены с метками вершин из множества V'(G_D) т.о. чтобы заданные метками на вершинах множества графических объектов включали новые объекты, описанные метками на вершинах V'(G_D). Аналогично, интервалы расстояний на ребрах графа G_T должны быть обобщены с интервалами на образах этих ребер из графа G_D.

Очевидно, что может быть построено большое число таких отображений и соответственно шаблонных графов. Необходимо ввести критерий, позволяющий выбирать наиболее подходящий граф. Следует отметить, что рассмотренное отображение вершин представляет собой путь редактирования (Edit Path) [Cook et al., 2006]. В общем случае для оценки пути редактирования может быть применена вероятностная оценка [Neuhaus et al., 2004], однако в данном случае более целесообразным является использование специальной эмпирической оценки, более соответствующей предметной области.

Введем оценку качества отображения вершин и соответствующего обновленного шаблонного графа G_T':

Q = (?Q_V(v_i>u_j))*Q_U(V (G_T)V'(G_T))*Q_U(V (G_D)V'(G_D)),.

где Q_V — оценка пары вершин из отображения Y, Q_U — оценка вершин из множеств V (G_T) V'(G_T) и V (G_D) V'(G_D), т. е оставшихся без образа или прообраза. Поскольку при отображении вершин идентификаторы вершин сохраняются, то соответствие между полями документа задано однозначно, поэтому в оценке шаблонного графа следует учитывать только вершины с метками текстовых объектов и разделительных линий.

Q_V(v>u) = Q_V(v') = maxQ_E(e_i) — б*(maxQ_E(e_i) — ?Q_E(e_i)/N_F),.

где Q_E(e_i) — оценка i-го ребра, выходящего из вершины v' графа G_T', полученной в результате отображения вершины v графа на вершину u графа G_D;; N_F — число полей в данном типе документа; б — эмпирический коэффициент, вводящий зависимость оценки не только от оценки наилучшего ребра, но и от средней оценки.

Оценка Q_U зависит от числа вершин в соответствующих множествах и имеет вид: Q_U(V (G)V'(G)) = U^{|V (G)V}'^(G)|, т. е. за каждую неотображенную вершину назначается фиксированный штраф U.

Оценка ребра имеет вид:

Q_E(e_i) =max (0;),.

где Дx = Width (XDistance)/W, Width (XDistance) — ширина интервала XDistance метки ребра e_i, W — характерная ширина интервала порядка размера страницы; аналогично для Дy. Данная эмпирическая оценка выбрана из следующих соображений. Во-первых, изолинии функции должны быть вогнутыми, т. е. оценка ребра с интервалами шириной (для примера) Дx = 1, Дy = 0 должна быть выше, чем для ребра с интервалами шириной Дx = ½, Дy = ½. Во-вторых, оценка должна быть близка к 1 для ребра, полученного в результате правильного сопоставления объектов (Дx и Дy при этом существенно меньше 1), и заметно снижаться при приближении значений Дx и Дy к 1. В данном случае изолиниями являются гиперболы вида,. График функции оценки ребра в области представляет собой поверхность, полученную «скольжением» гиперболыпо параболе .

Итак, после введения функции оценки задача сводится к поиску отображения вершин и графа шаблона с наилучшим качеством. Для этого применим следующий метод:

Будем последовательно выбирать пары для вершин первого графа, используя дерево перебора. Узел дерева соответствует решению отобразить вершину v_i на вершину u_j, либо оставить вершину v_i без образа.

Для каждого нетерминального узла и соответственно пути в дереве введем частичную оценку Q_P, которая, в отличие от Q не учитывает нерассмотренные вершины первого графа и не имеющие прообраза вершины второго. Т. е. будем учитывать в Q_U(V (G_T)V'(G_T)) только рассмотренные вершины шаблонного графа, а Q_U(V (G_D)V'(G_D)) опустим.

Перебор дерева производится в порядке уменьшения качества вершин. Поскольку при спуске по дереву качество не может увеличиваться, то качество текущей вершины одновременно является оценкой сверху качества всех продолжений данного пути. Т.о. порядок перебора соответствует алгоритму Дейкстры (для дерева).