Зображення обкладинки

Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS

Предложена реализация логического вывода по прикладной базе знаний на основании Rete и Treat алгоритмов сопоставления с образцом для определения оптимального из них по ресурсоемкости и быстродействию. Приведено описание реализации Treat алгоритма для программной оболочки CLIPS, позволяющее сохранить...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Электронное моделирование
Дата:2015
Автор: Мажара, О.А.
Формат: Стаття
Мова:Російська
Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
Теми:
Информационные технологии
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/101165
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS / О.А. Мажара // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 61-75. — Бібліогр.: 13 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859793624034705408
author Мажара, О.А.
author_facet Мажара, О.А.
citation_txt Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS / О.А. Мажара // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 61-75. — Бібліогр.: 13 назв. — рос.
collection DSpace DC
container_title Электронное моделирование
description Предложена реализация логического вывода по прикладной базе знаний на основании Rete и Treat алгоритмов сопоставления с образцом для определения оптимального из них по ресурсоемкости и быстродействию. Приведено описание реализации Treat алгоритма для программной оболочки CLIPS, позволяющее сохранить существующие структуры данных и методы оптимизации логического вывода вследствие хеширования, представления сети предкомпиляции и реорганизации базы знаний. Предложенный подход позволяет в дальнейшем расширить программную среду CLIPS дополнительными инкрементными алгоритмами сопоставления. Запропоновано реалізацію логічного виведення за прикладною базою знань на основі Rete і Treat алгоритмів співставлення зі зразком для визначення оптимального з них за ресурсоємністю та швидкодією. Надано опис реалізації Treat алгоритму для програмної оболонки CLIPS, який дозволяє зберегти існуючі структури даних та методи оптимізації логічного виведення внаслідок хешування, представлення мережі прекомпіляції та реорганізації бази знань. Запропонований підхід дозволяє надалі розширити програмне середовище CLIPS додатковими інкрементними алгоритмами співставлення. Implementation of the logical inference by the applied knowledge base based on Rete and Treat match algorithms for choosing optimal one in terms of resources usage and performance has been proposed. Treat algorithm implementation, which allows saving current approaches for data representation and optimizations by hashing, precompile network representation and knowledge base representation, was formalized for CLIPS. The proposed approach allows further extension of the CLIPS programming environment by additional incremental match algorithms.
first_indexed 2025-12-02T12:48:53Z
format Article
fulltext ÓÄÊ 004.825 Î.À. Ìàæàðà, àñïèðàíò Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò» (Óêðàèíà, 03056 Êèåâ, ïð. Ïîáåäû, 37, òåë. (096) 6315931, e-mail: olyamazhara@gmail.com) Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ñ îáðàçöîì â ïðîãðàììíîé îáîëî÷êå CLIPS Ïðåäëîæåíà ðåàëèçàöèÿ ëîãè÷åñêîãî âûâîäà ïî ïðèêëàäíîé áàçå çíàíèé íà îñíîâàíèè Rete è Treat àëãîðèòìîâ ñîïîñòàâëåíèÿ ñ îáðàçöîì äëÿ îïðåäåëåíèÿ îïòèìàëüíîãî èç íèõ ïî ðåñóðñîåìêîñòè è áûñòðîäåéñòâèþ. Ïðèâåäåíî îïèñàíèå ðåàëèçàöèè Treat àëãîðèòìà äëÿ ïðîãðàììíîé îáîëî÷êè CLIPS, ïîçâîëÿþùåå ñîõðàíèòü ñóùåñòâóþùèå ñòðóêòóðû äàííûõ è ìåòîäû îïòèìèçàöèè ëîãè÷åñêîãî âûâîäà âñëåäñòâèå õåøèðî- âàíèÿ, ïðåäñòàâëåíèÿ ñåòè ïðåäêîìïèëÿöèè è ðåîðãàíèçàöèè áàçû çíàíèé. Ïðåäëî- æåííûé ïîäõîä ïîçâîëÿåò â äàëüíåéøåì ðàñøèðèòü ïðîãðàììíóþ ñðåäó CLIPS äîïîë- íèòåëüíûìè èíêðåìåíòíûìè àëãîðèòìàìè ñîïîñòàâëåíèÿ. Çàïðîïîíîâàíî ðåàë³çàö³þ ëîã³÷íîãî âèâåäåííÿ çà ïðèêëàäíîþ áàçîþ çíàíü íà îñíîâ³ Rete ³ Treat àëãîðèòì³â ñï³âñòàâëåííÿ ç³ çðàçêîì äëÿ âèçíà÷åííÿ îïòèìàëüíîãî ç íèõ çà ðåñóðñîºìí³ñòþ òà øâèäêî䳺þ. Íàäàíî îïèñ ðåàë³çàö³¿ Treat àëãîðèòìó äëÿ ïðîãðàìíî¿ îáîëîíêè CLIPS, ÿêèé äîçâîëÿº çáåðåãòè ³ñíóþ÷³ ñòðóêòóðè äàíèõ òà ìåòîäè îïòèì³çàö³¿ ëîã³÷íîãî âèâåäåííÿ âíàñë³äîê õåøóâàííÿ, ïðåäñòàâëåííÿ ìåðåæ³ ïðåêîìï³ëÿö³¿ òà ðåîð- ãàí³çàö³¿ áàçè çíàíü. Çàïðîïîíîâàíèé ï³äõ³ä äîçâîëÿº íàäàë³ ðîçøèðèòè ïðîãðàìíå ñåðå- äîâèùå CLIPS äîäàòêîâèìè ³íêðåìåíòíèìè àëãîðèòìàìè ñï³âñòàâëåííÿ. Ê ë þ ÷ å â û å ñ ë î â à: ñîïîñòàâëåíèå ñ îáðàçöîì, Rete àëãîðèòì, Treat àëãîðèòì, ïðîäóêöèîííàÿ ñèñòåìà, ëîãè÷åñêèé âûâîä, CLIPS. Ïðîäóêöèîííûå ñèñòåìû øèðîêî ïðèìåíÿþòñÿ ïðè ðåøåíèè çàäà÷ èñ- êóññòâåííîãî èíòåëëåêòà, ÷òî îáóñëîâèëî ðàçâèòèå ñïåöèàëèçèðîâàííûõ ïðîãðàììíûõ ñðåäñòâ èõ ðàçðàáîòêè — îáîëî÷åê. Íàçíà÷åíèåì òàêèõ ïðîãðàììíûõ ñðåäñòâ ÿâëÿåòñÿ ïðåäîñòàâëåíèå ðàçðàáîò÷èêó âñòðîåííûõ ìåõàíèçìîâ ëîãè÷åñêîãî âûâîäà. Ñ îäíîé ñòîðîíû, ýòî óïðîùàåò ïðîöåññ ðàçðàáîòêè è ïîçâîëÿåò áûñòðî è ýôôåêòèâíî ñîçäàâàòü ïðèêëàäíûå ïðî- äóêöèîííûå ñèñòåìû, ñ äðóãîé — îáóñëîâëèâàåò çàâèñèìîñòü ýôôåêòèâ- íîñòè ðàáîòû ïðèêëàäíîé ñèñòåìû îò ìåõàíèçìîâ ñðåäû åå ðàçðàáîòêè. ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 61 � Î.À. Ìàæàðà, 2015 ������� ���� � �� ������� Íà ýôôåêòèâíîñòü ïðîäóêöèîííûõ ñèñòåì îòíîñèòåëüíî çàòðàò ðå- ñóðñîâ ïàìÿòè è âðåìåíè íàèáîëüøåå âëèÿíèå îêàçûâàåò ìåõàíèçì ñî- ïîñòàâëåíèÿ ñ îáðàçöîì. Ñóùåñòâóåò ïðÿìàÿ çàâèñèìîñòü ìåæäó ôîðìà- òîì ïðåäñòàâëåíèÿ ïðàâèë (ïðîäóêöèé) â áàçå çíàíèé è áûñòðîäåéñòâèåì ñèñòåìû. Îäíàêî â ñîâðåìåííûõ ñðåäàõ ðàçðàáîòêè ïðîäóêöèîííûõ ñèñ- òåì ðåàëèçóåòñÿ òîëüêî îäèí ìåõàíèçì ñîïîñòàâëåíèÿ ñ îáðàçöîì. Íàèáî- ëåå àïðîáèðîâàííûìè ðåàëèçàöèÿìè ýòîãî ìåõàíèçìà ÿâëÿþòñÿ Rete è Treat àëãîðèòìû [1, 2] è èõ ìîäèôèêàöèè. Ðåçóëüòàòû èññëåäîâàíèé ñâè- äåëüñòâóþò î òîì, ÷òî ýôôåêòèâíîñòü èõ èñïîëüçîâàíèÿ çàâèñèò îò îñî- áåííîñòåé áàçû çíàíèé, à ýòî äåëàåò íåâîçìîæíûì âûáîð îïòèìàëüíîãî àëãîðèòìà çàðàíåå. Ïîýòîìó çàäà÷à ñîçäàíèÿ ïðîãðàììíîé ñðåäû äëÿ ðàç- ðàáîòêè ïðîäóêöèîííûõ ñèñòåì, â êîòîðîé íà îñíîâå òåêóùåé áàçû çíàíèé ìîæíî ýêñïåðèìåíòàëüíî îïðåäåëèòü ðåñóðñîåìêîñòü ëîãè÷åñêîãî âûâî- äà, ÿâëÿåòñÿ àêòóàëüíîé è èìååò ïðàêòè÷åñêîå çíà÷åíèå. Àíàëèç ëèòåðàòóðíûõ äàííûõ è ïîñòàíîâêà ïðîáëåìû. Ïîäàâ- ëÿþùåå áîëüøèíñòâî ñîâðåìåííûõ ïðèêëàäíûõ ïðîäóêöèîííûõ ñèñòåì ñîçäàåòñÿ ñ ïîìîùüþ ñïåöèàëèçèðîâàííûõ îáîëî÷åê [3]. Íàèáîëåå èçâåñò- íûìè êîììåð÷åñêèìè îáîëî÷êàìè ïðîäóêöèîííûõ ñèñòåì ÿâëÿþòñÿ Jess, Exsys Corvid, G2. Èç ñâîáîäíî ðàñïðîñòðàíÿåìûõ îáîëî÷åê ïðîäóêöèîí- íûõ ñèñòåì íàèáîëåå èçâåñòíû CLIPS, Drools, Soar. Áûëà èññëåäîâàíà îáîëî÷êà CLIPS, òàê êàê â íàñòîÿùåå âðåìÿ îíà ÿâ- ëÿåòñÿ îäíèì èç ñàìûõ ðàñïðîñòðàíåííûõ ïðîãðàììíûõ ñðåäñòâ äëÿ ðàç- ðàáîòêè ïðèêëàäíûõ ïðîäóêöèîííûõ ñèñòåì, ïðîâåäåíèÿ íàó÷íûõ èññëå- äîâàíèé è îáó÷åíèÿ ñòóäåíòîâ ñïåöèàëüíîñòåé, ñâÿçàííûõ ñ èñêóññòâåííûì èíòåëëåêòîì [4]. Îñíîâíûå ïðåèìóùåñòâà, îáóñëîâèâøèå âûáîð CLIPS, ýòî ðàñïðîñòðàíåíèå ïî ñâîáîäíîé ëèöåíçèè ñ îòêðûòûì èñõîäíûì êî- äîì, êîòîðûé ìîæåò áûòü ìîäèôèöèðîâàí è èñïîëüçîâàí áåç îãðàíè÷åíèé, à òàêæå ïîëíàÿ ñîïðîâîäèòåëüíàÿ äîêóìåíòàöèÿ è âîçìîæíîñòü ñîòðóäíè- ÷åñòâà ñ ðàçðàáîò÷èêàìè ñèñòåìû. Êîíöåïòóàëüíûìè ïðåèìóùåñòâàìè ÿâëÿåòñÿ ïîääåðæêà íåñêîëüêèõ ïàðàäèãì ïðîãðàììèðîâàíèÿ, êðîññïëàò- ôîðìåííîñòü, âîçìîæíîñòü èíòåãðàöèè ñ äðóãèìè ÿçûêàìè ïðîãðàììèðî- âàíèÿ. Ðàçðàáîò÷èêè ïðåäñòàâèëè ñïåöèàëèçèðîâàííûå âåðñèè ñðåäû äëÿ ðàáîòû â òàêèõ îïåðàöèîííûõ ñèñòåìàõ êàê Android è iOS, ÷òî ïîçâîëÿåò ñîçäàâàòü ýêñïåðòíûå ñèñòåìû äëÿ ïîðòàòèâíûõ óñòðîéñòâ. Êðîìå òîãî, CLIPS àïðîáèðîâàí âî ìíîãèõ ïðèêëàäíûõ ïðîäóêöèîííûõ ñèñòåìàõ. Ïîñ- ëåäíÿÿ âåðñèÿ CLIPS 6.3 ïðåäñòàâëåíà â ìàðòå 2015 ãîäà [5].  ñðåäå CLIPS ðåàëèçîâàíà îïòèìèçèðîâàííàÿ âåðñèÿ Rete àëãîðèòìà ñîïîñòàâëåíèÿ ñ îáðàçöîì [1]. Ñóùåñòâóåò ðÿä ïîäõîäîâ ê åãî ðåàëèçàöèè, êîòîðûå îïðåäåëÿþòñÿ ñïîñîáàìè ïðåäñòàâëåíèÿ Alpha è Beta ïàìÿòè â ñåòè ñîïîñòàâëåíèÿ [6]. Òåêóùàÿ âåðñèÿ CLIPS 6.3 èìååò ðÿä óñîâåðøåíñò- Î.À. Ìàæàðà 62 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 âîâàíèé ïî ñðàâíåíèþ ñ ïðåäûäóùåé. Îñíîâíûå èçìåíåíèÿ êàñàþòñÿ ïîäõîäîâ ê óâåëè÷åíèþ áûñòðîäåéñòâèÿ ïîñðåäñòâîì îïòèìèçàöèè àëãî- ðèòìà ñîïîñòàâëåíèÿ [7]. Óñîâåðøåíñòâîâàíèå Rete àëãîðèòìà îñóùåñòâëÿëîñü â ñîîòâåòñòâèè ñî ñïåöèôè÷åñêèìè òðåáîâàíèÿìè çàäà÷è ëîãè÷åñêîãî âûâîäà [8—10]. Íàèáîëåå ðàñïðîñòðàíåííîé ìîäèôèêàöèåé óíèâåðñàëüíîãî Rete àëãî- ðèòìà ÿâëÿåòñÿ Treat àëãîðèòì, êîòîðûé ìîæåò áûòü èñïîëüçîâàí äëÿ îáùåãî ñëó÷àÿ ïðèêëàäíîé çàäà÷è [2]. Åãî èñïîëüçóþò â îòäåëüíûõ âåð- ñèÿõ èçâåñòíûõ îáîëî÷åê ïðîäóêöèîííûõ ñèñòåì, òàêèõ êàê Soar è OPS.  ðàáîòå [11] ïðèâåäåíû ñõåìû ñîïîñòàâëåíèÿ ñ îáðàçöîì ïî Rete è Treat àëãîðèòìàì. Îäíàêî ïîêà íå óñòàíîâëåíû ôîðìàëüíûå êðèòåðèè, ïîçâîëÿþùèå âûáðàòü îïòèìàëüíîå îòíîñèòåëüíî âû÷èñëèòåëüíûõ ðåñóð- ñîâ ïðåäñòàâëåíèå ïðîäóêöèè â áàçå çíàíèé (ÁÇ) íà ýòàïå ïðîåêòèðîâàíèÿ ïðîäóêöèîííîé ñèñòåìû. Ïîýòîìó íåîáõîäèìî ñîçäàòü ñðåäó ðàçðàáîòêè äëÿ ðåàëèçàöèè äâóõ ïîäõîäîâ ê ñîïîñòàâëåíèþ ñ îáðàçöîì ñ öåëüþ ýêñ- ïåðèìåíòàëüíîãî âûáîðà îïòèìàëüíîãî àëãîðèòìà â çàâèñèìîñòè îò òåêó- ùåé ÁÇ. Ïðåäëàãàåòñÿ ñîçäàòü òàêóþ ñðåäó íà áàçå îáîëî÷êè CLIPS ñî âñòðîåííûì àëãîðèòìîì Rete è ðåàëèçàöèåé Treat àëãîðèòìà. Äëÿ äîñòèæåíèÿ óêàçàííîé öåëè ïîñòàâëåíû ñëåäóþùèå çàäà÷è: 1. Îïðåäåëèòü ïðîãðàììíûå ìîäóëè CLIPS, îáåñïå÷èâàþùèå ïðåä- êîìïèëÿöèþ Rete-ñåòè. 2. Îïðåäåëèòü ìîäóëè CLIPS, îáåñïå÷èâàþùèå ñîïîñòàâëåíèå ñ îá- ðàçöîì â ðåæèìå ëîãè÷åñêîãî âûâîäà. 3. Ðàçðàáîòàòü ïîäõîä ê ðåàëèçàöèè Treat àëãîðèòìà ñ ñîõðàíåíèåì ñóùåñòâóþùåé ñòðóêòóðû ïðåäñòàâëåíèÿ äàííûõ è îïòèìèçàöèè ñîïîñ- òàâëåíèÿ ñ îáðàçöîì. Èíêðåìåíòíîå ñîïîñòàâëåíèÿ ñ îáðàçöîì ñ èñïîëüçîâàíèåì Rete àëãîðèòìà èëè åãî ìîäèôèêàöèé ÿâëÿåòñÿ íàèáîëåå ðàñïðîñòðàíåííûì â ïðèêëàäíûõ ïðîèçâîäèòåëüíûõ ñèñòåìàõ. Èíêðåìåíòíûé ïîäõîä ïðåäóñ- ìàòðèâàåò ñîõðàíåíèå ñîñòîÿíèÿ çàäà÷è â ïðîöåññå ëîãè÷åñêîãî âûâîäà. Îí îñíîâàí íà òîì, ÷òî â ïðèêëàäíûõ çàäà÷àõ íà êàæäîì øàãå âûâîäà èçìåíåíèÿ ðàáî÷åé ïàìÿòè âëèÿþò ëèøü íà ñðàâíèòåëüíî íåáîëüøîå êî- ëè÷åñòâî ïðîäóêöèé. Ñîïîñòàâëåíèå îñóùåñòâëÿåòñÿ íå ïî óñëîâíîé ÷àñòè ïðàâèëà, à ïî çàðàíåå ñîçäàííîé íà ýòàïå ïðåäêîìïèëÿöèè ñåòè àíàëèçà àíòåöåäåíòîâ ïðîäóêöèé. Òàêèì îáðàçîì, ñîïîñòàâëåíèå ïðîèñõîäèò â äâóõ ðåæèìàõ: íà ýòàïå ïðåäêîìïèëÿöèè áàçû çíàíèé ïðîäóêöèé ôîðìè- ðóåòñÿ Rete-ñåòü ïîòîêà äàííûõ; íà ýòàïå ëîãè÷åñêîãî âûâîäà ïðîâîäèòñÿ íåïîñðåäñòâåííî ñîïîñòàâëåíèå ïî ñåòè. Rete-ñåòü ñîñòîèò èç äâóõ ÷àñòåé, �- è �-ñåòåé, êîòîðûå ñîîòâåòñòâóþò ýòàïàì ñîïîñòàâëåíèÿ. Ñîãëàñîâàíèÿ â ðàìêàõ îäíîãî øàáëîíà ïðîäóêöèè Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 63 ïðîèñõîäÿò â óçëàõ �-ñåòè è íàçûâàþòñÿ âíóòðåííèìè òåñòàìè. Âíóòðåí- íèå òåñòû ïðåäóñìàòðèâàþò ïðîâåðêó òèïîâ, êîíñòàíòíûõ çíà÷åíèé, ñî- ãëàñîâàíèÿ ïåðåìåííûõ, âñòðå÷àþùèõñÿ â óñëîâíîé ÷àñòè ïðàâèëà òîëüêî îäèí ðàç. Íà ýòàïå âûïîëíåíèÿ â óçëàõ �-ñåòè õðàíÿòñÿ ñâåäåíèÿ î ôàêòàõ, êîòîðûå ïðèâåëè ê èõ àêòèâàöèè, ò.å. �-ïàìÿòü.  óçëàõ �-ñåòè ïðîèñõîäèò ñîãëàñîâàíèå øàáëîíîâ â ðàìêàõ îòäåëü- íîé ïðîäóêöèè — âíåøíèå òåñòû.  Rete-ñåòè �-óçëû èìåþò äâà âõîäà: ëåâûé è ïðàâûé. Ëåâûé âõîä âñåãäà ïîëó÷àåò èíôîðìàöèþ î ñîãëàñîâàíèè îò ðîäèòåëüñêîãî �-óçëà, ïðàâûé — îò ðîäèòåëüñêîãî �-óçëà ïî ðåçóëüòà- òàì ïðåäâàðèòåëüíûõ ñîãëàñîâàíèé.  êàæäîì �-óçëå ñîäåðæèòñÿ èíôîð- ìàöèÿ î ôàêòàõ, êîòîðûå ïðèâåëè ê âûïîëíåíèþ âíåøíèõ òåñòîâ è åãî àêòèâàöèè. Ëèñòîâûå (òåðìèíàëüíûå) óçëû ñåòè ïîòîêà äàííûõ îòðàæàþò àêòèâàöèþ ïðîäóêöèè è ñîäåðæàò èíôîðìàöèþ î ôàêòàõ ðàáî÷åé ïàìÿòè, êîòîðûå ñ íåé ñîãëàñóþòñÿ. Òàêèì îáðàçîì, òåðìèíàëüíûå óçëû ñåòè ñîõðà- íÿþò òåêóùèé êîíôëèêòíûé íàáîð èç àêòèâèðîâàííûõ ïðîäóêöèé.  ñëó÷àå äîáàâëåíèÿ ôàêòà ê ðàáî÷åé ïàìÿòè èíôîðìàöèÿ îá èçìå- íåíèÿõ ïîñòóïàåò ê âåðøèíå ñåòè ñîïîñòàâëåíèÿ. Äàëåå ïðîèñõîäèò ðàñ- ïðîñòðàíåíèå èçìåíåíèé ïî ñåòè ïîñðåäñòâîì âûïîëíåíèÿ òåñòîâ â óçëàõ è èõ àêòèâàöèè. Ïðîäóêöèÿ àêòèâèðóåòñÿ, êîãäà ýòè èçìåíåíèÿ äîñòèãàþò ëèñòîâîãî óçëà.  êëàññè÷åñêîé âåðñèè Rete óäàëåíèå ôàêòîâ ïðåäóñ- ìàòðèâàåò òå æå äåéñòâèÿ, ÷òî è äîáàâëåíèå. Ôàêò ïîñòóïàåò â ñåòü ñ îò- ìåòêîé îá óäàëåíèè è ïðèâîäèò ê äåàêòèâàöèè ñîîòâåòñòâóþùèõ âåðøèí. Òàêîé ïîäõîä ê óäàëåíèþ íàçûâàþò ñèììåòðè÷íûì [12]. Äëÿ îáðàáîòêè íåãàòèâíûõ óñëîâíûõ ýëåìåíòîâ â ñåòè äîáàâëÿþò ñïåöèàëèçèðîâàííûå �-óçëû, ñîäåðæàùèå ñ÷åò÷èê ôàêòîâ, êîòîðûå ñîãëàñóþòñÿ ñ îòðèöàòåëü- íûì óñëîâíûì ýëåìåíòîì è ïðåïÿòñòâóþò àêòèâàöèè. Ðåàëèçàöèÿ ñîïîñòàâëåíèÿ ñ îáðàçöîì â îáîëî÷êå CLIPS.  òåêó- ùåé âåðñèè CLIPS èñïîëüçóåòñÿ ðåàëèçàöèÿ ñîïîñòàâëåíèÿ ñ îáðàçöîì ñ õåøèðîâàíèåì �- è �-ïàìÿòè â ñåòè ïîòîêà äàííûõ ïðè àñèììåòðè÷íîì óäàëåíèè. Ñîïîñòàâëåíèå ñ îáðàçöîì ñâÿçàíî ñ ôóíêöèîíèðîâàíèåì ñèñòåìû â äâóõ ðåæèìàõ ðàáîòû: ïðåäêîìïèëÿöèè è ëîãè÷åñêîãî âûâîäà. Àðõèòåêòóðà ñèñòåìû îòðàæàåò îáà ýòàïà ñîïîñòàâëåíèÿ: ïîñòðîåíèå ñåòè ïîòîêà äàííûõ è ïðîâåðêó èçìåíåíèÿ ôàêòîâ ðàáî÷åé ïàìÿòè. Ñèíòàêñè÷åñêèé è ñåìàíòè÷åñêèé àíàëèç ïðîäóêöèé ïðîèñõîäèò íà ýòàïå çàãðóçêè ïðàâèë â ñèñòåìó. Åãî öåëüþ ÿâëÿåòñÿ ôîðìèðîâàíèå ñåòè Rete àëãîðèòìà. Äîáàâëåíèå ïðîäóêöèé âî âðåìÿ ëîãè÷åñêîãî âûâîäà â ïðèêëàäíîé çàäà÷å â CLIPS íå ïðåäóñìîòðåíî. Ñîïîñòàâëåíèå ñ îáðàçöîì ÿâëÿåòñÿ îäíèì èç áàçîâûõ ìåõàíèçìîâ ëîãè÷åñêîãî âûâîäà, ïîýòîìó åãî ðåàëèçàöèÿ îòðàæàåòñÿ â íåñêîëüêèõ ìîäóëÿõ CLIPS.  äàííîì ñëó÷àå öåëü ñîñòîÿëà â ðåàëèçàöèè Treat àëãî- Î.À. Ìàæàðà 64 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 ðèòìà ñ ñîõðàíåíèåì ïðåäëîæåííîãî äëÿ Rete ôîðìàòà ïðåäñòàâëåíèÿ äàííûõ. Äëÿ åå äîñòèæåíèÿ â ïåðâóþ î÷åðåäü áûëè îïðåäåëåíû ðàçëè÷èÿ ìåæäó êëàññè÷åñêîé âåðñèåé Rete àëãîðèòìà (Forgy), ðåàëèçîâàííîé â ñðåäå CLIPS (Riley), è Treat (Miranker) àëãîðèòìîì. Ðåçóëüòàòû ñðàâíåíèÿ ïðåäñòàâëåíû â òàáë. 1, èç êîòîðîé âèäíî, ÷òî â ïîñëåäíåé âåðñèè ñðåäû CLIPS ðåàëèçîâàí ñïîñîá óäàëåíèÿ ôàêòîâ, ïðåäëîæåííûé äëÿ Treat àëãîðèòìà. Äëÿ ðåàëèçàöèè Treat àëãîðèòìà íà îñíîâå ñóùåñòâóþùåãî ôóíêöèîíàëà ïðîâåäåí àíàëèç òåêóùåé âíóòðåííåé àðõèòåêòóðû CLIPS è îñîáåííîñòåé ïðåäñòàâëåíèÿ äàííûõ. Ôðàãìåíòû àðõèòåêòóðû CLIPS, íåîáõîäèìûå äëÿ ðåàëèçàöèè Treat àëãîðèòìà, áûëè ðàñïðåäåëåíû ïî êàòåãîðèÿì: íåèçìåíÿåìûå è òðåáóþùèå ìîäèôèêàöèè. Ïðåäêîìïèëÿöèÿ Rete-ñåòè ñîïîñòàâëåíèÿ. Ôîðìèðîâàíèå ñåòè ïî- òîêà äàííûõ â ñðåäå CLIPS ïðîèñõîäèò â íåñêîëüêî ýòàïîâ. Íà ïåðâîì ýòàïå îñóùåñòâëÿåòñÿ îáðàáîòêà ÁÇ ñ öåëüþ ïðåîáðàçîâàíèÿ â ôîðìàò, ïðèãîäíûé äëÿ òîïîëîãèè Rete-ñåòè. Çàòåì ïðîâîäèòñÿ îïòèìèçàöèÿ ïðåäñòàâëåíèÿ ïðàâèë äëÿ îáðàáîòêè ñåòè. Ïðîìåæóòî÷íîå ïðåäñòàâëåíèå ÁÇ èñïîëüçóåòñÿ äëÿ îïðåäåëåíèÿ ïîçèöèé ïåðåìåííûõ, íà îñíîâàíèè ÷åãî ïðîèñõîäèò ôîðìèðîâàíèå âûðàæåíèé, êîòîðûå â äàëüíåéøåì èñïîëü- çóþòñÿ äëÿ îöåíêè ñîãëàñîâàíèÿ øàáëîíà è ôàêòà. Ïîñëåäíèì ýòàïîì ÿâëÿåòñÿ èíòåãðàöèÿ ïðàâèëà â ñåòè ñîïîñòàâëåíèÿ è ñâÿçûâàíèÿ. Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 65 Ñïîñîá ðåàëèçàöèè Rete (Forgy) CLIPS Rete (Riley) Treat (Miranker) Êîìïèëÿöèÿ ñåòè ïîòîêà äàííûõ �-ñåòü âíóòðåííèõ òåñ- òîâ �-ñåòü âíóòðåííèõ òåñ- òîâ �-ñåòü âíóòðåííèõ òåñ- òîâ �-ñåòü âíåøíèõ òåñòîâ �-ñåòü âíåøíèõ òåñòîâ Äèíàìè÷åñêàÿ ñåòü ñî- ãëàñîâàíèÿ Ñîõðàíåíèå äàííûõ �-ïàìÿòü ñîãëàñîâàíèÿ ôàêòîâ è �-ïàìÿòü ÷àñ- òè÷íîãî ñîãëàñîâàíèÿ ñ øàáëîíàìè �-ïàìÿòü ñîãëàñîâàíèÿ ôàêòîâ, �-ïàìÿòü ÷àñ- òè÷íîãî ñîãëàñîâàíèÿ ñ øàáëîíàìè, êîíôëèêò- íîå ìíîæåñòâî �-ïàìÿòü ñîãëàñîâàíèÿ ôàêòîâ è êîíôëèêòíîå ìíîæåñòâî Îáðàáîòêà äîáàâëåíèÿ ôàêòîâ Ðàñïðîñòðàíåíèå îò êîð- íåâîãî óçëà â ñòàòè÷åñ- êîé ñåòè ïîòîêà äàííûõ Ðàñïðîñòðàíåíèå îò êîðíåâîãî óçëà â ñòà- òè÷åñêîé ñåòè ïîòîêà äàííûõ Ðàñïðîñòðàíåíèå ïî ñòà- òè÷åñêîé �-ñåòè è ïîñò- ðîåíèå äèíàìè÷åñêîé ñåòè ñîãëàñîâàíèÿ ïåðå- ìåííûõ â ñëó÷àå íåîá- õîäèìîñòè Îáðàáîòêà óäàëåíèÿ ôàêòîâ Ñèììåòðè÷íîå óäàëåíèå Àñèììåòðè÷íîå óäàëå- íèå Àñèììåòðè÷íîå óäàëå- íèå Òàáëèöà 1 Ïî ðåçóëüòàòàì äàííîãî èññëåäîâàíèÿ âûäåëåíû ôðàãìåíòû àðõè- òåêòóðû ñèñòåìû, îòâå÷àþùèå çà ïîñòðîåíèå Rete-ñåòè (ðèñ. 1). Øòðèõî- âûìè ëèíèÿìè íà ðèñ. 1 îáîçíà÷åíû ìîäóëè, íå òðåáóþùèå èçìåíåíèé. Ñòðóêòóðà êàæäîãî ìîäóëÿ ñîäåðæèò íàçâàíèå, ñîîòâåòñòâóþùåå ôóíê- öèîíàëüíîìó íàçíà÷åíèþ, îñíîâíûå äàííûå è ôóíêöèè â òîì âèäå, â êîòîðîì îíè îáúÿâëåíû â ñèñòåìå.  òàáë. 2 ïðèâåäåíî îïèñàíèå ëîãè÷åñêèõ ìîäóëåé è óêàçàíû íåîáõî- äèìûå ìîäèôèêàöèè äëÿ îáåñïå÷åíèÿ Treat-ñåòè ïîòîêà äàííûõ. Ìîäóëè Scanner è Defrule Parser îáåñïå÷èâàþò ñ÷èòûâàíèå ïðîäóêöèé èç âõîäíîãî ïîòîêà äàííûõ è èõ ïðåäñòàâëåíèå âî âíóòðåííåì ôîðìàòå ñèñòåìû. Ìîäóëü Reorder îáåñïå÷èâàåò äîïîëíèòåëüíóþ îïòèìèçàöèþ ïðåä- ñòàâëåíèÿ ïðàâèë â ñèñòåìå. Äîêàçàíî, ÷òî òàêîé ïîäõîä ìîæåò çíà÷è- òåëüíî óñêîðèòü ëîãè÷åñêèé âûâîä â ïðèêëàäíîé çàäà÷å [13]. Äîïîëíè- òåëüíàÿ îïòèìèçàöèÿ ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿ ÁÇ ïðåäïîëàãàåò ðåîðãàíèçàöèþ è ìîäèôèêàöèþ. Ðåîðãàíèçàöèÿ ïðåäñòàâëÿåò ñîáîé óïîðÿäî÷åíèå óñëîâíûõ ýëåìåíòîâ òàêèì îáðàçîì, ÷òî â àíòåöåäåíòàõ îñòàåòñÿ åäèíñòâåííûé óñëîâíûé ýëå- ìåíò «èëè», ðàñïîëîæåííûé â ñàìîì íà÷àëå. Ýòî ïîçâîëÿåò óïðîñòèòü ïîñòðîåíèå ñåòè ñîãëàñîâàíèÿ ôàêòîâ è óìåíüøèòü åå ðàçìåð. Î.À. Ìàæàðà 66 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Scanner (scanner.h) - struct token + (void ,const char , struct token ); GetToken * * * Defrule Parser (rulepsr.h, rulelhs.h, pattern.h) -struct ;patternEntityRecord -struct ,patternEntitiy -struct patternParser, -struct patternData +int ParseDefrule (void , const char ); * * +struct IhsParseNode ParseRuleLHS (void , * * const char , struct token , * * const char , int ); * * Analysis (analysis.h) struct nandFrame theNandFrames) * + (void ,struct IhsParseNode );VariableAnalysis * * +static int (void theEnv, structGetVariables * IhsParseNode thePattern, int patternHeadType, * +void (void , struct IhsParseNode , struct IhsParseNode , struct nandFrame ); + struct expr GetvarReplace(void , struct IhsParseNode , int,struct nandFrame ); FieldConversion * * * * * * * * Generate (generate.h, factgen.h) Reorder (reorder.h) - struct IhsParseNode +struct IhsParseNode (void , struct IhsParseNode , int ); +void (void , struct IhsParseNode ); ReorderPatterns AddInitialPatterns * * * * * +struct joinNode (void ,int.struct IhsParseNode ,int,struct joinNode ,int, int); +void InitializeFactPatterns(void ); * * * * * ConstructJoins Build (rulebld.h, factbld.h) - struct factPatternNode Ðèñ. 1. Ìîäóëè ïîñòðîåíèÿ Rete-ñåòè ïîòîêà äàííûõ Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 67 Ìîäóëü Íàçíà÷åíèå Âõîäíûå äàííûå Âûõîäíûå äàííûå Ïðåäóñìîòðåííûå èçìåíåíèÿ Scanner Ñ÷èòûâàíèå èíôîðìàöèè èç âõîäíîãî ïîòîêà äàííûõ ïî çàäàííîìó ôîðìàòó ÿçû- êà. Ëåêñè÷åñêèé àíàëèç ïðî- äóêöèé. Ôîðìèðîâàíèå ñòðóêòóðû äëÿ ïðåäñòàâëå- íèÿ âõîäíûõ ìàðêåðîâ çà- äàííîãî òèïà Ëåêñåìû èç âõîäíîãî ïî- òîêà äàííûõ Ìàðêåð â âèäå ñòðóêòóðû äàííûõ, ñîäåðæàùåé òèï è çíà÷åíèå ëåêñåìû Áåç èçìåíåíèé Defrule Parser Ñèíòàêñè÷åñêèé àíàëèç ïðîäóêöèé. Ôîðìèðîâàíèå ïðîìåæóòî÷íîãî ôîðìàòà ÁÇ äëÿ îáðàáîòêè Ìàðêåðû ëåê- ñåì Ñïèñîê ïðàâèë ÁÇ â ôîðìàòå âíóòðåí- íåãî ïðåäñòàâëå- íèÿ. Ïðîìåæóòî÷- íîå ïðåäñòàâëåíèå ÁÇ â âèäå ñòðóêòóð äàííûõ Òî æå Reorder Îïòèìèçàöèÿ ïðåäñòàâëå- íèÿ óñëîâíûõ ýëåìåíòîâ äëÿ àíàëèçèðóåìîé ñåòè Ïðîìåæóòî÷- íîå ïðåäñòàâ- ëåíèå ÁÇ â âèäå ñòðóê- òóð äàííûõ Îïòèìèçèðîâàííîå ïðåäñòàâëåíèå ÁÇ â âèäå ñòðóêòóð äàííûõ " " Analy- sis Ñîõðàíåíèå ïîëîæåíèÿ ïå- ðåìåííûõ â àíòåöåäåíòå è ôîðìèðîâàíèÿ âûðàæåíèé, èñïîëüçóåìûõ äëÿ îöåíêè ñîãëàñîâàíèÿ â �-ñåòè. Ñå- ìàíòè÷åñêèé àíàëèç ÁÇ Îïòèìèçè- ðîâàííîå ïðåäñòàâëå- íèå ÁÇ â âèäå ñòðóêòóð äàííûõ Ïðåäñòàâëåíèå ÁÇ ñ èíôîðìàöèåé î òåñòàõ, âûïîëíÿå- ìûõ ñ öåëüþ ñîãëà- ñîâàíèÿ ïåðåìåí- íûõ äëÿ âíåøíèõ èëè âíóòðåííèõ òåñòîâ Ïðåäñòàâëåíèå ñåòè äëÿ äèíà- ìè÷åñêîãî ñîã- ëàñîâàíèÿ ïåðå- ìåííûõ Build Èíòåãðèðóåò ïðàâèëî â Rete-ñåòü Òî æå Ñåòü øàáëîíîâ (�- ñåòü) è ñåòü ñîãëà- ñîâàíèÿ (�-ñåòü) Ïðåäñòàâëåíèÿ �-ñåòè äëÿ õðà- íåíèÿ èíôîðìà- öèè, íåîáõîäè- ìîé ïðè ñîãëà- ñîâàíèè ïåðåìåí- íûõ. Ïðåäñòàâ- ëåíèå äàííûõ äëÿ ôîðìèðîâà- íèÿ äèíàìè÷åñ- êîé ñåòè ñîãëà- ñîâàíèÿ ïåðå- ìåííûõ Gene- rate Ïîñòðîåíèå óçëîâ �-ñåòè äëÿ ïðîâåðêè çàäàííûõ îã- ðàíè÷åíèé íà çíà÷åíèÿ óñ- ëîâíûõ ýëåìåíòîâ ïðàâèëà " " Âûðàæåíèÿ äëÿ ïðî- âåðêè çíà÷åíèé â óçëàõ �- è �-ñåòè Äèíàìè÷åñêîå ôîðìèðîâàíèå âûðàæåíèé äëÿ ïðîâåðêè ñîã- ëàñîâàíèÿ ïå- ðåìåííûõ â ïðå- äåëàõ îäíîãî ïðàâèëà Òàáëèöà 2 Ìîäèôèêàöèÿ îáåñïå÷èâàåò óìåíüøåíèå èçáûòî÷íîñòè â ñèñòåìå ïî- ñðåäñòâîì óäàëåíèÿ ëèøíèõ óñëîâíûõ ýëåìåíòîâ è ëîãè÷åñêèõ ñâÿçîê, íå âëèÿþùèõ íà ðåçóëüòàòû ñîãëàñîâàíèÿ. Ñîçäàííàÿ îáùàÿ ñòðóêòóðà ïðåäñòàâëåíèÿ ïðîäóêöèé ìîæåò áûòü îäèíàêîâî ýôôåêòèâíî èñïîëüçîâàíà äëÿ àëãîðèòìîâ Rete è Treat. Ïîýòî- ìó äëÿ ñîõðàíåíèÿ öåëîñòíîñòè è îäíîòèïíîñòè ñèñòåìû ýòè ìîäóëè îñòàþòñÿ íåèçìåííûìè. Îáðàáîòêà Rete-ñåòè ñîïîñòàâëåíèÿ.  ðåæèìå ëîãè÷åñêîãî âûâîäà ïî ñåòè ñîïîñòàâëåíèÿ èñïîëüçóþòñÿ ðàçëè÷íûå ìîäóëè, ïðåäíàçíà÷åí- íûå äëÿ îáðàáîòêè ïðîöåññà äîáàâëåíèÿ è óäàëåíèÿ ôàêòîâ.  ýòîì ðå- æèìå ñîïîñòàâëåíèå ïðîèñõîäèò â äâà ýòàïà: ñîãëàñîâàíèå ôàêòîâ ñ øàá- ëîíîì è ñâÿçûâàíèå ïåðåìåííûõ. Äëÿ êàæäîãî èç ýòàïîâ ïðåäóñìîòðåíû ðàçëè÷íûå ñòðóêòóðû ïðåäñòàâëåíèÿ äàííûõ, îïðåäåëåííûå ïðè ôîðìè- ðîâàíèè ñåòè Rete. Ìîäóëè, îáåñïå÷èâàþùèå íåïîñðåäñòâåííî ïðîöåññ ñîïîñòàâëåíèÿ, ïðåäñòàâëåíû íà ðèñ. 2. Îñíîâíûì îòëè÷èåì àëãîðèòìà Treat îò Rete ÿâëÿåòñÿ îòñóòñòâèå ñîõðà- íåíèÿ ñîãëàñîâàíèÿ ïåðåìåííûõ, à ñëåäîâàòåëüíî, è �-ñåòè ñîïîñòàâëåíèÿ.  Treat àëãîðèòìå ïðèìåíÿåòñÿ ïîäõîä ê ñîõðàíåíèþ êîíôëèêòíîãî ìíîæåñòâà, ïîçâîëÿþùèé ýôôåêòèâíî îáðàáàòûâàòü ïðîöåññ óäàëåíèÿ ôàêòîâ.  òàáë. 3 ïðèâåäåíû ìîäóëè îáðàáîòêè ñåòè ïîòîêà äàííûõ â ñðåäå CLIPS è îïðå- äåëåíû èçìåíåíèÿ, íåîáõîäèìûå äëÿ ðåàëèçàöèè Treat àëãîðèòìà. Ðåàëèçàöèÿ ñåòè Treat àëãîðèòìà. Íà îñíîâàíèè àáñòðàêòíîãî îïè- ñàíèÿ Treat àëãîðèòìà, ïðåäëîæåííîãî â ðàáîòå [2], ïðåäñòàâèì ñõåìó åãî ðàáîòû (ðèñ. 3). Íà âõîä àëãîðèòìà ïîñòóïàþò èçìåíåíèÿ ðàáî÷åé ïàìÿòè â âèäå ôàêòîâ ñ îòìåòêîé (ìàðêåðîì) äîáàâëåíèÿ èëè óäàëåíèÿ. Äëÿ Î.À. Ìàæàðà 68 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 + struct partialMatch (void ,struct partialMatch ,struct partialMatch ); +void s (void ,struct patternNodeHeader , struct partialMatch , struct alphaMatch ); + void (void , struct joinNode ,int); * MergePartialMatches RemoveAlphaMemoryMatche DestroyBetaMemory * * * * * * * * * Rete Utility (reteutil.h) Match (match.h, factmch.h) - struct patternMatch - struct partialMatch - struct alphaMatch + void (void void , int, int); RemoveActfvation * * Engine (engine.h, agenda.h) - struct activation - struct engineData +void (void ,void ,void );AddActivation * * * + void (void theEnv, struct patternMatch listOfMatchedPatterns) +void (void , struct partialMatch ); NetworkRetract DeletePartialMatches * * * * Retract (retract.h) + void (void ,struct partialMatch , struct joinNode ); + void (void ,struct partialMatch , struct joinNode ,int); + void (void ,struct partialMatch ,struct joinNode ,int); +void (void ,structpartialMatch , struct partialMatch ,struct joinNode ,int); NetworkAssert NetworkAssertLeft NetworkAssertRight PPDrive * * * * * * * * * * * * * Drive (drive.h) Ðèñ. 2. Ìîäóëè ñîïîñòàâëåíèÿ â Rete-ñåòè êàæäîãî óñëîâíîãî ýëåìåíòà ïðàâèëà (condition element (CE)) íà ïóòè ðàñïðîñòðàíåíèÿ èçìåíåíèé ïî ñåòè âûïîëíÿþòñÿ òåñòû â çàâèñèìîñòè îò òèïà óçëà è çíà÷åíèÿ ìàðêåðà.  Treat àëãîðèòìå �-ñåòü ïîòîêà äàííûõ èñïîëüçóåòñÿ òàê æå, êàê â Rete. Äëÿ îáåñïå÷åíèÿ ôóíêöèîíèðîâàíèÿ Treat-ñåòè â êàæäîì óçëå �-ïà- ìÿòè õðàíèòñÿ ñïèñîê ïðîäóêöèé, ñ êîòîðûìè îíà ñîãëàñîâûâàåòñÿ.  ïðåäëîæåííîé â ðàáîòå [2] âåðñèè äëÿ ïàðàëëåëüíûõ âû÷èñëåíèé íå ïðè- ìåíÿåòñÿ îïòèìèçàöèÿ âñëåäñòâèå ñîâìåñòíîãî âëàäåíèÿ íåñêîëüêèìè ïðîäóêöèÿìè âåðøèí ñåòè. Îäíàêî äëÿ ïîñëåäîâàòåëüíîé ðåàëèçàöèè CLIPS ñîõðàíåíèå ïîäõîäà ê ñîâìåñòíîìó âëàäåíèþ âåðøèíàìè â �-ñåòè ïîçâîëÿåò èçáåæàòü èçáûòî÷íûõ çàòðàò ïàìÿòè. Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 69 Ìîäóëü Íàçíà÷åíèå Âõîäíûå äàííûå Âûõîäíûå äàííûå Íåîáõîäèìûå èçìåíåíèÿ Retract Îáðàáîòêà ñåòè ïîòîêà äàííûõ ïîñëå óäàëåíèÿ ôàêòà Ôàêò äëÿ óäàëå- íèÿ è ñïèñîê ñîã- ëàñóåìûõ ñ íèì øàáëîíîâ Ñåòü ñîãëàñîâàíèÿ ïîñëå îáðàáîòêè óäàëåíèÿ ôàêòà Óäàëåíèå îáðàáîòêè �- ñåòè. Îáåñïå÷åíèå óäà- ëåíèÿ ôàêòà ñ èñïîëü- çîâàíèåì ñîõðàíåííî- ãî êîíôëèêòíîãî ìíî- æåñòâà Drive Îáðàáîòêà ñåòè ïîòîêà äàííûõ â ñëó÷àå äîáàâëå- íèÿ ôàêòîâ ê ðà- áî÷åé ïàìÿòè Äîáàâëåííûé ôàêò Ñåòü ñîãëàñîâàíèÿ ñ èçìåíåíèÿìè â ñîîòâåòñòâèè ñ äî- áàâëåííûì ôàêòîì Ñîçäàíèå ôóíêöèîíàëà äèíàìè÷åñêîãî ôîðìè- ðîâàíèÿ è îáðàáîòêè ñåòè ñîãëàñîâàíèÿ. Óäà- ëåíèå îáðàáîòêè �-ñåòè Match Îïðåäåëåíèå îñ- íîâíûõ ñòðóêòóð äàííûõ äëÿ ïðåä- ñòàâëåíèÿ �- è �-ñåòè Óçëû �-ñåòè Çíà÷åíèå �-ïàìÿòè â óçëàõ ñåòè Ìîäèôèêàöèÿ ñòðóê- òóð äàííûõ äëÿ îáåñïå- ÷åíèÿ ñîõðàíåíèÿ êîíô- ëèêòíîãî ìíîæåñòâà è ôîðìèðîâàíèÿ ñåòè ñîãëàñîâàíèÿ â ðåæèìå ëîãè÷åñêîãî âûâîäà Engine Âûïîëíåíèå ïðà- âèëà èç êîíô- ëèêòíîãî ìíî- æåñòâà, èçáðàí- íîãî ïî çàäàí- íîé ñòðàòåãèè ðàç- ðåøåíèÿ êîíô- ëèêòà ñ ñîõðà- íåíèåì öåëîñò- íîñòè ñåòè ïîòî- êà äàííûõ Òåêóùåå êîíô- ëèêòíîå ìíîæåñò- âî ïðîäóêöèé Èçìåíåíèÿ â ðàáî- ÷åé ïàìÿòè â ðå- çóëüòàòå âûïîëíå- íèÿ êîíñåêâåíòà ïðîäóêöèè Ìîäèôèêàöèÿ ôóíê- öèîíàëà îáåñïå÷åíèÿ öåëîñòíîñòè ñåòè ïîòî- êà äàííûõ ñ ó÷åòîì ïîäõîäà ê ñîõðàíåíèþ êîíôëèêòíîãî ìíî- æåñòâà Rete Utility Èíèöèàëèçàöèÿ è äîñòóï ê �- è �-ñåòè ñ âíåøíèõ ìîäóëåé Ñåòü ïîòîêà äàí- íûõ èëè çàïðîñ íà åå èíèöèàëè- çàöèþ � / �-ñåòü Ìîäèôèêàöèÿ èíèöèà- ëèçàöèè è äîñòóïà ê ñå- òè ïîòîêà äàííûõ Òàáëèöà 3 �-ñåòü îòñóòñòâóåò â Treat àëãîðèòìå. Ñîãëàñîâàíèå ïåðåìåííûõ îñóùåñòâëÿåòñÿ â ðåæèìå ëîãè÷åñêîãî âûâîäà ïî äèíàìè÷åñêè ñîçäàííîé ñåòè. Ñåòü ñîãëàñîâàíèÿ ôîðìèðóåòñÿ òîëüêî äëÿ ïðîäóêöèé, â êîòîðûõ áûëè àêòèâèðîâàíû âñå �-âåðøèíû� Äëÿ îáåñïå÷åíèÿ ìîäèôèêàöèè Rete àëãîðèòìà â Treat íåîáõîäèìî âûïîëíèòü ñëåäóþùèå øàãè: 1. Ìîäèôèöèðîâàòü ïðåäñòàâëåíèå ñåòè ñîïîñòàâëåíèÿ äëÿ îáåñïå- ÷åíèÿ ñîõðàíåíèÿ äàííûõ, íåîáõîäèìûõ äëÿ ðàáîòû Treat; óäàëèòü èçáû- òî÷íóþ èíôîðìàöèþ. 2. Óäàëèòü ôóíêöèîíàë ôîðìèðîâàíèÿ è îáðàáîòêè �-ñåòè. 3. Ðåàëèçîâàòü äèíàìè÷åñêîå ôîðìèðîâàíèå ñåòè ñîãëàñîâàíèÿ è åå îáðàáîòêè ñ ïðèìåíåíèåì òåêóùèõ ïîäõîäîâ ê ïðåäñòàâëåíèþ äàííûõ â ñèñòåìå. Èçìåíåíèÿ â ñèñòåìå, íåîáõîäèìûå äëÿ ðåàëèçàöèè Treat àëãîðèòìà ñîïîñòàâëåíèÿ ñ îáðàçöîì, ïðèâåäåíû â òàáë. 4. Äëÿ êàæäîãî èç ìîäóëåé Î.À. Ìàæàðà 70 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Èçìåíåíèÿ â ðàáî÷åé ïàìÿòè ÑÅ ñîãëàñîâûâàåòñÿ ñ ôàêòîì? ÑÅ ïîëîæèòåëüíûé? ÑÅ ïîëîæèòåëüíûé? ÑÅ ñîãëàñîâàíî ñ äðóãèì ôàêòîì? Ôàêò äîáàâëÿåòñÿ? Äà Äà Äà Äà Íåò Íåò Íåò Äîáàâèòü ôàêò ê ïàìÿòè�- Äîáàâèòü íîâóþ àêòèâàöèþ ê êîíôëèêòíîìó ìíîæåñòâó Äîáàâèòü íîâóþ àêòèâàöèþ ê êîíôëèêòíîìó ìíîæåñòâó Óäàëèòü ôàêò èç ïàìÿòè�- Âíåñòè èçìåíåíèÿ â ñïèñîê àêòèâàöèé Âíåñòè èçìåíåíèÿ â ñïèñîê àêòèâàöèé Óäàëèòü èç êîíôëèêòíîãî ìíîæåñòâà ïðàâèëà, ñîîòâåòñòâóþùèå àêòèâàöèè Âûïîëíèòü äîïîëíèòåëüíóþ ïðîâåðêó íà ñîãëàñîâàíèå ñ òåêóùèìè àêòèâàöèÿìè Ðèñ. 3. Ñõåìà ðàáîòû Treat àëãîðèòìà Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 71 Ìîäóëü Ôóíêöèÿ Íàçíà÷åíèå Ñòàòóñ Óðîâåíü îáðàáîòêè Treat-ñåòè Analy- sis Variable Analysis Îáðàçóåò âçàèìíûå ññûëêè íà ïå- ðåìåííûå â ïðåäåëàõ îäíîãî ïðàâè- ëà. Ïðîâåðÿåò ñåìàíòè÷åñêèå îøèá- êè, ñâÿçàííûå ñ ñîãëàñîâàíèåì ïå- ðåìåííûõ Ìîäèôèöèðî- âàííàÿ Ïîñòðîåíèå �-ñåòè Create External Network Test Ãåíåðèðóåò âûðàæåíèÿ äëÿ ñîãëàñî- âàíèÿ ïåðåìåííûõ â äèíàìè÷åñêîé ñåòè ñîãëàñîâàíèÿ Äîáàâëåíà Ïîñòðîåíèå äèíàìè÷åñêîé ñåòè ñîãëàñî- âàíèÿ Get Variables Ðàñïðîñòðàíÿåò ïî ñåòè ïîòîêà äàí- íûõ èíôîðìàöèþ î ðàñïîëîæåíèè ïåðåìåííûõ â àíòåöåäåíòå â îäíîì ñåìàíòè÷åñêîì ïðîñòðàíñòâå Áåç èçìåíåíèé Ïîñòðîåíèå �-ñåòè Process Variable Îáåñïå÷èâàåò îáðàáîòêó ïåðåìåííîé, âñòðå÷àþùåéñÿ â ïðàâèëå îäèí ðàç Òî æå Òî æå Build Construct Joins Èíòåãðèðóåò âíóòðåííèå è âíåøíèå òåñòû â ñîîòâåòñòâóþùèå âåðøèíû �- �-ñåòåé Ìîäèôèöèðî- âàííàÿ Ïîñòðîåíèå ñåòè ïîòîêà äàí- íûõ Initialize FactPat- terns Äîáàâëÿåò øàáëîíû ôàêòîâ ê ñåòè ïîòîêà äàííûõ Áåç èçìåíåíèé Ïîñòðîåíèå �-ñåòè PlaceFact Pattern Èíòåãðèðóåò øàáëîíû ôàêòîâ â �- ñåòü Òî æå Òî æå Construct Dynamic Joins Èíòåãðèðóåò âíåøíèå òåñòû â äè- íàìè÷åñêóþ ñåòü ñîãëàñîâàíèÿ Äîáàâëåíà Ïîñòðîåíèå äèíàìè÷åñêîé ñåòè ñîãëàñî- âàíèÿ Gene- rate FieldCon- version Ãåíåðèðóåò âûðàæåíèÿ äëÿ òåñòîâ, ñâÿçàííûõ ñ îãðàíè÷åíèÿìè íà çíà- ÷åíèå â øàáëîíàõ, è èíòåãðèðóåò èõ â ñåòü ïîòîêà äàííûõ Ìîäèôèöèðî- âàííàÿ Ïîñòðîåíèå ñåòè ïîòîêà äàííûõ Getvar Replace Çàìåíÿåò ïåðåìåííûå â óçëàõ ñåòè íà âûçîâû ôóíêöèé, ïîëó÷àþùèå òåêóùåå çíà÷åíèå ïåðåìåííîé èç ÷àñòè÷íîãî ñîãëàñîâàíèÿ èëè àêòè- âàöèè Òî æå Ïîñòðîåíèå è îáðàáîòêà ñå- òè ïîòîêà äàí- íûõ Match FactPattern Match Îáåñïå÷èâàåò âûïîëíåíèå ñîïîñ- òàâëåíèÿ â �-ñåòè Áåç èçìåíåíèé Îáðàáîòêà �- cåòè Òàáëèöà 4 Î.À. Ìàæàðà 72 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Ìîäóëü Ôóíêöèÿ Íàçíà÷åíèå Ñòàòóñ Óðîâåíü îáðàáîòêè Treat-ñåòè Retract Network Retract Óäàëÿåò èç ñåòè ïîòîêà äàííûõ èí- ôîðìàöèþ î ïðåäâàðèòåëüíîì ñîã- ëàñîâàíèè ñ çàäàííûì ôàêòîì Ìîäèôèöèðî- âàííàÿ Îáðàáîòêà ïðîöåññà óäà- ëåíèÿ ôàêòà â ñåòè ïîòîêà äàííûõ Delete Partial Matches Óäàëÿåò âñå ÷àñòè÷íûå ñîãëàñîâàíèÿ èç ñåòè Òî æå Óäàëåíèå ôàê- òîâ èç ñåòè â ïðîöåññå ïåðå- çàãðóçêè ñèñ- òåìû Delete Partial Join Matches Óäàëÿåò óçëû ñåòè ñîãëàñîâàíèÿ, íå ïðèâåäøèå ê àêòèâàöèè, èç äèíàìè- ÷åñêîé ñåòè ïîòîêà äàííûõ Äîáàâëåíà Îáðàáîòêà äè- íàìè÷åñêîé ñåòè ñîãëàñî- âàíèÿ Drive Network Assert Îáðàáàòûâàåò ñîãëàñîâàíèÿ ïåðåìåí- íûõ è ôîðìèðîâàíèå àêòèâàöèé äëÿ äîáàâëåíèÿ â êîíôëèêòíîå ìíîæåñòâî Ìîäèôèöèðî- âàííàÿ Îáðàáîòêà ñîã- ëàñîâàíèÿ ïåðå- ìåííûõ â äè- íàìè÷åñêîé ñåòè Network AssertLeft Ïðîâåðÿåò ñîãëàñîâàíèÿ ïåðâîãî àê- òèâèðîâàííîãî óñëîâíîãî ýëåìåíòà ñ äðóãèìè øàáëîíàìè àíòåöåäåíòà Òî æå Òî æå Network Assert Right Îáåñïå÷èâàåò ïðîâåðêó ñîãëàñîâà- íèÿ ïåðåìåííûõ â ïðåäåëàõ àíòå- öåäåíòà " " " " PPDrive Èíòåãðèðóåò ðåçóëüòàòû ñîãëàñîâà- íèÿ â �-ñåòè è ðåçóëüòàòû ñîãëàñî- âàíèÿ ïåðåìåííûõ " " Îáðàáîòêà ñå- òè ïîòîêà äàí- íûõ Engine AddActi- vation Äîáàâëÿåò àêòèâàöèè â êîíôëèêòíîå ìíîæåñòâî " " Òî æå Remove Activation Óäàëÿåò àêòèâàöèè èç êîíôëèêòíî- ãî ìíîæåñòâà " " " " Rete Utility Merge Partial Matches Îáúåäèíÿåò ÷àñòè÷íûå ñîãëàñîâàíèÿ äëÿ óìåíüøåíèÿ çàòðàò ïàìÿòè " " " " Remove Alpha Memory Matches Óäàëÿåò �-ïàìÿòü èç óçëîâ ñåòè Áåç èçìåíåíèé Îáðàáîòêà �-ñåòè Destroy Beta Memory Óäàëÿåò ðåçóëüòàòû ñîãëàñîâàíèÿ ïåðåìåííûõ â óçëàõ ñåòè ñîãëàñî- âàíèÿ Ìîäèôèöèðî- âàííàÿ Îáðàáîòêà ñîãëàñîâàíèÿ ïåðåìåííûõ Îêîí÷àíèå òàáë. 4 âûäåëåíû îñíîâíûå ôóíêöèè è ñòðóêòóðû äàííûõ, êîòîðûå îáåñïå÷èâàþò ïðîöåññ ïîñòðîåíèÿ è îáðàáîòêè ñåòè ñîïîñòàâëåíèÿ àëãîðèòìà. Ñòàòóñ ôóíêöèè îïðåäåëÿåòñÿ îáúåìîì íåîáõîäèìûõ èçìåíåíèé. Ñ÷èòàåòñÿ, ÷òî ôóíêöèÿ îñòàëàñü áåç èçìåíåíèé ëîãèêè, åñëè ìîäèôèêàöèÿ êàñàëàñü òîëüêî âçàèìîäåéñòâèé ìåæäó ìîäóëÿìè. Óðîâåíü îáðàáîòêè Treat-ñåòè îïðåäåëÿåòñÿ ýòàïîì ñîïîñòàâëåíèÿ è ïîäìíîæåñòâàìè óçëîâ ñåòè ïîòîêà äàííûõ, êîòîðûìè îïåðèðóåò ôóíêöèÿ. Ïîñòðîåíèþ �-ñåòè ñîîòâåòñòâóåò ýòàï ïðåäêîìïèëÿöèè. Ôîðìèðîâàíèå äèíàìè÷åñêîé ñåòè ñîãëàñîâàíèÿ è ïîñëåäóþùàÿ îáðàáîòêà ñåòè ïîòîêà äàííûõ ïðîèñõîäÿò íà ýòàïå ëîãè- ÷åñêîãî âûâîäà. Òàêèì îáðàçîì, äåòàëèçèðîâàíû âñå ìîäèôèêàöèè, îáåñïå÷èâàþùèå ðàñøèðåíèå îáîëî÷êè ïðîäóêöèîííûõ ñèñòåì CLIPS äîïîëíèòåëüíûì àëãîðèòìîì ñîïîñòàâëåíèÿ ñ ñîõðàíåíèåì îñíîâíûõ ïîäõîäîâ ê ïðåä- ñòàâëåíèþ äàííûõ. Ýòî ïîçâîëÿåò ðåàëèçîâàòü äâà ìåõàíèçìà ñîïîñòàâ- ëåíèÿ â åäèíîé ñðåäå ñ âîçìîæíîñòüþ âûáîðà îäíîãî èç íèõ ïîëüçîâà- òåëåì — ðàçðàáîò÷èêîì ïðèêëàäíîé ïðîäóêöèîííîé ñèñòåìû. Äëÿ ïðèìåðà òåñòèðîâàíèÿ ðàñøèðåííîé îáîëî÷êè CLIPS ïðèâåäåì îäíó èç îáùåïðèíÿòûõ â ïðîäóêöèîííûõ ñèñòåìàõ òåñòîâûõ çàäà÷, Man- ners, ðåøàþùóþ êîìáèíàòîðíóþ ïðîáëåìó ðàññàäêè ãîñòåé ïî èíòåðåñàì (çàäàíî 64 ÷åëîâåêà). Äëÿ îïèñàíèÿ ýòîé çàäà÷è èñïîëüçóåòñÿ âîñåìü ïðà- âèë (ïðîäóêöèé), â àíòåöåäåíòå êîòîðûõ ïðåäñòàâëåíû óñëîâèÿ, îïðåäå- ëÿþùèå ñîñåäåé çà ñòîëîì. Ýòè óñëîâèÿ ôîðìàëèçîâàíû â âèäå ôàêòîâ, ïðåäñòàâëÿþùèõ îòíîøåíèå, ñâÿçûâàþùåå èìÿ ãîñòÿ, åãî ïîë è õîááè. Ôàêòû ÿâëÿþòñÿ îáðàçöàìè äëÿ ìåõàíèçìà ñîïîñòàâëåíèÿ. Äëÿ âûïîë- íåíèÿ ïðîãðàììû íà âõîäíûõ äàííûõ ïî ðàçìåùåíèþ 64-õ ãîñòåé òðå- áóåòñÿ çàïóñê 2271 ïðàâèëà. Ïðè ýòîì ñðåäíåå ÷èñëî ôàêòîâ ðàáî÷åé ïàìÿòè — 1307, ñðåäíåå ÷èñëî àêòèâàöèé — 63. Çàòðàòû ïàìÿòè äëÿ Rete àëãîðèòìà — 1828 Kb, äëÿ Treat — 1327 Kb. Ðåçóëüòàòû òåñòèðîâàíèÿ ïîäòâåðæäàþò ïðåèìóùåñòâà Treat àëãîðèòìà ïî ðåñóðñîåìêîñòè. Âûâîäû Ïðåäëîæåííûé ñïîñîá ðàñøèðåíèÿ ïðîäóêöèîííîé îáîëî÷êè CLIPS äàåò âîçìîæíîñòü â äàëüíåéøåì äîïîëíÿòü ñèñòåìó äîáàâî÷íûìè èíêðåìåíò- íûìè àëãîðèòìàìè ñîïîñòàâëåíèÿ ñ ñîõðàíåíèåì åäèíîãî ôîðìàòà ïðåä- ñòàâëåíèÿ äàííûõ. Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 73 ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Forgy C.L. On the Efficient Implementation of Production System. PhD thesis. — Pittsburg, 1979. — 356 p. — [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://reports-archive.adm. cs.cmu.edu/anon/scan/CMU-CS-79-forgy.pdf. 2. Miranker D.P. TREAT: A New and Efficient Match Algorithm for AI Production Systems. — London: Pitman/Morgan Kaufmann, 1987. — 144 p. 3. Sanjay K. Importance of Expert System Shell in Development of Expert System// Intern. J. of Innovative Research and Development. — 2015. — Vol. 4, Issue 3. — P. 128 — 133. — [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://www.ijird.com/index.php/ijird/article/ view/62073. 4. Stefano A., Gangemi F., Santoro C. ERESYE: artificial intelligence in Erlang programs // ERLANG’05: Proc. of the 2005 ACM SIGPLAN workshop on Erlang. —Tallinn, Estonia, 2005. — P. 62—71. — [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://dl.acm.org/cita- tion. cfm?id=1088373&dl=ACM&coll=DL&CFID=542447529&CFTOKEN=27514249. 5. CLIPS Rule Based Programming Language.— [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://sourceforge.net/projects/clipsrules/files/CLIPS/6.30/. 6. Doorenbos R. Production Matching for Large Learning Systems. — Pittsburg: Computer Science Department, Carnegie Mellon University, 1995. — 208 p. 7. Riley G. CLIPS Implementation of Rete // Proc. of October Rules Conference. — Chantilly, 2009. — [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://sourceforge.net/p/ clipsrules/ discus- sion/776945/thread/8460f0d6/e8cb/attachment/CLIPS_Implementation_of_ Rete.pdf . 8. Sellis T., Lin C.C., Raschid L. Implementing large production systems in a DBMS envi- ronment: concepts and algorithms // Management of data : ACM SIGMOD international con- ference. — N Y: ACM Press, 1988. — P. 404—423. 9. Berstel B. Extending the RETE algorithm for event management // Temporal Representation and Reasoning: Ninth Intern. Symposium. IEEE Computer Society Press. — Washington, 2002. — P. 49—51. 10. Kang J.A. Shortening matching time in OPS5 production systems// IEEE Transactions on Software Engineering. — 2004. — ¹ 30 (7). — P. 448—457. 11. Ìàæàðà Î.Î. Ïîð³âíÿííÿ Rete òà Treat àëãîðèòì³â ñï³âñòàâëåííÿ ç³ çðàçêîì // Àäàï- òèâí³ Ñèñòåìè Àâòîìàòè÷íîãî Óïðàâë³ííÿ: ̳æâ³äîì÷èé íàóêîâî-òåõí³÷íèé çá³ðíèê. Âèï. 1 (24) — Êè¿â: ÍÒÓÓ «Êϲ», 2014. — Ñ. 53—61. 12. Proctor M. Symmetrical and Asymmetrical Rete. — [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: — http://blog.athico.com/2008/10/symmetrical-and-asymmetrical-rete.html. 13. Äæàððàíòàíî Äæ., Ðàéëè Ã. Ýêñïåðòíûå ñèñòåìû: ïðèíöèïû ðàçðàáîòêè è ïðî- ãðàììèðîâàíèå. 4-å èçäàíèå; ïåð. ñ àíãë. — Ì. : ÎÎÎ «È.Ä. Âèëüÿìñ», 2007. — 1152 ñ. O.À. Mazhara TREAT ALGORITHM IMPLEMENTATION BY THE BASIC MATCH ALGORITHM BASED ON CLIPS PROGRAMMING ENVIRONMENT Implementation of the logical inference by the applied knowledge base based on Rete and Treat match algorithms for choosing optimal one in terms of resources usage and performance has been proposed. Treat algorithm implementation, which allows saving current approaches for data rep- resentation and optimizations by hashing, precompile network representation and knowledge base representation, was formalized for CLIPS. The proposed approach allows further extension of the CLIPS programming environment by additional incremental match algorithms. K e y w o r d s: match, Rete algorithm, Treat algorithm, production system, inference, CLIPS. Î.À. Ìàæàðà 74 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 REFERENCES 1. Forgy, C.L. (1979), “On the Efficient Implementation of Production System”, Doctor’s De- gree, Carnegie Mellon University, Pittsburgh, USA. 2. Miranker, D.P. (1987), “TREAT: A New and Efficient Match Algorithm for AI Production System”, Doctor’s degree, Pitman / Morgan Kaufmann, London, UK. 3. Sanjay, K. (2015), “Importance of Expert System Shell in Development of Expert System”, International Journal of Innovative Research and Development, Vol. 4 no. 3, pp. 128-133, available at: http://www.ijird.com/index.php/ijird/article/view/62073 (accessed September 1, 2015). 4. Stefano, A. Gangemi, F. and Santoro, C. (2005), “ERESYE: artificial intelligence in Erlang programs”, Proceedings of the ACM SIGPLAN workshop on Erlan, Tallinn, Estonia, Sep- tember 26-28, 2005. New York: ACM, available at: http://dl.acm.org/citation.cfm?id= 1088373&dl=ACM&coll=DL&CFID=542447529&CFTOKEN=27514249 (accessed Au- gust 10, 2015). 5. CLIPS Rule Based Programming Language, available at: http://sourceforge.net/projects/ clipsrules/files/CLIPS/6.30/ (accessed August 30, 2015). 6. Doorenbos, R. (1995), “Production Matching for Large Learning Systems”, Doctor’s De- gree, Carnegie Mellon University , Pittsburgh, USA. 7. Riley, G. (2009), “CLIPS Implementation of Rete”, Proceedings of the October Rules Con- ference, Chantilly, Virginia, USA, October 25-26, 2009, available at: http:// sourceforge. net/p/clipsrules/discussion/776945/thread/8460f0d6/e8cb/attachment/CLIPS_ Implementa- tion_of_Rete.pdf (accessed September 2, 2015). 8. Sellis, T. Lin, C.C. and Raschid, L. (1988), “Implementing large production systems in a DBMS environment: Concept and algorithms”, Proceedings of the ACM SIGMOD Interna- tional conference Management of data, Chicago, Illinois, June 1-3, 1988, pp. 404-423. 9. Berstel, B. (2002), “Extending the RETE algorithm for event management”, Proceedings of the Ninth International Symposium on Temporal Representation and Reasoning, IEEE Com- puter Society, Washington, DC, USA , pp. 49-51. 10. Kang, J.A., Mo, A. and Cheng, K. (2004), “Shortening Matching Time in OPS5 Production Systems”, IEEE Transactions on Software Engineering, Vol. 30 , no.7, pp. 448-457. 11. Mazhara, O.O. (2014), “Comparison of the Treat and Rete match algorithms”, Adaptyvni Systemy Avtomatychnogo Upravlinnya: Mizhvidomchyy naukovo-tehnichny zbirnyk, Kiev, KPI, Vol. 1, no. 24, pp. 53-61. 12. Proctor, M. (2008), “Symmetrical and Asymmetrical Rete”, available at: http://blog.athico. com/2008/10/symmetrical-and-asymmetrical-rete.html (accessed September 3, 2015). 13. Giarratano, J. and Riley, G. (2007), Ekspertnye sistemy: printsipy razrabotki i programiro- vanie [Expert systems: design principles and programming], OOO «I.D. Vil’yams», Mos- cow, Russia. Ïîñòóïèëà 10.09.15 ÌAÆÀÐÀ Îëüãà Àëåêñàíäðîâíà, àñïèðàíò, àññèñòåíò êàôåäðû àâòîìàòèçàöèè ïðîåêòè- ðîâàíèÿ ýíåðãåòè÷åñêèõ ïðîöåññîâ è ñèñòåì òåïëîýíåðãåòè÷åñêîãî ôàêóëüòåòà Íàöèîíàëü- íîãî òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò», êîòîðûé îêîí- ÷èëà â 2012 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — èñêóññòâåííûé èíòåëëåêò, ýêñïåðòíûå è ïðîäóêöèîííûå ñèñòåìû. Ðåàëèçàöèÿ Treat àëãîðèòìà íà îñíîâå ñîïîñòàâëåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 75
id nasplib_isofts_kiev_ua-123456789-101165
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 0204-3572
language Russian
last_indexed 2025-12-02T12:48:53Z
publishDate 2015
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
record_format dspace
spelling Мажара, О.А.
2016-05-31T18:04:34Z
2016-05-31T18:04:34Z
2015
Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS / О.А. Мажара // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 61-75. — Бібліогр.: 13 назв. — рос.
0204-3572
https://nasplib.isofts.kiev.ua/handle/123456789/101165
004.825
Предложена реализация логического вывода по прикладной базе знаний на основании Rete и Treat алгоритмов сопоставления с образцом для определения оптимального из них по ресурсоемкости и быстродействию. Приведено описание реализации Treat алгоритма для программной оболочки CLIPS, позволяющее сохранить существующие структуры данных и методы оптимизации логического вывода вследствие хеширования, представления сети предкомпиляции и реорганизации базы знаний. Предложенный подход позволяет в дальнейшем расширить программную среду CLIPS дополнительными инкрементными алгоритмами сопоставления.
Запропоновано реалізацію логічного виведення за прикладною базою знань на основі Rete і Treat алгоритмів співставлення зі зразком для визначення оптимального з них за ресурсоємністю та швидкодією. Надано опис реалізації Treat алгоритму для програмної оболонки CLIPS, який дозволяє зберегти існуючі структури даних та методи оптимізації логічного виведення внаслідок хешування, представлення мережі прекомпіляції та реорганізації бази знань. Запропонований підхід дозволяє надалі розширити програмне середовище CLIPS додатковими інкрементними алгоритмами співставлення.
Implementation of the logical inference by the applied knowledge base based on Rete and Treat match algorithms for choosing optimal one in terms of resources usage and performance has been proposed. Treat algorithm implementation, which allows saving current approaches for data representation and optimizations by hashing, precompile network representation and knowledge base representation, was formalized for CLIPS. The proposed approach allows further extension of the CLIPS programming environment by additional incremental match algorithms.
ru
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Электронное моделирование
Информационные технологии
Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
Treat algorithm implementation by the basic match algorithm based on CLIPS programming environment
Article
published earlier
spellingShingle Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
Мажара, О.А.
Информационные технологии
title Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
title_alt Treat algorithm implementation by the basic match algorithm based on CLIPS programming environment
title_full Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
title_fullStr Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
title_full_unstemmed Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
title_short Реализация Treat алгоритма на основе сопоставления с образцом в программной оболочке CLIPS
title_sort реализация treat алгоритма на основе сопоставления с образцом в программной оболочке clips
topic Информационные технологии
topic_facet Информационные технологии
url https://nasplib.isofts.kiev.ua/handle/123456789/101165
work_keys_str_mv AT mažaraoa realizaciâtreatalgoritmanaosnovesopostavleniâsobrazcomvprogrammnoioboločkeclips
AT mažaraoa treatalgorithmimplementationbythebasicmatchalgorithmbasedonclipsprogrammingenvironment

Схожі ресурси