Конструктивно-продукційна модель графового представлення тексту
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...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/181 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозиторії
Problems in programming| id |
pp_isofts_kiev_ua-article-181 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/69/0a8f5f0f032cd89a5178bf159a6d5969.pdf |
| spelling |
pp_isofts_kiev_ua-article-1812024-04-28T13:09:56Z Constructive-synthesizing model of text graph representation Конструктивно-продукционная модель графового представления текста Конструктивно-продукційна модель графового представлення тексту Shynkarenko, V.I. Kuropiatnyk, O.S. graph model of the text; graph compression; constructive-synthesizing structure; text comparison UDC 004.91:510.25+519.17 графовая модель; сжатие графа; конструктивно-продукционная структура; сопоставление текстов УДК 004.91:510.25+519.17 графова модель тексту; стискання графа; конструктивно-продукційна структура; співставлення текстів УДК 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.Problems in programming 2016; 2-3: 63-72 В статье рассмотрена графовая модель текста, позволяющая ускорить обработку информации. Данная модель позволяет выявлять одинаковые фрагменты в документах с изменением порядка следования предложений и других частей. Использование конструктивно-продукционных структур для формализации данной модели является перспективным подходом для дальнейшей автоматизации процесса работы с моделью и соответственно с текстом.Problems in programming 2016; 2-3: 63-72 У статті розглянута графова модель тексту, що дозволяє прискорити обробку інформації. Дана модель дозволяє виявляти однакові фрагменти в документах зі зміною порядку слідування речень та інших частин. Використання конструктивно-продукційних структур для формалізації даної моделі є перспективним підходом для подальшої автоматизації процесу роботи з моделлю і від-повідно з текстом.Problems in programming 2016; 2-3: 63-72 Інститут програмних систем НАН України 2018-07-06 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/181 10.15407/pp2016.02-03.063 PROBLEMS IN PROGRAMMING; No 2-3 (2016); 63-72 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2016); 63-72 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2016); 63-72 1727-4907 10.15407/pp2016.02-03 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/181/176 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T13:09:56Z |
| collection |
OJS |
| language |
rus |
| topic |
graph model of the text graph compression constructive-synthesizing structure text comparison UDC 004.91:510.25+519.17 графовая модель сжатие графа конструктивно-продукционная структура сопоставление текстов УДК 004.91:510.25+519.17 графова модель тексту стискання графа конструктивно-продукційна структура співставлення текстів УДК 004.91:510.25+519.17 |
| spellingShingle |
graph model of the text graph compression constructive-synthesizing structure text comparison UDC 004.91:510.25+519.17 графовая модель сжатие графа конструктивно-продукционная структура сопоставление текстов УДК 004.91:510.25+519.17 графова модель тексту стискання графа конструктивно-продукційна структура співставлення текстів УДК 004.91:510.25+519.17 Shynkarenko, V.I. Kuropiatnyk, O.S. Конструктивно-продукційна модель графового представлення тексту |
| topic_facet |
graph model of the text graph compression constructive-synthesizing structure text comparison UDC 004.91:510.25+519.17 графовая модель сжатие графа конструктивно-продукционная структура сопоставление текстов УДК 004.91:510.25+519.17 графова модель тексту стискання графа конструктивно-продукційна структура співставлення текстів УДК 004.91:510.25+519.17 |
| format |
Article |
| author |
Shynkarenko, V.I. Kuropiatnyk, O.S. |
| author_facet |
Shynkarenko, V.I. Kuropiatnyk, O.S. |
| author_sort |
Shynkarenko, V.I. |
| title |
Конструктивно-продукційна модель графового представлення тексту |
| title_short |
Конструктивно-продукційна модель графового представлення тексту |
| title_full |
Конструктивно-продукційна модель графового представлення тексту |
| title_fullStr |
Конструктивно-продукційна модель графового представлення тексту |
| title_full_unstemmed |
Конструктивно-продукційна модель графового представлення тексту |
| title_sort |
конструктивно-продукційна модель графового представлення тексту |
| title_alt |
Constructive-synthesizing model of text graph representation Конструктивно-продукционная модель графового представления текста |
| description |
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.Problems in programming 2016; 2-3: 63-72 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/181 |
| work_keys_str_mv |
AT shynkarenkovi constructivesynthesizingmodeloftextgraphrepresentation AT kuropiatnykos constructivesynthesizingmodeloftextgraphrepresentation AT shynkarenkovi konstruktivnoprodukcionnaâmodelʹgrafovogopredstavleniâteksta AT kuropiatnykos konstruktivnoprodukcionnaâmodelʹgrafovogopredstavleniâteksta AT shynkarenkovi konstruktivnoprodukcíjnamodelʹgrafovogopredstavlennâtekstu AT kuropiatnykos konstruktivnoprodukcíjnamodelʹgrafovogopredstavlennâtekstu |
| first_indexed |
2024-09-16T04:08:13Z |
| last_indexed |
2024-09-16T04:08:13Z |
| _version_ |
1812407867308769280 |
| fulltext |
Теоретичні та методологічні основи програмування
© В.И. Шинкаренко, Е.С. Куропятник, 2016
ISSN 1727-4907. Проблеми програмування. 2016. № 2–3. Спеціальний випуск 63
УДК 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 , сигнатурой и аксиоматикой ,,MC .
Носитель включает в себя конструктивные элементы с набором атрибутов. Сигнатура состоит из множе-
ства имен операций и отношений. Аксиоматика включает множества определений, аксиом, правил, свойств,
правил и пр. Носитель и сигнатура определяются аксиоматикой.
Преобразования КПС позволяют применять их для различных предметных областей. Специализация
КПС подразумевает определение атрибутов носителя, семантическую составляющую, а также определения ко-
нечного конкретного набора операций, их атрибутов. В ходе интерпретации каждой операции сигнатуры ста-
Теоретичні та методологічні основи програмування
64
вится в соответствие алгоритм ее выполнения, являющийся элементом носителя некоторой алгоритмической
структуры [14]. Реализации КПС заключается в построении конструкций из элементов носителя КПС путем
выполнения алгоритмов, связанных с операциями сигнатуры.
Подход на основе КПС может быть использован для формализации понятий текста, его составляющих.
Особенности определения понятий текста, предложения, слова определяют носитель КПС и суть операций по
ее преобразованию. Так, например, если слово рассматривать с точки зрения естественного языка, то оно не
может включать символы-цифры, а если с точки зрения языков программирования, слово – лексема, которая
может содержать цифры и иные символы (имена переменных, функций, классов и т.п.). Таким образом, опреде-
ление подобных понятий может как расширять, так и сужать область определения элементов носителя, кон-
струкций, операций над ними.
Формализованная спецификация текста средствами КПС
Формализованная спецификация текста и его составляющих дает возможность автоматизировать разра-
ботку и обновление программ для решения поставленных задач.
Введем некоторые ограничения и дополнения аксиоматики и обозначений [10] в соответствие с рассмат-
риваемой предметной областью.
С данной целью определим КПС и выполним ее специализацию:
TTTTSS MCMC ,,,, , (1)
где TM – носитель, включающий все символы электронного представления текста и конструкции, построенные
на них, T – операции и отношения на элементах TM , T – аксиоматика, определяющая TM и T .
Частичная аксиоматика носителя. Носитель включает множества терминалов и нетерминалов.
NPNDLKTTTT TTTTTTNTM , , LK TT , – множество кириллических и латинских символов соответ-
ственно, которые входят в текст; DT – множества символов-разделителей для отображения знаков пунктуации
и пробела; NT – множество цифр; NPT – множество непечатных символов, не включая пробел;
TN – множе-
ство нетерминалов (вспомогательных символов).
Элементы носителя iw m имеют набор атрибутов codetypewi , . Принадлежность конкретного атрибу-
та элементу носителя будем обозначать mwi . Тип ( mtype ) принимает значение терминал/нетерминал
( nterter / ). Атрибут code указывает на машинное представление символа-терминала. В качестве идентифици-
рующего атрибута выступает код.
Частичная аксиоматика отношений и операций. Сигнатура T состоит из множества операций
}{,,,T , }{ , где – множество операций связывания, – множество операций вывода,
}:,{ – множество операций над атрибутами; – множество правил продукций вида iii gs ,: , i –
номер правила, s – последовательность операций подстановки, g – последовательность операций над атрибу-
тами, « » – отношение подстановки. }||,|,{ – операции подстановки, частичного и полного вывода.
Операция конкатенации ),( ji mm связывает два элемента носителя. Результатом выполнения операции
является форма l
lw . Форма может быть построена таким образом:
),(
0 kwjwww mml
kjl
для Tiw Mm
i
;
jww ml
jl
, если ),(),(
00
jwwjww mml
jj
, где – пустой элемент;
),( 21 210
lll wwwwl
для Tiwkwjwkwjwjwiw Mmmlmmml
ikjkjji
),,(|),(| .
Множество значений атрибутов формы определяется совокупностью значений атрибутов ее составляю-
щих.
Сентенциальная форма – форма, полученная в результате вывода из аксиомы (начального нетерминаль-
ного символа, принадлежащего носителю) согласно правилам вывода конкретизированной КПС.
Формы, в которых отсутствуют нетерминальные элементы – конструкции. Конструкции имеют такие
атрибуты: тип языковой конструкции, набор кодов. Атрибут тип ( ltype ) может принимать такие значения:
к-слово, к-предложение, к-абзац, к-текст.
Отношение подстановки – отношение с атрибутами jwwiw ll
ji
, где ji ll , – сентенциальные формы [11].
Теоретичні та методологічні основи програмування
65
Для заданной формы ),,,,,( 21 210 kwhwwwww lllll
khl
и доступного отношения подстановки
),( qwhww ll
qhp
такого, что hw l
h
– подформа l
lw результатом трехместной операции подстановки
),,(*
* llll
lqhpl
wqwhwww
будет форма ),,,,,( 21
*
210
* kwqwwwww
lllll
kql
.
Двухместная операция частичного вывода ),(|*
* ll
lpl
www
( | ) заключается в:
выборе одного из доступных правил подстановки rrr gs ,: с отношениями подстановки rs ;
выполнении на его основе операций подстановки;
выполнении операций над атрибутами rg в соответствующей последовательности.
Операция полного вывода или просто вывода ( || ) заключается в пошаговом преобразовании форм,
начиная с начального нетерминала и заканчивая конструкцией, удовлетворяющей условию окончания вывода,
что подразумевает циклическое выполнение операций частичного вывода. Операция двухместная
),(||*
* ll
ll
ww
.
Операция присваивания ),(: ba копирует значение операнда b в a .
Операция ),( ji ww выполняет сравнения атрибутов. Результатом операции сравнения является значе-
ние «истина», если ji ww , иначе – «ложь».
Элемент принадлежит форме lm , если :,, 321 lll )),(|)),(|),(((&),( 32313121 mlllmlmlllll , где
321 ,, lll – формы, образованные с помощью операции конкатенации.
Расширение аксиоматики носителя. Конструкция является к-словом cwltype , если
NLKii TTTmlm : .
Конструкция является к-предложением csltype , если SDTmmll ),,( 1 , }"...",".",?"","!{"SDT ,
DSD TT .
Конструкция является к-абзацем cpltype , если ),( 21 lll ),(& 212 mml , ,131 mcode
102 mcode (переход на новую строку, возврат каретки).
К-абзац может включать в себя несколько предложений, к-предложение – несколько абзацев.
Конструкция является к-текстом ctltype , если ),( 21 lll cpltype 1& )|(& 22 lcpltype и
21, ll имеют смысловую связь.
Интерпретация КПС текста. Частично интерпретируем структуру TC (1) с помощью алгоритмической
структуры AC :
111,,,,, ,,,,,,, MCCVMCC TATAITATATATATAT , (2)
где T1 , }|{ 0
,
i
i
Y
XiTA AV – множество базовых алгоритмов [10, 13], ii YX , – множества определений и зна-
чений алгоритма i
i
Y
XiA |0
. )}())()(({ 00
,,
,
Tii
VA
TATA CAYAXM
TA
o
i
– неоднородный носитель, )( TC –
множество языковых конструкций, которые удовлетворяют TC ; );""|{(
21,31 l
llA );""|(
,,4 i
iqh
f
fll
A
);"|"|(
,5
j
i
f
f
A );"||"|( ,6
A );":"|( ,7 a
baA )}""|( ,8 c
baA .
Структура TAC включает алгоритмы выполнения операций:
− ji
ji
AA
AA
A
,
0
1 | – композиция алгоритмов, ji AA – последовательное выполнение алгоритма jA после ал-
горитма iA ;
− 1|0
2
A
ZA – условное выполнение: алгоритм iA выполняется, если условие Z истинно;
− l
llA
21 ,3 | –конкатенация, 21,, lll – формы;
Теоретичні та методологічні основи програмування
66
− i
iqh
f
fll
A
,,4 | – подстановка, iqh fll ,, – формы;
− j
i
f
f
A
,5 | ,
,6 |A – частичный и полный вывод, где ji ff , – формы, – аксиома, – множество
сформированных конструкций;
− a
baA ,7 | – присвоение операнду a значение операнда b ;
− c
baA ,8 | – сравнение атрибутов a и b , если ba , то truec , в противном случае falsec .
Конкретизация КПС текста. Выполним конкретизацию структуры
TC :
222 ,, MCC TKKT ,
где 12 , }},,,,,,,{}{;{ 22 iwT nNNTM
i
. Атрибутом нетерминала ( iw ) является тип
конструкции ( iwkind ), для построения которой он используется.
Далее рассмотрим правила для построения к-текста, а также других конструкций, которые могут в него
входить.
Правило 1s позволяет начать выполнение построения текста, определив значение соответствующего ат-
рибута как текст:
1s , ctkindg :1 .
Правило 42 ss позволяют определить составляющие текста – абзацы (одного или много), определив
значение соответствующего атрибута как абзац
2s , pkindg c:2 , 3s , 214 mms ,
где 21,mm – символы возврата каретки и перехода на новую строку.
Правила 42 ss позволяют определить составляющие абзаца – предложение (много или одно), опреде-
лив значение соответствующего атрибута как предложение
5s , 6s , skindg c:6 , endms 7 ,
где SDend Tm – символ признак окончания предложения.
Правила 98 ss позволяют определить составляющие предложения: одно или более слов
8s , wkindg c:8 , 9s .
Правила 1110 ss позволяют определить разделитель между словами
sepms 10 , sepms 11 ,
где SDDWDWDsep TTTTm \, .
Правила 1312 ss позволяют построить слово из одной и более букв:
cms 12 , cms 13 ,
где NLKc TTTm .
Тут под записью типа NLKcc TTTmm , следует понимать множество альтернативных правил,
что можно также записать в виде ...|| вбa .
Операции над атрибутами выполняются после операции частичного вывода.
Реализация КПС текста. Реализация структуры (2) заключается в формировании языковых конструк-
ций из элементов ее носителя путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам
аксиоматики:
Теоретичні та методологічні основи програмування
67
)( TARTA CC ,
где )()( TATA CC .
Рассмотри пример построения конструкции «Колпак под колпаком.». Далее показан вывод текста, состо-
ящего из одного абзаца и одного предложения, заканчивающегося точкой:
'10''13''.''10''13''10''13'
76421
Определим количество слов и структуру предложения:
'10''13'.''''''10''13''.''10''13''.'10''13''.'10''13''.'
10899
.
Далее используя правила 12, 13 получаем фразу «Колпак’32’под’32’колпаком.’13’’10’». Здесь в кавычки
взяты символы пробела и перехода к новому абзацу.
Для обработки конструкций рассмотрим задачи синтеза и анализа графовой модели текста [8].
Синтез графа конструктивно-продукционными структурами
Пусть есть множество языковых конструкций )( TAC , порожденное структурой TAC (2). Задача состо-
ит в определенные структуры gC , порождающей множество конструкций-графов )( gC такое, что существу-
ет биективное отображение )()(: ggTA CСf .
Для решения поставленной задачи определим структуру и специализируем ее соответствующим обра-
зом:
ggggS MCMC ,,,, ,
где gM – расширяемый носитель, включающий множества конструкций-графов, языковых конструкций и их
элементов, g – множество операций и отношений на элементах gM , g – аксиоматика.
Частичная аксиоматика носителя. Носитель включает множества терминальных и нетерминальных
элементов ggg NTM . Терминалами являются языковые конструкции, построенные КПС (2) и их состав-
ляющие ( TT ), а также конструкции графов и их составляющих EVTT Tgg , g – множество
конструкций-графов, V , E – множества вершин и дуг с их атрибутами.
Вершина имеет атрибуты tokenscontentid ,,wv , id – идентификатор, принимает целочисленные зна-
чения, content – часть текстовой конструкции, tokens – список, содержащий признаки начала языковых кон-
струкций. Атрибуты дуги endstart,routes,idw e , , id – идентификатор, принимает целочисленные значе-
ния, routes – множество номеров путей, в которые входит дуга (указывает на порядок обхода графа), start, end
– вершин, которые являются началом и концом дуги.
Нагруженный граф будем обозначать EVG
gw , , }{},{ jwiw eEvV
jevi
– множества вершин и дуг,
нагруженых атрибутами. Каждое множество содержит пустой элемент.
Граф имеет такие атрибуты lamountvcurrentvlastvstartw g _,_,_,_ , где start_v– стартовая вершина
графа, last_v – последняя добавленная вершина, current_v – текущая вершина при формировании графа,
amount_l – количество циклов, в которые входит стартовая вершина.
Частичная аксиоматика операций. Рассмотрим сигнатуру g :
gggg }{,,, ,
где },
~
,:,:,{
g – множество операций преобразования и связывания, }
~
||,|,{ g – множество
операций вывода, },#,:,{ g – множество операций над атрибутами, g – множество правил продукций
вида iii gs ,: , i – номер правила, s – последовательность операций подстановки, g – последователь-
ность операций над атрибутами, « » – отношение подстановки.
Теоретичні та методологічні основи програмування
68
Операция ),,(: 21 Gvve
заключается в определении дуги e , соединяющей вершины 1v и 2v графа G .
Если дуга со значениями соответствующих атрибутов отсутствует, то возвращается пустой элемент множества
дуг графа G , его идентификатор равен нулю.
Операция ),(: Vxv заключается в нахождении вершины v с атрибутом веса, равным x , из множества
вершин V . Если вершина со значениями соответствующих атрибутов отсутствует, то возвращается пустой
элемент множества вершин V , его идентификатор равен нулю.
Операция ),,( Lnc заключается в выполнении n операций из списка L , если truec .
Операция вычисления мощности множества Q# определяет число, равное количеству элементов в Q .
Операция сложения двух чисел ),( ba предполагает нахождение третьего числа, являющегося их
суммой.
Операция объединения графов ),(
~
21 21
GGG wwwg
предполагает формирование нового графа
G
gw , включающего объединенные множества вершин и дуг исходных графов EVG
gw , ,
21 VVV , 21 EEE , 111 ,
1
EVGw , 222 ,
2
EVGw , при этом – традиционная операция объедине-
ния множеств.
Отношение подстановки имеет вид
iii gs , , iii sss ~, , iii ggg ~, ,
где is , is~ – отношение подстановки для распознавания языковой конструкции и построения конструкции графа
соответственно, ig , ig~ – операции над атрибутами языковой конструкции и графа, его вершин и дуг соответ-
ственно. В случае если операции над атрибутами не выполняются, отношение подстановки имеет вид
,s .
Операция полного вывода ),(
~
|| l
lw состоит в:
− определении входной конструкции, набора отношений подстановки и доступных из них;
− выполнении операции частичного вывода, пока языковая конструкция полностью не распо-
знана, то есть для каждого ее элемента i в графе нет соответствующего элемента-вершины или форма графа
содержит нетерминалы.
Результатом операции вывода является конструкция-граф.
Конкретизация КПС графа. Выполним конкретизацию структуры gC :
333 ,, MCC gKKg ,
где g3 , , { 33 gMM ,TTc },{g N , },,{ *** GGGTg , EVG , , }{vV , E ,
*** ,GVG , },{ *
2
*
1
* vvV , }{ *
1
* eE , ****** ,GVG , },{ **
2
**
1
** vvV , }}{ **
1
** eE .
Для распознавания языковых конструкций определим такие правила:
,
11 cs d ):,1,( 11 truedEOFccodeg , cs d
22 , ):,1,( 22 truedEOFccodeg ,
где с – символ текста, кроме EOF – признак конца текста в его электронном представлении.
Следующие правила описывают добавление первой вершины в пустой граф:
,
~
σs~1 G ctcpcscwtokensc,v:contentVvidg ,,,:,#:~
1 ,
0:_, GlamountvG:last_vv,G:current_vv,G:start_v .
Правило 2
~s позволяет добавить к графу новую вершину и дугу, связывающую новую вершину с теку-
щей в графе
,),(
~
,),(
~~
:~ **
2 *
1
GGGGGGs
d
),,_(:),,(:~
112 GvGvcurrenteVcvg
,
Теоретичні та методологічні основи програмування
69
,:,14,0&0( *
111 truedeidvid ,_:*
1 Gvcurrentidvid ,_:*
1 Gvcurrentcontentvcontent
,1#:*
2 Vvid ,:,:,1#:,: *
2
*
1
*
1
*
1
*
1
*
2 veendvestartEeidcvcontent },_{:*
1 Glamounteroutes
),:,&_( *
2 cwvtokensTxxGvcurrentcontent WD
):,&_( *
2 csvtokensTxxGvcurrentcontent SD ,
.):_,:_),:,'10'_( 22
*
2 vGvcurrentvGvlastcpvtokensGvcurrentcontent
Правило 3
~s позволяет добавить к графу новую дугу, связывающую текущую вершину со стартовой.
GGGGGs
d
),(
~
,),(
~~ ****
3 *
2
, ),,,_(:),,(:~
1113 GvGvcurrenteVcvg
:,_:,:,14,0&_( **
1
**
1
*
211 vcontentGvcurretidvidtruedeidGvstartv
,_:,_: **
2 GvstartidvidGvcurretcontent :,1#:,: **
1
**
1
**
2 estartEeidcvcontent
,1_:_},_{:,:,: **
1
**
2
**
1
**
1 GlamountGlamountGlamounteroutesveendv
)),,_(:,1,&_( **
2 cwGvstarttokensvtokensTxxGvcurrentcontent WD
)),,_(:,1,&_( **
2 csGvstarttokensvtokensTxxGvcurrentcontent SD
)__)),,_(:,1,'10'_( **
2 GvstartGvcurrentcpGvstarttokensvtokensGvcurrentcontent .
Правило 4
~s позволяет изменить нагрузку имеющейся дуги:
,~
*
3
4 GGs
d
),,_(:,),(:~
1114 GvGvcurrenteGVcvg
, ,:,3,0&0( *
311 truedeidvid
,1,&_(},_{:,5,_( 111 WDTxxGvcurrentcontentGlamounterouteseroutesvGvstart
)),,(:,1,&_()),,(: 1111 csvtokensvtokensTxxGvcurrentcontentcwvtokensvtokens SD
,6,_(),:)),,(:,1,'10'_( 111 vGvstartvvcurrentcpvtokensvtokensGvcurrentcontent
)),,(:,1,&_(},_{: 1111 cwvtokensvtokensTxxGvcurrentcontentGlamounterouteseroutes WD
,'10'_()),,(
~
:,1,&_( 11 GvcurrentcontentcsvtokensvtokensTxxGvcurrentcontent SD
.))1_:_,_:)),,(: 11 GlamountGlamountGvstartvcurrentcpvtokensvtokens
Следующее правило позволяют завершить процесс построения конструкции-графа:
~~
5s .
Интерпретация КПС графа. Интерпретируем графовую структуру:
4
,,,,,,, , gggAgAIAAAAGAg MCCVMCC ,
где 34 , }|{ 0 i
i
Y
XiA AV – множество базовых алгоритмов [10, 13], ii YX , – множества определений та зна-
чений алгоритма i
i
Y
XiA |0
. )}()())()(({ 00
glii
VA
AA CCAYAXM
A
o
i
– неоднородный носитель,
Теоретичні та методологічні основи програмування
70
)(),( gl CC – множество языковых и графовых конструкций, которые удовлетворяют lC и gC соответствен-
но; );"
~
||"{( 64 A );":"( 9
A );":"( 10 A );""( 11 A );"#"( 12A )""( 13 A , )"
~
"( 14 A , )}""( 15 A .
Структура gGA C, включает алгоритмы, реализующие такие операции:
− 0
1A , 0
2A , 8753 , AAAA – аналогичны алгоритмам структуры AC ;
−
g
A ,6 | – полный вывод, где – аксиома, – множество сформированных конструкций;
− e
GvvA ,,9 21
| – определение дуги e , соединяющей две заданные вершины 21 ,vv в графе G ;
− v
VxA ,10 | – нахождение вершины v с заданным значением атрибута веса x в множестве вершин V ;
− L
LncA ,,11 | – выполнение n операций из списка L , если truec , L – список из n операций;
− x
QA |12 –вычисление мощности x множества Q ;
− c
baA ,13 | – сложения двух чисел ba, , c – результат;
− G
GGA
21,14 | – объединение графов 21,GG в G ;
− Q
QQ
A
21,15 | – объединение множеств 21,QQ в Q .
Реализация КПС графа. Реализация структуры gAC заключается в формировании графовых конструк-
ций, которые имеют однозначное соответствие конструкциям )( TAC путем выполнения алгоритмов, связан-
ных с операциями сигнатуры, по правилам аксиоматики:
)( gARgA CC ,
где )()( gAgA CC .
Сжатие графа
Данная графовая модель может быть использована для сравнения текстов, поиска подстроки в строке.
Для ускорения процесса сравнения можно применить сжатия графа. Для этого рассмотрим такую структуру:
CCCCS MCMC ,,,, ,
где gCC EVM { , }},{},}
~
||,|,{},:,{{ iiCCCC gs .
Частичная аксиоматика операций.
Отношение подстановки и операции подстановки, частичного и полного вывода, конкатенации, присваи-
вания аналогичны одноименным операциям КПС графа.
Интерпретация КПС сжатия графа. Алгоритмы операций, использованы в рассматриваемой структу-
ре, аналогичны алгоритмам одноимённых операций структуры для построения графа.
Конкретизация КПС сжатия графа. Выполним конкретизацию структуры для сжатия графа:
CKCKCKCKKC MCC ,, ,
где }{, CKCKCCK NNMM .
Рассмотрим правила, позволяющие сжать граф.
Gs 1 , GGs d2 ,
),,(:,:,4,(),,,(:),,,(: 212121 jiikjji vcontentvcontentvcontenttruederouteseroutesGvveGvvegg
):),,(: 1 kjii veendvtokensvtokensvtokens , 3s .
Теоретичні та методологічні основи програмування
71
Реализация КПС сжатия графа. Реализация интерпретируемой структуры CAC заключается в форми-
ровании графовых конструкций, которые имеют однозначное соответствие конструкциям )( TAC и )( gAC
путем выполнения алгоритмов, связанных с операциями сигнатуры, по правилам аксиоматики:
)( CARCA CC ,
где )()( CACA 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.
Теоретичні та методологічні основи програмування
72
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
mailto:shinkarenko_vi@ua.fm
|