=Paper=
{{Paper
|id=Vol-1631/63-72
|storemode=property
|title=Constructive-synthesizing model of text graph representation
|pdfUrl=https://ceur-ws.org/Vol-1631/63-72.pdf
|volume=Vol-1631
|authors=Viktor Shynkarenko,Olena Kuropiatnyk
|dblpUrl=https://dblp.org/rec/conf/ukrprog/ShynkarenkoK16
}}
==Constructive-synthesizing model of text graph representation==
https://ceur-ws.org/Vol-1631/63-72.pdf
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
УДК 004.91:510.25+519.17
КОНСТРУКТИВНО-ПРОДУКЦИОННАЯ МОДЕЛЬ
ГРАФОВОГО ПРЕДСТАВЛЕНИЯ ТЕКСТА
В.И. Шинкаренко, Е.С. Куропятник
У статті розглянута графова модель тексту, що дозволяє прискорити обробку інформації. Дана модель дозволяє виявляти однако-
ві фрагменти в документах зі зміною порядку слідування речень та інших частин. Використання конструктивно-продукційних
структур для формалізації даної моделі є перспективним підходом для подальшої автоматизації процесу роботи з моделлю і від-
повідно з текстом.
Ключові слова: графова модель тексту, стискання графа, конструктивно-продукційна структура, співставлення текстів.
В статье рассмотрена графовая модель текста, позволяющая ускорить обработку информации. Данная модель позволяет выявлять
одинаковые фрагменты в документах с изменением порядка следования предложений и других частей. Использование конструк-
тивно-продукционных структур для формализации данной модели является перспективным подходом для дальнейшей автомати-
зации процесса работы с моделью и соответственно с текстом.
Ключевые слова: графовая модель, сжатие графа, конструктивно-продукционная структура, сопоставление текстов.
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.
Key words: graph model of the text, graph compression, constructive-synthesizing structure, text comparison.
Введение
Исследования и моделирование в различных отраслях науки и общественного производства, а также об-
разовательные процессы неотрывно связаны с обработкой уже имеющихся научных изданий, разработкой и
документированием новых методик, разработкой текстов компьютерных программ и тому подобное. Скорость
и интенсивность развития сфер науки, образования и производства, средств их информационной поддержки
порождает проблему обработки текстов, которая может быть разделена на несколько составляющих. На сегодня
наиболее актуальными являются поиск, сравнение, проверка правописания, выделение знаний. Разработка и
модернизация средств автоматизации для решения данных вопросов позволяет улучшить временные показате-
ли решения данных задач.
Существует множество методик для предварительной обработки текстов с целью упрощения их даль-
нейшей обработки. Среди них приведение символов к нижнему регистру и единой кодировки, удаление
стопслов и замена слов их грамматическими основами [1, 2], удаление или игнорирование пунктуационных
знаков [3], игнорирование пробелов, пустых строк, комментариев в текстах программ [4].
Особое внимание уделяется обработке текстов с целью выявления плагиата. Для этого разработано мно-
жество алгоритмов, моделей и программ на их основе [4]. Среди них графовое представление семантики текста
[3, 5], токенизации [6], морфологический анализ и синтаксический разбор [4], латентный семантический анализ
[6, 7] и др.
Представление текста в виде графовой модели [8] позволяет ускорить обработку текстовой информации.
Использование КПС для формализации данной модели является перспективным подходом для дальнейшей ав-
томатизации процесса работы с моделью и соответственно текстом.
Формализация средствами конструктивно-продукционных структур (КПС) позволяет описать не только
структуру объектов, но их свойства, определить допустимые операции над ними, алгоритмические элементы
построения конструкций на их основе [9]. Ранее была рассмотрена обобщенная КПС [10]. Данный подход явля-
ется универсальным для решения многих задач и применяется в разноплановых работах, посвященных адапта-
ции алгоритмов сжатия [11], формированию структур данных на логическом уровне [12], обобщенных грамма-
тик [13].
Особенностью КПС является возможность формирования конструкций различной природы на основе
операций подстановки, связывания, вывода и других вспомогательных операций, а также использования атри-
бутов [10].
Обобщенная конструктивно-продукционная структура
Обобщённая КПС определяется носителем M , сигнатурой Σ и аксиоматикой Λ C = M , Σ, Λ .
Носитель включает в себя конструктивные элементы с набором атрибутов. Сигнатура состоит из множе-
ства имен операций и отношений. Аксиоматика включает множества определений, аксиом, правил, свойств,
правил и пр. Носитель и сигнатура определяются аксиоматикой.
Преобразования КПС позволяют применять их для различных предметных областей. Специализация
КПС подразумевает определение атрибутов носителя, семантическую составляющую, а также определения ко-
нечного конкретного набора операций, их атрибутов. В ходе интерпретации каждой операции сигнатуры ста-
вится в соответствие алгоритм ее выполнения, являющийся элементом носителя некоторой алгоритмической
63
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
структуры [14]. Реализации КПС заключается в построении конструкций из элементов носителя КПС путем
выполнения алгоритмов, связанных с операциями сигнатуры.
Подход на основе КПС может быть использован для формализации понятий текста, его составляющих.
Особенности определения понятий текста, предложения, слова определяют носитель КПС и суть операций по
ее преобразованию. Так, например, если слово рассматривать с точки зрения естественного языка, то оно не
может включать символы-цифры, а если с точки зрения языков программирования, слово – лексема, которая
может содержать цифры и иные символы (имена переменных, функций, классов и т.п.). Таким образом, опреде-
ление подобных понятий может как расширять, так и сужать область определения элементов носителя, кон-
струкций, операций над ними.
Формализованная спецификация текста средствами КПС
Формализованная спецификация текста и его составляющих дает возможность автоматизировать разра-
ботку и обновление программ для решения поставленных задач.
Введем некоторые ограничения и дополнения аксиоматики и обозначений [10] в соответствие с рассмат-
риваемой предметной областью.
С данной целью определим КПС и выполним ее специализацию:
C = M , Σ, Λ S a S CT = M T , ΣT , ΛT , (1)
где M T – носитель, включающий все символы электронного представления текста и конструкции, построенные
на них, ΣT – операции и отношения на элементах M T , Λ T – аксиоматика, определяющая M T и Σ T .
Частичная аксиоматика носителя. Носитель включает множества терминалов и нетерминалов.
M T ⊃ TT U N T , TT = TK U TL U TD U TN U TNP , TK , TL – множество кириллических и латинских символов соответ-
ственно, которые входят в текст; TD – множества символов-разделителей для отображения знаков пунктуации
и пробела; T N – множество цифр; TNP – множество непечатных символов, не включая пробел; N T – множе-
ство нетерминалов (вспомогательных символов).
Элементы носителя w mi имеют набор атрибутов wi = type, code . Принадлежность конкретного атрибу-
та элементу носителя будем обозначать wi ↵m . Тип ( type↵m ) принимает значение терминал/нетерминал
( ter / nter ). Атрибут code указывает на машинное представление символа-терминала. В качестве идентифици-
рующего атрибута выступает код.
Частичная аксиоматика отношений и операций. Сигнатура Σ T состоит из множества операций
Σ T = Ξ, Θ, Φ, {→} U Ψ , Ξ = {⋅} , где Ξ – множество операций связывания, Θ – множество операций вывода,
Φ = {=, :=} – множество операций над атрибутами; Ψ – множество правил продукций вида ψ i :< si , g i > , i –
номер правила, s – последовательность операций подстановки, g – последовательность операций над атрибу-
тами, « → » – отношение подстановки. Θ = {⇒, |⇒, ||⇒} – операции подстановки, частичного и полного вывода.
Операция конкатенации ⋅(mi , m j ) связывает два элемента носителя. Результатом выполнения операции
является форма wl l . Форма может быть построена таким образом:
− wl l = w0 ⋅( w j m j , wk mk ) для ∀ wi mi ∈ M T ;
− wl l = w j m j , если l = w0 ⋅(ε, w j m j )= w0 ⋅( w j m j , ε) , где ε – пустой элемент;
− wl l = w0 ⋅( w1 l1 , w2 l 2 ) для ∀ wi l i = w j m j | ⋅( w j m j , wk mk ) | ⋅( w j l j , wk mk ), ∀ wi mi ∈ M T .
Множество значений атрибутов формы определяется совокупностью значений атрибутов ее составляю-
щих.
Сентенциальная форма – форма, полученная в результате вывода из аксиомы (начального нетерминаль-
ного символа, принадлежащего носителю) согласно правилам вывода конкретизированной КПС.
Формы, в которых отсутствуют нетерминальные элементы – конструкции. Конструкции имеют такие
атрибуты: тип языковой конструкции, набор кодов. Атрибут тип ( type↵l ) может принимать такие значения:
к-слово, к-предложение, к-абзац, к-текст.
Отношение подстановки – отношение с атрибутами wi li w → w j l j , где li , l j – сентенциальные формы [11].
64
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Для заданной формы wl l = w0 ⋅( w1 l1 , w2 l 2 , K , wh l h , K , wk l k ) и доступного отношения подстановки
w p → ( wh l h , wq l q ) такого, что wh l h – подформа wl l результатом трехместной операции подстановки
wl*
l * = w p ⇒( wh l h , wq l q , wl l ) будет форма w* l * = w0 ⋅( w1 l1 , w2 l 2 , K , wq l q , K , wk l k ) .
l
Двухместная операция частичного вывода w* l * = w p |⇒ (Ψ , wl l ) ( |⇒∈ Θ ) заключается в:
l
− выборе одного из доступных правил подстановки ψ r : s r , g r с отношениями подстановки s r ;
− выполнении на его основе операций подстановки;
− выполнении операций над атрибутами g r в соответствующей последовательности.
Операция полного вывода или просто вывода ( ||⇒∈ Θ ) заключается в пошаговом преобразовании форм,
начиная с начального нетерминала и заканчивая конструкцией, удовлетворяющей условию окончания вывода,
что подразумевает циклическое выполнение операций частичного вывода. Операция двухместная
wl*
l * = ||⇒ (Ψ , wl l ) .
Операция присваивания := (a, b) копирует значение операнда b в a .
Операция = ( wi , w j ) выполняет сравнения атрибутов. Результатом операции сравнения является значе-
ние «истина», если wi = w j , иначе – «ложь».
Элемент принадлежит форме m∈l , если ∃ l1 , l2 , l3 : l = ⋅(l1 , l 2 ) & ((l1 = ⋅(l3 , m) | l1 = ⋅(m, l3 )) | l 2 = ⋅(l3 , m)) , где
l1 , l 2 , l3 – формы, образованные с помощью операции конкатенации.
Расширение аксиоматики носителя. Конструкция является к-словом type↵l = cw , если
∀mi ∈ l : mi ∈ TK U TL U TN .
Конструкция является к-предложением type↵l = cs , если l = ⋅(l1 , m), m ∈ TSD , TSD = {"!" , " ?", ".", "..."} ,
TSD ⊂ TD .
Конструкция является к-абзацем type↵l = cp , если l = ⋅(l1 , l 2 ) & l 2 = ⋅(m1 , m2 ) , code↵m1 = 13,
code↵m2 = 10 (переход на новую строку, возврат каретки).
К-абзац может включать в себя несколько предложений, к-предложение – несколько абзацев.
Конструкция является к-текстом type↵l = ct , если l = ⋅(l1 , l 2 ) & type↵l1 = cp & (type↵l 2 = cp | l 2 = ε) и
l1 , l 2 имеют смысловую связь.
Интерпретация КПС текста. Частично интерпретируем структуру CT (1) с помощью алгоритмической
структуры C A :
CT , C A,T = M A,T ,V A,T , Σ A,T , Λ A,T I a A CT , A CT = M 1 , Σ1 , Λ 1 , (2)
0 Y
где Λ1 ⊃ Λ T , VA,T = {Ai | Xi i } – множество базовых алгоритмов [10, 13], X i , Yi – множества определений и зна-
0 Y
чений алгоритма Ai | Xi . Λ A,T = {M A,T = U ( X ( Ai0 ) U Y ( Ai0 )) U Ω(CT )} – неоднородный носитель, Ω(CT ) –
i
Aio∈VA,T
множество языковых конструкций, которые удовлетворяют CT ; Λ1 = {( A3 |ll1, l2 ↵"⋅"); ( A4 |lfi, l , f ↵" ⇒" );
h q i
f
( A5 | f j, Ψ ↵" |⇒" );
i
( A6 | σΩ, Ψ ↵"||⇒" ); (A | a
7 a,b ↵":=" ); ( A8 | ca , b ↵" =" )} .
Структура A CT включает алгоритмы выполнения операций:
A ⋅A
− A10 | Ai , Aj – композиция алгоритмов, Ai ⋅ A j – последовательное выполнение алгоритма A j после ал-
i j
горитма Ai ;
− A20 | ZA1 – условное выполнение: алгоритм Ai выполняется, если условие Z истинно;
− A3 | ll1 , l2 –конкатенация, l , l1 , l 2 – формы;
65
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
− A4 |lf i , l , f – подстановка, l h , l q , f i – формы;
h q i
f Ω
− A5 | f j, Ψ , A6 | σ,
i
Ψ – частичный и полный вывод, где f i , 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 .
Правило s 2 − s 4 позволяют определить составляющие текста – абзацы (одного или много), определив
значение соответствующего атрибута как абзац
s 2 = τ → απ , g 2 = kind↵α := cp , s3 = π → απ , s 4 = π → m1m2 ,
где m1 , m 2 – символы возврата каретки и перехода на новую строку.
Правила s 2 − s 4 позволяют определить составляющие абзаца – предложение (много или одно), опреде-
лив значение соответствующего атрибута как предложение
s5 = α → ργα , s6 = α → ργ , g 6 = kind↵ρ := cs , s7 = γ → mend ,
где mend ∈ TSD – символ признак окончания предложения.
Правила s8 − s9 позволяют определить составляющие предложения: одно или более слов
s8 = ρ → κ , g 8 = kind↵κ := cw , s9 = ρ → κδρ .
Правила s10 − s11 позволяют определить разделитель между словами
s10 = δ → msep , s11 = δ → msepδ ,
где m sep ∈TWD , TWD = T D \ TSD .
Правила s12 − s13 позволяют построить слово из одной и более букв:
s12 = κ → mcκ , s13 = κ → mc ,
где mc ∈TK U TL U TN .
Тут под записью типа κ → mc , mc ∈ TK U TL U T N следует понимать множество альтернативных правил,
что можно также записать в виде κ → a | б | в... .
Операции над атрибутами выполняются после операции частичного вывода.
Реализация КПС текста. Реализация структуры (2) заключается в формировании языковых конструк-
ций из элементов ее носителя путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам
аксиоматики:
66
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
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’». Здесь в кавычки
взяты символы пробела и перехода к новому абзацу.
Для обработки конструкций рассмотрим задачи синтеза и анализа графовой модели текста [8].
Синтез графа конструктивно-продукционными структурами
Пусть есть множество языковых конструкций Ω ( A CT ) , порожденное структурой A CT (2). Задача состо-
ит в определенные структуры C g , порождающей множество конструкций-графов Ω (C g ) такое, что существу-
ет биективное отображение f : Ω ( A СT ) → Ω g (C g ) .
Для решения поставленной задачи определим структуру и специализируем ее соответствующим обра-
зом:
C = M , Σ, Λ S a Cg = M g ,Σg ,Λg ,
где M g – расширяемый носитель, включающий множества конструкций-графов, языковых конструкций и их
элементов, Σ g – множество операций и отношений на элементах M g , Λ g – аксиоматика.
Частичная аксиоматика носителя. Носитель включает множества терминальных и нетерминальных
элементов M g = Tg U N g . Терминалами являются языковые конструкции, построенные КПС (2) и их состав-
ляющие ( TT ), а также конструкции графов и их составляющих T g = Ω U Ω g U TT U V U E , Ω g – множество
конструкций-графов, V , E – множества вершин и дуг с их атрибутами.
Вершина имеет атрибуты w v = id , content, tokens , id – идентификатор, принимает целочисленные зна-
чения, content – часть текстовой конструкции, tokens – список, содержащий признаки начала языковых кон-
струкций. Атрибуты дуги w e = 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 , g i > , i – номер правила, s – последовательность операций подстановки, g – последователь-
ность операций над атрибутами, « → » – отношение подстановки.
67
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
)
Операция e := (v1 , v 2 , G ) заключается в определении дуги e , соединяющей вершины v1 и v 2 графа 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 , включающего объединенные множества вершин и дуг исходных графов wg G = V,E ,
V = V1 U V2 , E = E1 U E 2 , w1 G1 =< V1 , E1 > , w2 G2 =< V2 , E 2 > , при этом U – традиционная операция объедине-
ния множеств.
Отношение подстановки имеет вид
ψ i = si , g i , s i = s i , ~si , g i = g i , g~i ,
где s i , ~
s i – отношение подстановки для распознавания языковой конструкции и построения конструкции графа
соответственно, g , g~ – операции над атрибутами языковой конструкции и графа, его вершин и дуг соответ-
i i
ственно. В случае если операции над атрибутами не выполняются, отношение подстановки имеет вид
ψ = s, ε .
~ (Ψ , l ) состоит в:
Операция полного вывода ||⇒ wl
− определении входной конструкции, набора отношений подстановки и доступных из них;
− выполнении операции частичного вывода, пока языковая конструкция ω ∈ Ω полностью не распо-
знана, то есть для каждого ее элемента ωi в графе нет соответствующего элемента-вершины или форма графа
содержит нетерминалы.
Результатом операции вывода является конструкция-граф.
Конкретизация КПС графа. Выполним конкретизацию структуры C g :
Cg K a K Cg = M 3 , Σ3 , Λ3 ,
где Λ 3 ⊃ Λ g , Λ 3 ⊃ { M 3 ⊃ M g , c ∈ TT , N g = {α, δ} , Tg ⊃ {G, G * , G ** } , G = V , E , V = {v} , E = ∅ ,
G * =< V * , G * > , V * = {v1* , v 2* } , E * = {e1* } , G ** =< V ** , G ** > , V ** = {v1** , v 2** } , E ** = {e1** }} .
Для распознавания языковых конструкций определим такие правила:
s1 = σ d1 → cσ , g1 = ÷ (code↵c ≠ EOF ,1, d1 := true) , s 2 = σ d 2 → c , g 2 = ÷ (code↵c = EOF ,1, d 2 := true) ,
где с – символ текста, кроме EOF – признак конца текста в его электронном представлении.
Следующие правила описывают добавление первой вершины в пустой граф:
~ Gα , g~ = id↵v :=#V , content↵v: = c,tokens :=< cw, cs, cp, ct > ,
~s = σ →
1 1
start_v↵G: = v, current_v↵G: = v,last_v↵G: = v, amount _ l↵G := 0 .
Правило ~
s 2 позволяет добавить к графу новую вершину и дугу, связывающую новую вершину с теку-
щей в графе
~ ~ ~
s2 := Gα d * →
~ )
U(G, G * )α , U (G, G * )α → Gα , g~2 = v1 :=& (c,V ), e1 := (current _ v↵G, v, G ) ,
1
68
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
÷ (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* := v2* , routes↵e1* := {amount _ l↵G},
÷ (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 = α d * → U(G, G ** )α , U (G, G ** )α → Gα
2
, g~ 3 = v1 :=& (c,V ), e1 :=) (current _ v↵G, v1 , G ),
÷ (v1 = start _ v↵G & id↵e1 = 0,14, d 2* := 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 ) .
Правило ~
s 4 позволяет изменить нагрузку имеющейся дуги:
~ )
s 4 = Gα d * → Gα , g~4 = v1 :=& (c,V↵G ) , e1 := (current _ v↵G, v1 , G ) , ÷ (id↵v1 ≠ 0 & id↵e1 ≠ 0, 3, d 3* := true,
3
÷( 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 = α →
Интерпретация КПС графа. Интерпретируем графовую структуру:
C g , C A, G = M A , V A , Σ A , Λ A Ia A Cg , ACg = M g , Σg , Λ 4 ,
0 Y
где Λ 4 ⊃ Λ 3 , VA = {Ai | Xi i } – множество базовых алгоритмов [10, 13], X i , Yi – множества определений та зна-
чений алгоритма Ai0 |YXi . Λ A = {M A = U ( X ( Ai0 ) ∪ Y ( Ai0 )) U Ω(Cl ) U Ω(C g )} – неоднородный носитель,
i
Aio ∈V A
69
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Ω(Cl ), Ω(Cg ) – множество языковых и графовых конструкций, которые удовлетворяют C l и C g соответствен-
~ " ); ( A ↵":=) " ); ( A ↵":=& " ); ( A ↵"÷" ); ( A ↵" # " ); ( A ↵"+" ) , ( A ↵"~
но; Λ 4 ⊃ {( A6 ↵"||⇒ 9 10 11 12 13 14 U" ) , ( A15 ↵"U" )} .
Структура A, G C g включает алгоритмы, реализующие такие операции:
− A10 , A20 , A3 − A5 , A7 − A8 – аналогичны алгоритмам структуры C A ;
− A6 | σΩ, Ψg – полный вывод, где σ – аксиома, Ω – множество сформированных конструкций;
− A9 | ve1 , v2 , G – определение дуги e , соединяющей две заданные вершины v1 , v 2 в графе G ;
− A10 |vx,V – нахождение вершины v с заданным значением атрибута веса x в множестве вершин V ;
− A11 | cL, n, L – выполнение n операций из списка L , если c = true , L – список из n операций;
− A12 |Qx –вычисление мощности x множества Q ;
− A13 |ca , b – сложения двух чисел a, b , c – результат;
− A14 |G
G1 , G2 – объединение графов G1 , G 2 в G ;
− A15 |Q
Q , Q – объединение множеств Q1 ,Q2 в Q .
1 2
Реализация КПС графа. Реализация структуры A C g заключается в формировании графовых конструк-
ций, которые имеют однозначное соответствие конструкциям Ω ( A CT ) путем выполнения алгоритмов, связан-
ных с операциями сигнатуры, по правилам аксиоматики:
A Cg R a Ω( A Cg ) ,
где Ω( A Cg ) ⊂ Ω( A Cg ) .
Сжатие графа
Данная графовая модель может быть использована для сравнения текстов, поиска подстроки в строке.
Для ускорения процесса сравнения можно применить сжатия графа. Для этого рассмотрим такую структуру:
C = M , Σ, Λ S a C C = M C , Σ C , Λ C ,
~ } U Ψ }, Ψ = {ψ = s , g }} .
где Λ C = {M C = V U E U Ω g , Σ C = {{⋅, :=}, {→, |⇒, ||⇒ C C C i i
Частичная аксиоматика операций.
Отношение подстановки и операции подстановки, частичного и полного вывода, конкатенации, присваи-
вания аналогичны одноименным операциям КПС графа.
Интерпретация КПС сжатия графа. Алгоритмы операций, использованы в рассматриваемой структу-
ре, аналогичны алгоритмам одноимённых операций структуры для построения графа.
Конкретизация КПС сжатия графа. Выполним конкретизацию структуры для сжатия графа:
C C K a C CK = M CK , Σ CK , Λ CK ,
где M CK = M C U N CK , N CK = {σ} .
Рассмотрим правила, позволяющие сжать граф.
s1 = σ → Gσ , s2 = Gσ d→ Gσ ,
g1 = g 2 = e1 := (vi , v j , G ), e2 := (v j , v k , G ), ÷ (routes↵e1 = routes↵e2 , 4, d := true, content↵v i := ⋅(content↵vi , content↵v j ),
tokens↵vi := ⋅(tokens↵vi , tokens↵v j ), end↵e1 := v k ) , s3 = σ → ε .
70
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Реализация КПС сжатия графа. Реализация интерпретируемой структуры A CC заключается в форми-
ровании графовых конструкций, которые имеют однозначное соответствие конструкциям Ω ( A CT ) и Ω ( A C g )
путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам аксиоматики:
A CC R a Ω ( A CC ) ,
где Ω( A CC ) ⊂ Ω( A CC ) .
Выводы
Проблема поиска информации, ее сравнении требует автоматизированных средств решения. С данной
целью целесообразной является разработка средств формализации для представления текстов.
Формальные грамматические и алгоритмические структуры использованы как средство формализации
текста в виде конструкций с атрибутами. Конструктивно-продукционный подход позволяет определить порядок
конструирования и обработки текста, представить его в виде графовых структур с целью снижения алгоритми-
ческой сложности.
В рамках рассмотренного атрибутивного подхода могут быть решены задачи по таким направлениям, как
семантический поиск и сопоставление текстов для выявления заимствований, что является ключевыми момен-
тами в решении проблем плагиата.
1. Efstathios Stamatatos Plagiarism Detection Based on Structural Information – CIKM’11, October 24–28, 2011, Glasgow, Scotland, UK.
2. Leilei Kong, Zhimao Lu, Haoliang Qi and Zhongyuan Han. Detecting High Obfuscation Plagiarism: Exploring Multi-Features Fusion via Ma-
chine Learning // International Journal of u-and e-Service, Science and Technology – 2014. – Vol. 7, N 4. – P. 385–396.
3. Ahmed Hamza Osman, Naomie Salim, Mohammed Salem Binwahlan. Plagiarism Detection Using Graph-Based Representation // JOURNAL
OF COMPUTING. – 2010. – Vol. 2, N 4. – P. 36 – 41.
4. Bin-Habtoor A.S., Zaher M.A. A Survey on Plagiarism Detection Systems [Text] // International Journal of Computer Theory and Engineering. –
2012. – Vol. 4, N 2. – P. 185–188.
5. Ahmed Hamza Osman, Naomie Salim, Mohammed Salem Binwahlan, Hanza Hentably, Albaraa M. Ali. Conceptual Similarity and graph-based
method for plagiarism detection // Journal of Theoretical and Applied Information Technology. – 31st October 2011. – Vol. 32, N 2. –
P. 135–145.
6. Mozgovoy M. Maxim Mozgovoy Desktop Tools for Offline Plagiarism Detection in Computer Programs // Informatics in Education. – 2006. –
Vol. 5, N 1. – P. 97–112.
7. Mozgovoy M., Kakkonen T., Cosma G. Automatic Student Plagiarism Detection: Future Perspectives // Journal of Educational Computing Re-
search. – 2010. – Vol. 43(4). – P. 507–527.
8. Шинкаренко В.І., Куроп’ятник О.С. Система контролю плагіату в студентських роботах // Восточно-Европейский журнал передовых
технологий. – Харьков: Технологический центр, 2012. – № 4/2 (58). – С. 32–36.
9. Ільман В.М., Скалозуб В.В., Шинкаренко В.І. Формальні структури та їх застосування: мононографія. – Д.: Вид-во Дніпропетр. нац. ун-
ту залізн. трансп. ім. акад. В. Лазаряна, 2009. – 205 с.
10. Шинкаренко В.И., Ильман В.М. Конструктивно-продукционные структуры и их грамматические интерпретации. I. Обобщенная фор-
мальная конструктивно-продукционная структура // Кибернетика и системный анализ. – Киев, 2014. – Т. 50, № 5 – С. 8–16.
11. Шинкаренко В.И. , Васецкая Т.Н. Моделирования процесса адаптации алгоритмов сжатия средствами конструктивно-продукционных
структур // Кибернетика и системный анализ. – 2015. – Т. 51. – № 6. – С. 19–34.
12. Шинкаренко В.И., Ильман В.М., Забула Г.В. Конструктивно-продукционная модель структур данных на логическом уровне // Проблемы
программирования. – 2014. – № 2–3. – С. 10–16.
13. Шинкаренко В.И., Ильман В.М. Конструктивно-продукционные структуры и их грамматические интерпретации. II. Уточняющие пре-
образования // Кибернетика и системный анализ. – 2014. – № 6. – С. 15–28.
14. Шинкаренко В.И., Ильман В.М., Скалозуб В.В. Структурные модели алгоритмов в задачах прикладного программирования. Часть I.
Формальные алгоритмические структуры // Кибернетика и системный анализ. – 2009. – № 3. – С. 3–14.
References
1. EFSTATHIOS, STAMATATOS (2011) Plagiarism Detection Based on Structural Information in CIKM’11. Glasgow, Scotland, UK October 24–
28, 2011.
2. LEILEI KONG & ZHIMAO LU & HAOLIANG QI & ZHONGYUAN HAN (2014) Detecting High Obfuscation Plagiarism: Exploring Multi-
Features Fusion via Machine Learning. International Journal of u-and e-Service, Science and Technology. 7 (4). P. 385–396.
3. AHMED HAMZA OSMAN & NAOMIE SALIM & MOHAMMED SALEM BINWAHLAN (2010) Plagiarism Detection Using Graph-Based
Representation Journal of Computing. 2 (4). P. 36 – 41.
4. A. S. BIN-HABTOOR & M. A. ZAHER (2012) A Survey on Plagiarism Detection Systems. International Journal of Computer Theory and
Engineering. 4 (2). P. 185 – 188.
5. AHMED HAMZA OSMAN & NAOMIE SALIM & MOHAMMED SALEM BINWAHLAN & HANZA HENTABLY & ALBARAA M. ALI
(2011) Conceptual Similarity and graph-based method for plagiarism detection. Journal of Theoretical and Applied Information Technology. 32
(2). P. 135–145.
6. MOZGOVOY, M. (2006) Desktop Tools for Offline Plagiarism Detection in Computer Programs. Informatics in Education. 5 (1). pp. 97–112
7. M. MOZGOVOY & T. KAKKONEN & G. COSMA (2010) Automatic Student Plagiarism Detection: Future Perspectives. Journal of
Educational Computing Research. 43 (4). P. 507-527.
71
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
8. V. SHYNKARENKO & E. KUROPYATNICK (2012) Monitoring system of plagiarism in student works. East Europe Journal of Enterprise
Technologies. 4/2 (58). p. 32 – 36.
9. V. ILMAN, V. SKALOZUB & V. SHYNKARENKO Formal structures and their applications: monograph. Dnipropetrovsk: DNURT named
after academician V. Lazaryan.
10. SHYNKARENKO V. & ILMAN V. (2014) Constructive-synthesizing structures and their grammatical interpretations. I. Generalized formal
constructive-synthesizing structure. Cybernetics and Systems Analysis. 50 (5). P. 8–16.
11. SHYNKARENKO V. & VASETSKA T. (2015) Modeling the Adaptation of Compression Algorithms by Means of Constructive-Synthesizing
Structures. Cybernetics and Systems Analysis. 51(6). P. 19 – 34.
12. SHYNKARENKO V. I., ILMAN V. M., ZABULA H. V. (2014) Logical view for construction-synthesis model of data structeres. Problems in
programming. 2-3 Special issue.
13. SHYNKARENKO V. & ILMAN V (2014). Constructive-production structures and their grammatical interpretations. II. Clarifying conversions.
Cybernetics and Systems Analysis. 6. P. 15 – 28.
14. SHYNKARENKO V. & ILMAN V., SKALOZUB V. (2009) Structural models of algorithms in problems of applied programming. i. formal
algorithmic structures. Cybernetics and Systems Analysis. 3. P. 3 – 14.
Об авторах:
Шинкаренко Виктор Иванович,
доктор технических наук, профессор,
заведующий кафедрой Компьютерные информационные технологии.
Количество научных публикаций в украинских изданиях – 200.
Индекс Гирша – 5.
http://orcid.org/0000-0001-8738-7225,
Куропятник Елена Сергеевна,
аспирант кафедры Компьютерные информационные технологии.
Количество научных публикаций в украинских изданиях – 14.
Индекс Гирша – 1.
http://orcid.org/0000-0003-2286-884X.
Место работы авторов:
Днепропетровский национальный университет
железнодорожного транспорта имени академика В. Лазаряна.
49010, Днепропетровск, ул. Лазаряна, 2, ДНУЖТ, кафедра КИТ.
Тел.: (056) 373 1535.
E-mail: shinkarenko_vi@ua.fm, elenadiit@rambler.ru
72