У статті розглянута графова модель тексту, що дозволяє прискорити обробку інформації. Дана модель дозволяє виявляти однакові фрагменти в документах зі зміною порядку слідування речень та інших частин. Використання конструктивно-продукційних структур для формалізації даної моделі є перспективним підходом для подальшої автоматизації процесу роботи з моделлю і відповідно з текстом. Ключові слова: графова модель тексту, стискання графа, конструктивно-продукційна структура, співставлення текстів. В статье рассмотрена графовая модель текста, позволяющая ускорить обработку информации. Данная модель позволяет выявлять одинаковые фрагменты в документах с изменением порядка следования предложений и других частей. Использование конструктивно-продукционных структур для формализации данной модели является перспективным подходом для дальнейшей автоматизации процесса работы с моделью и соответственно с текстом. Ключевые слова: графовая модель, сжатие графа, конструктивно-продукционная структура, сопоставление текстов. The article describes the graph model of the text, allowing speeds up processing. This model allows us to identify the same fragments in the documents with the change in the order of sentences and other parts. Using constructive-synthesizing structure to formalize this model is a promising approach to further automate the process of working with the model and the text accordingly.
структуры [
Подход на основе КПС может быть использован для формализации понятий текста, его составляющих. Особенности определения понятий текста, предложения, слова определяют носитель КПС и суть операций по ее преобразованию. Так, например, если слово рассматривать с точки зрения естественного языка, то оно не может включать символы-цифры, а если с точки зрения языков программирования, слово – лексема, которая может содержать цифры и иные символы (имена переменных, функций, классов и т.п.). Таким образом, определение подобных понятий может как расширять, так и сужать область определения элементов носителя, конструкций, операций над ними. Формализованная спецификация текста средствами КПС
Формализованная спецификация текста и его составляющих дает возможность автоматизировать разработку и обновление программ для решения поставленных задач.
Введем некоторые ограничения и дополнения аксиоматики и обозначений [
С данной целью определим КПС и выполним ее специализацию:
C = M ,Σ, Λ S a S CT = MT ,ΣT , ΛT , (1) где M T – носитель, включающий все символы электронного представления текста и конструкции, построенные на них, ΣT – операции и отношения на элементах M T , ΛT – аксиоматика, определяющая M T и ΣT .
Частичная аксиоматика носителя. Носитель включает множества терминалов и нетерминалов. M T ⊃ TT U NT ,TT = TK UTL UTD UTN UTNP , TK , TL – множество кириллических и латинских символов соответственно, которые входят в текст; TD – множества символов-разделителей для отображения знаков пунктуации является форма wl l . Форма может быть построена таким образом: wl l=w0 ⋅(wj m j , wk mk ) для ∀wi mi ∈ MT ; wl l=wj mj , если l=w0 ⋅(ε,wj m j )=w0 ⋅( wj m j , ε) , где ε – пустой элемент; wl l=w0 ⋅(w1 l1, w2 l2 ) для ∀wi li =wj m j |⋅(wj m j , wk mk )|⋅(wj l j ,wk mk ), ∀ wi mi ∈MT . щих.
− − − Множество значений атрибутов формы определяется совокупностью значений атрибутов ее составляюСентенциальная форма – форма, полученная в результате вывода из аксиомы (начального нетерминального символа, принадлежащего носителю) согласно правилам вывода конкретизированной КПС.
Формы, в которых отсутствуют нетерминальные элементы – конструкции. Конструкции имеют такие атрибуты: тип языковой конструкции, набор кодов. Атрибут тип ( type↵l ) может принимать такие значения: к-слово, к-предложение, к-абзац, к-текст.
Отношение подстановки – отношение с атрибутами wi li w →wj l j , где li ,l j – сентенциальные формы [
TSD ⊂ TD . Для заданной формы wl l=w0 ⋅(w1 l1, w2 l2 , K, wh lh , K, wk lk ) и доступного отношения подстановки wp → (wh lh , wq lq ) такого, что wh lh – подформа wl l результатом трехместной операции подстановки wl* l* =wp ⇒(wh lh ,wq lq , wl l) будет форма wl* l* = w0 ⋅(w1 l1, w2 l2 , K, wq lq , K, wk lk ) .
Двухместная операция частичного вывода wl* l* =wp |⇒ (Ψ, wl l) ( |⇒∈ Θ ) заключается в: − выборе одного из доступных правил подстановки ψ r : sr , gr с отношениями подстановки sr ; − выполнении на его основе операций подстановки; − выполнении операций над атрибутами gr в соответствующей последовательности.
Операция полного вывода или просто вывода ( ||⇒∈ Θ ) заключается в пошаговом преобразовании форм, начиная с начального нетерминала и заканчивая конструкцией, удовлетворяющей условию окончания вывода, что подразумевает циклическое выполнение операций частичного вывода. Операция двухместная wl* l* = ||⇒ (Ψ, wl l) .
Операция присваивания := (a, b) копирует значение операнда b в a .
Операция = (wi , w j ) выполняет сравнения атрибутов. Результатом операции сравнения является значение «истина», если wi = w j , иначе – «ложь». l1, l2 , l3 – формы, образованные с помощью операции конкатенации.
Элемент принадлежит форме m∈l , если ∃l1, l2, l3 : l = ⋅(l1,l2 ) & ((l1 = ⋅(l3, m)|l1 = ⋅(m,l3 ))|l2 = ⋅(l3, m)) , где Расширение аксиоматики носителя.
Конструкция является к-словом type↵l = cw , если Конструкция является к-предложением type↵l = cs , если l = ⋅(l1, m), m ∈TSD , TSD = {"!","?",".","..."} , Конструкция является к-абзацем type↵l = cp , если l = ⋅(l1, l2 ) &l2 = ⋅(m1, m2 ) , code↵m1 = 13, code↵m2 = 10 (переход на новую строку, возврат каретки).
К-абзац может включать в себя несколько предложений, к-предложение – несколько абзацев. Конструкция является к-текстом type↵l = ct , если l = ⋅(l1, l2 ) & type↵l1 = cp & (type↵l2 = cp | l2 = ε) и l1, l2 имеют смысловую связь.
Интерпретация КПС текста. Частично интерпретируем структуру CT (1) с помощью алгоритмической структуры C A :
CT ,CA,T = M A,T ,VA,T ,Σ A,T , Λ A,T I a A CT , ACT = M1,Σ1, Λ1 ,
(2)
где Λ1 ⊃ ΛT , VA,T = {Ai0 |YXi i } – множество базовых алгоритмов [
U ( X ( Ai0 ) U Y ( Ai0 )) U Ω(CT )} – неоднородный носитель, Ω(CT ) – Aio∈VA,T l множество языковых конструкций, которые удовлетворяют CT ; Λ1 = {(A3 |l1,l2 ↵"⋅"); ( A4 |lfhi,lq, fi ↵"⇒"); ( A5 | ffij,Ψ ↵"|⇒"); ( A6 |σΩ,Ψ ↵"||⇒"); ( A7 |aa,b ↵":="); ( A8 |ca,b ↵"=")} .
Структура A CT включает алгоритмы выполнения операций:
A10 | AAii ⋅,AAjj – композиция алгоритмов, Ai ⋅ A j – последовательное выполнение алгоритма A j после алгоритма Ai ; − − −
A20 | ZA1 – условное выполнение: алгоритм Ai выполняется, если условие Z истинно; A3 |ll1,l2 –конкатенация, l,l1, l2 – формы; сформированных конструкций; − − − −
A4 |lfhi,lq , fi – подстановка, lh , lq , fi – формы; A5 | ffij,Ψ , A6 |σΩ,Ψ – частичный и полный вывод, где fi , f j – формы, σ – аксиома, Ω – множество A7 |aa,b – присвоение операнду a значение операнда b ;
A8 |ca,b – сравнение атрибутов a и b , если a = b , то c = true , в противном случае c = false . Конкретизация КПС текста. Выполним конкретизацию структуры CT :
CT K a K CT = M 2 , Σ 2 , Λ 2 , где Λ2 ⊃ Λ1 , Λ 2 ⊃ {M 2 = TT U N; N ={wi ni } = {α, γ, δ, κ, π, ρ, σ, τ}} . Атрибутом нетерминала ( wi ) является тип конструкции ( kind↵wi ), для построения которой он используется.
Далее рассмотрим правила для построения к-текста, а также других конструкций, которые могут в него входить.
Правило s1 позволяет начать выполнение построения текста, определив значение соответствующего атрибута как текст:
s1 = σ →τ , g1 = kind↵τ := ct .
Правило s2 − s4 позволяют определить составляющие текста – абзацы (одного или много), определив значение соответствующего атрибута как абзац
s2 = τ →απ , g2 = kind↵α := cp , s3 = π →απ , s4 = π → m1m2 , где m1, m2 – символы возврата каретки и перехода на новую строку.
Правила s2 − s4 позволяют определить составляющие абзаца – предложение (много или одно), определив значение соответствующего атрибута как предложение
s5 = α → ργα , s6 = α → ργ , g6 = kind↵ρ := cs , s7 = γ → mend , где mend ∈TSD – символ признак окончания предложения.
Правила s8 − s9 позволяют определить составляющие предложения: одно или более слов
s8 = ρ → κ , g8 = kind↵κ := cw , s9 = ρ → κδρ .
Правила s10 − s11 позволяют определить разделитель между словами где msep ∈TWD ,TWD = TD \ TSD .
Правила s12 − s13 позволяют построить слово из одной и более букв: s10 = δ → msep , s11 = δ → msepδ ,
s12 = κ → mcκ , s13 = κ → mc , где mc ∈TK U TL U TN .
Тут под записью типа κ → mc , mc ∈ TK U TL U TN следует понимать множество альтернативных правил, что можно также записать в виде κ → a |б | в... .
Операции над атрибутами выполняются после операции частичного вывода.
Реализация КПС текста. Реализация структуры (2) заключается в формировании языковых конструкций из элементов ее носителя путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам аксиоматики:
A CT R a Ω( A CT ) , где Ω( A CT ) ⊂ Ω( A CT ) .
Рассмотри пример построения конструкции «Колпак под колпаком.». Далее показан вывод текста, состоящего из одного абзаца и одного предложения, заканчивающегося точкой:
1 2 4 6 7 σ ⇒ τ⇒ απ ⇒ α'13''10'⇒ ργ'13''10'⇒ ρ'.''13''10' Определим количество слов и структуру предложения:
9 9 8 10 ρ'.''13''10 ⇒ κδρ'.''13''10 ⇒ κδκδρ'.''13''10'⇒ κδκδκ'.''13''10'⇒ κ' ' κ' ' κ.''13''10' .
Далее используя правила 12, 13 получаем фразу «Колпак’32’под’32’колпаком.’13’’10’». Здесь в кавычки взяты символы пробела и перехода к новому абзацу.
Для обработки конструкций рассмотрим задачи синтеза и анализа графовой модели текста [
Пусть есть множество языковых конструкций Ω( ACT ) , порожденное структурой A CT (2). Задача состоит в определенные структуры Cg , порождающей множество конструкций-графов Ω(Cg ) такое, что существует биективное отображение f :Ω( A СT ) → Ωg (Cg ) .
Для решения поставленной задачи определим структуру и специализируем ее соответствующим образом:
C = M , Σ, Λ S a C g = M g , Σ g , Λ g , где M g – расширяемый носитель, включающий множества конструкций-графов, языковых конструкций и их элементов, Σ g – множество операций и отношений на элементах M g , Λ g – аксиоматика.
Частичная аксиоматика носителя. Носитель включает множества терминальных и нетерминальных элементов M g = Tg U N g . Терминалами являются языковые конструкции, построенные КПС (2) и их составляющие ( TT ), а также конструкции графов и их составляющих Tg = Ω U Ω g U TT U V U E , Ω g – множество конструкций-графов, V , E – множества вершин и дуг с их атрибутами.
Вершина имеет атрибуты w v= id, content, tokens , id – идентификатор, принимает целочисленные значения, content – часть текстовой конструкции, tokens – список, содержащий признаки начала языковых конструкций. Атрибуты дуги we = id, routes, start, end , id – идентификатор, принимает целочисленные значения, routes – множество номеров путей, в которые входит дуга (указывает на порядок обхода графа), start, end – вершин, которые являются началом и концом дуги.
Нагруженный граф будем обозначать wg G = V , E , V ={wvi vi }, E ={we j e j } – множества вершин и дуг, нагруженых атрибутами. Каждое множество содержит пустой элемент.
Граф имеет такие атрибуты w g = start _ v, last _ v, current_ v, amount_ l , где start_v– стартовая вершина графа, last_v – последняя добавленная вершина, current_v – текущая вершина при формировании графа, amount_l – количество циклов, в которые входит стартовая вершина.
Частичная аксиоматика операций. Рассмотрим сигнатуру Σ g :
Σ g = Ξ g , Θ g , Φ ,{→} U Ψg , ~ где Ξ g = {⋅,:=),:=&, U,U} – множество операций преобразования и связывания, Θ g = {⇒,|⇒,||⇒~ } – множество операций вывода, Φ g = {÷,:=, # , +} – множество операций над атрибутами, Ψg – множество правил продукций вида ψi :< si , gi > , i – номер правила, s – последовательность операций подстановки, g – последовательность операций над атрибутами, « → » – отношение подстановки. Операция e :=) (v1, v2 , G) заключается в определении дуги e , соединяющей вершины v1 и v2 графа G . Если дуга со значениями соответствующих атрибутов отсутствует, то возвращается пустой элемент множества дуг графа G , его идентификатор равен нулю.
Операция v :=& (x,V ) заключается в нахождении вершины v с атрибутом веса, равным x , из множества вершин V . Если вершина со значениями соответствующих атрибутов отсутствует, то возвращается пустой элемент множества вершин V , его идентификатор равен нулю.
Операция ÷(c, n, L) заключается в выполнении n операций из списка L , если c = true . Операция вычисления мощности множества #Q определяет число, равное количеству элементов в Q . Операция сложения двух чисел +(a,b) предполагает нахождение третьего числа, являющегося их суммой.
Операция объединения графов
~ wg G = U(w1 G1, w2 G2 ) предполагает формирование нового графа wg G , включающего объединенные множества вершин и дуг исходных графов w g G = V , E , V = V1 U V2 , E = E1 U E2 , w1 G1 =< V1, E1 > , w2 G2 =< V2 , E2 > , при этом U – традиционная операция объединения множеств.
Отношение подстановки имеет вид ~ ψi = si , gi , si = si , ~si , gi = gi , gi , где si , ~si – отношение подстановки для распознавания языковой конструкции и построения конструкции графа соответственно, gi , g~i – операции над атрибутами языковой конструкции и графа, его вершин и дуг соответственно. В случае если операции над атрибутами не выполняются, отношение подстановки имеет вид ψ = s, ε .
Операция полного вывода ||⇒~ (Ψ, wl l) состоит в: −
определении входной конструкции, набора отношений подстановки и доступных из них; − выполнении операции частичного вывода, пока языковая конструкция ω ∈ Ω полностью не распознана, то есть для каждого ее элемента ωi в графе нет соответствующего элемента-вершины или форма графа содержит нетерминалы.
Результатом операции вывода является конструкция-граф. Конкретизация КПС графа. Выполним конкретизацию структуры C g :
C g K a K C g = M 3 , Σ3 , Λ 3 , где Λ3 ⊃ Λ g , Λ3 ⊃ { M 3 ⊃ M g , c ∈ TT ,
Ng = {α, δ} , Tg ⊃ {G,G*,G**} , G = V , E , V = {v} , E = ∅ , G* =< V *,G* > , V * = {v1*, v2*} , E* = {e1*} , G** =< V ** , G** > , V ** = {v1** , v2**} , E** = {e1**}} .
Для распознавания языковых конструкций определим такие правила: s1 = σ d1 → cσ , g1 = ÷ (code↵c ≠ EOF,1, d1 := true) , s2 = σ d2 → c , g2 = ÷ (code↵c = EOF,1, d2 := true) , где с – символ текста, кроме EOF – признак конца текста в его электронном представлении. Следующие правила описывают добавление первой вершины в пустой граф: ~s1 = σ →~ Gα , g~1 = id↵v :=#V , content↵v: = c,tokens :=< cw, cs, cp, ct > ,
start_v↵G: = v, current_v↵G: = v,last_v↵G: = v, amount _ l↵G := 0 .
Правило ~s2 позволяет добавить к графу новую вершину и дугу, связывающую новую вершину с текущей в графе ~s2 := Gα d* →~ ~U(G,G* )α , U (G,G* )α → Gα , g~2 = v1 :=& (c,V ), e1 :=) (current _ v↵G, v,G) ,
~ 1 ÷ (id↵v1 = 0 & id↵e1 = 0,14, d1* := true, id↵v1* := id↵current _ v↵G, content↵v1* := content↵current _ v↵G, id↵v2* :=#V +1, content↵v2* := c, id↵e1* :=# E +1, start↵e1* := v1*, end↵e1* := v* , routes↵e1* := {amount _ l↵G}, 2 ÷ (content↵current _ v↵G = x & x ∈TWD , tokens↵v2* :=< cw >), ÷ (content↵current _ v↵G = x & x ∈TSD ,tokens↵v2* :=< cs >) , ÷ (content↵current _ v↵G ='10',tokens↵v2* :=< cp >), last _ v↵G := v2 , current _ v↵G := v2 ) .
~ Правило s3 позволяет добавить к графу новую дугу, связывающую текущую вершину со стартовой.
~ ~ ~s3 = α * → U(G,G** )α , U (G,G** )α → Gα , g~3= v1 :=& (c,V ), e1 :=) (current _ v↵G, v1,G),
d2 ÷ (v1 = start _ v↵G &id↵e1 = 0,14,d2* := true, id↵v1** := id↵curret _ v↵G,content↵v1** := := content↵curret _ v↵G,id↵v2** := id↵start _ v↵G, content↵v2** := c, id↵e1** :=# E +1, start↵e1** := := v1**, end↵e1** := v2**, routes↵e1** := {amount _ l↵G}, amount _ l↵G := amount _ l↵G +1, ÷ (content↵current _ v↵G = x & x ∈TWD ,1, tokens↵v2** := ⋅(tokens↵start _ v↵G, < cw >)), ÷ (content↵current _ v↵G = x & x ∈TSD ,1,tokens↵v2** := ⋅(tokens↵start _ v↵G, < cs >)), ÷ (content↵current _ v↵G ='10',1,tokens↵v2** := ⋅(tokens↵start _ v↵G, < cp >)), current _ v↵G = start _ v↵G) .
~ Правило s4 позволяет изменить нагрузку имеющейся дуги: ~ ~ s4 = Gα * → Gα , g4 = v1 :=& (c,V↵G), e1 :=) (current _ v↵G, v1,G) , ÷ (id↵v1 ≠ 0 & id↵e1 ≠ 0,3, d3* := true, d3 ÷(start _ v↵G ≠ v1,5, routes↵e1 := routes↵e1 U {amount _ l↵G},÷ (content↵current _ v↵G = x & x ∈TWD ,1, tokens↵v1 := ⋅(tokens↵v1, < cw >)), ÷ (content↵current _ v↵G = x & x ∈TSD ,1,tokens↵v1 := ⋅(tokens↵v1, < cs >)), ÷(content↵current _ v↵G ='10',1,tokens↵v1 := ⋅(tokens↵v1, < cp >)), current↵v := v1),÷(start _ v↵G = v, 6, routes↵e1 := routes↵e1 U{amount _ l↵G}, ÷ (content↵current _ v↵G = x & x ∈TWD ,1,tokens↵v1 := ⋅(tokens↵v1, < cw >)), ~ ÷ (content↵current _ v↵G = x & x ∈TSD ,1, tokens↵v1 := U(tokens↵v1, < cs >)), ÷ (content↵current _ v↵G ='10', tokens↵v1 := ⋅(tokens↵v1, < cp >)), current↵v := start _ v↵G, amount _ l↵G := amount _ l↵G +1)) . Следующее правило позволяют завершить процесс построения конструкции-графа: s5 = α →~ ε .
~ Интерпретация КПС графа. Интерпретируем графовую структуру:
Cg , CA,G = M A,VA, Σ A, Λ A I a ACg , ACg = M g , Σg , Λ 4
Aio ∈VA
где Λ4 ⊃ Λ3 , VA = {Ai0 |YXi i } – множество базовых алгоритмов [
U ( X ( Ai0 ) ∪ Y ( Ai0 )) U Ω(Cl ) U Ω(Cg )} – неоднородный носитель, Ω(Cl ), Ω(Cg ) – множество языковых и графовых конструкций, которые удовлетворяют Cl и Cg соответствен~ но; Λ4 ⊃ {( A6↵"||⇒~ "); ( A9↵":=)"); ( A10↵":=&"); ( A11↵"÷"); ( A12↵"#"); ( A13↵"+") , ( A14↵"U") , ( A15↵"U")} . Структура A,G Cg включает алгоритмы, реализующие такие операции:
A10 , A20 , A3 − A5 , A7 − A8 – аналогичны алгоритмам структуры C A ;
Ω A6 |σ,Ψg – полный вывод, где σ – аксиома, Ω – множество сформированных конструкций; A9 |ve1,v2,G – определение дуги e , соединяющей две заданные вершины v1, v2 в графе G ;
v A10 |x,V – нахождение вершины v с заданным значением атрибута веса x в множестве вершин V ;
L A11 |c,n, L – выполнение n операций из списка L , если c = true , L – список из n операций; A12 |Qx –вычисление мощности x множества Q ;
c A13 |a,b – сложения двух чисел a, b , c – результат;
G A14 |G1,G2 – объединение графов G1, G2 в G ;
Q
A15 |Q1,Q2 – объединение множеств Q1,Q2 в Q .
Реализация КПС графа. Реализация структуры ACg заключается в формировании графовых конструкций, которые имеют однозначное соответствие конструкциям Ω( ACT ) путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам аксиоматики:
ACg Ra Ω( ACg ) , где Ω(ACg ) ⊂ Ω( ACg ) . Сжатие графа
Данная графовая модель может быть использована для сравнения текстов, поиска подстроки в строке. Для ускорения процесса сравнения можно применить сжатия графа. Для этого рассмотрим такую структуру:
C = M , Σ, Λ S a CC = M C , ΣC , ΛC , где ΛC = {M C = V U E U Ω g , ΣC = {{⋅,:=},{→,|⇒,||⇒~ } U ΨC }, ΨC = {ψ C = si , gi }} .
Частичная аксиоматика операций.
Отношение подстановки и операции подстановки, частичного и полного вывода, конкатенации, присваивания аналогичны одноименным операциям КПС графа.
Интерпретация КПС сжатия графа. Алгоритмы операций, использованы в рассматриваемой структуре, аналогичны алгоритмам одноимённых операций структуры для построения графа.
Конкретизация КПС сжатия графа. Выполним конкретизацию структуры для сжатия графа: где M CK = M C U NCK , NCK = {σ} .
Рассмотрим правила, позволяющие сжать граф.
CC K a CCK = M CK , ΣCK , Λ CK , s1 = σ → Gσ , s2 = Gσ d→ Gσ , g1 = g2 = e1 := (vi , v j ,G), e2 := (v j , vk ,G), ÷ (routes↵e1 = routes↵e2 , 4, d := true, content↵vi := ⋅(content↵vi , content↵v j ), tokens↵vi := ⋅(tokens↵vi ,tokens↵v j ), end↵e1 := vk ) , s3 = σ → ε . Реализация КПС сжатия графа. Реализация интерпретируемой структуры A CC заключается в формиМесто работы авторов: