Вхождения в моноидах треков
Запропоновано ефективні алгоритми для розв’язання декількох задач входження трека-зразка в трек-об’єкт. Розглянуто задачі пошуку зразка в треку, пов’язані з задачею пошуку частих зразків в структурованих даних, та задачі обчислення числа вікон, що містять зразок....
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45241 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Вхождения в моноидах треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 4. — С. 31-38. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45241 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-452412013-06-11T03:09:01Z Вхождения в моноидах треков Шахбазян, К.В. Шукурян, Ю.Г. Кибернетика Запропоновано ефективні алгоритми для розв’язання декількох задач входження трека-зразка в трек-об’єкт. Розглянуто задачі пошуку зразка в треку, пов’язані з задачею пошуку частих зразків в структурованих даних, та задачі обчислення числа вікон, що містять зразок. Efficient pattern matching algorithms for traces and their dependence graphs are proposed. Pattern matching problems related to problems of recognizing frequent patterns in structured data, counting the number of windows of trace-object where pattern is included are considered. 2010 Article Вхождения в моноидах треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 4. — С. 31-38. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45241 519.712 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Шахбазян, К.В. Шукурян, Ю.Г. Вхождения в моноидах треков Кибернетика и системный анализ |
| description |
Запропоновано ефективні алгоритми для розв’язання декількох задач входження трека-зразка в трек-об’єкт. Розглянуто задачі пошуку зразка в треку, пов’язані з задачею пошуку частих зразків в структурованих даних, та задачі обчислення числа вікон, що містять зразок. |
| format |
Article |
| author |
Шахбазян, К.В. Шукурян, Ю.Г. |
| author_facet |
Шахбазян, К.В. Шукурян, Ю.Г. |
| author_sort |
Шахбазян, К.В. |
| title |
Вхождения в моноидах треков |
| title_short |
Вхождения в моноидах треков |
| title_full |
Вхождения в моноидах треков |
| title_fullStr |
Вхождения в моноидах треков |
| title_full_unstemmed |
Вхождения в моноидах треков |
| title_sort |
вхождения в моноидах треков |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45241 |
| citation_txt |
Вхождения в моноидах треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 4. — С. 31-38. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šahbazânkv vhoždeniâvmonoidahtrekov AT šukurânûg vhoždeniâvmonoidahtrekov |
| first_indexed |
2025-07-04T03:55:22Z |
| last_indexed |
2025-07-04T03:55:22Z |
| _version_ |
1836687112606318592 |
| fulltext |
ÓÄÊ 519.712
Ê.Â. ØÀÕÁÀÇßÍ, Þ.Ã. ØÓÊÓÐßÍ
ÂÕÎÆÄÅÍÈß Â ÌÎÍÎÈÄÀÕ ÒÐÅÊÎÂ
Êëþ÷åâûå ñëîâà: ñðàâíåíèå ñ îáðàçöîì, ìîíîèä òðåêîâ, ãðàô çàâèñèìîñòè.
ÂÂÅÄÅÍÈÅ
Äëÿ äâóõ òðåêîâ òðåêà-îáúåêòà t è òðåêà-îáðàçöà p, ïðèíàäëåæàùèõ çàäàííîìó
ñâîáîäíîìó ÷àñòè÷íî-êîììóòàòèâíîìó ìîíîèäó M D( , )� òðåêîâ, ñòàâÿòñÿ ñëåäó-
þùèå çàäà÷è.
• Îïðåäåëèòü, âõîäèò ëè òðåê-îáðàçåö p M D� ( , )� â òðåê-îáúåêò
t M D� ( , )� . Òðåê p âõîäèò â òðåê t , åñëè ãðàô çàâèñèìîñòè p ìîæíî ïîëó÷èòü èç
ãðàôà çàâèñèìîñòè t óäàëåíèåì íåêîòîðûõ âåðøèí è ïðèìûêàþùèõ ê íèì äóã.
• Ïîäñ÷èòàòü äëÿ çàäàííîãî ñëîâà-ïðåäñòàâëåíèÿ y òðåêà t è öåëîãî ïîëîæè-
òåëüíîãî w ÷èñëî w-òðåêîâûõ îêîí ñëîâà y , â êîòîðûå âõîäèò òðåê-îáðàçåö p .
• Ïîäñ÷èòàòü ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ òðåêà-îáúåêòà t , â êîòîðûå âõî-
äèò òðåê-îáðàçåö p .
Ïðîáëåìà ñðàâíåíèÿ íåêîòîðîãî îáúåêòà (target) ñ îáðàçöîì (pattern) äëÿ ìàñ-
ñèâîâ ñòðóêòóðèðîâàííûõ äàííûõ ïðèâëåêàåò áîëüøîå âíèìàíèå, è åå ðåøåíèå
âàæíî äëÿ ðàçâèòèÿ ìåòîäîâ âñêðûòèÿ äàííûõ (date mining). Îäíèì èç íàèáîëåå îá-
ùèõ ôîðìàëèçìîâ äëÿ ìîäåëèðîâàíèÿ ñòðóêòóðèðîâàííûõ äàííûõ ÿâëÿþòñÿ ãðàôû.
Îäíàêî ïðè ðàññìîòðåíèè ãðàôîâ îáùåãî âèäà âîçíèêàþò ïðîáëåìû, ñâÿçàííûå ñ
ýôôåêòèâíîñòüþ. Êàê ïðàâèëî, ïîäîáíûå çàäà÷è èìåþò î÷åâèäíûå ïåðåáîðíûå àë-
ãîðèòìû è ïîýòîìó çäåñü ðå÷ü èäåò î íàõîæäåíèè ýôôåêòèâíûõ àëãîðèòìîâ.
Ïðîáëåìà ñðàâíåíèÿ îáúåêòà ñ îáðàçöîì ñòàâèòñÿ îáû÷íî â îäíîé èç ñëåäóþ-
ùèõ ïîñòàíîâîê:
1) íàéòè âõîæäåíèå îáðàçöà â îáúåêò — ìàññèâ äàííûõ — â âèäå ôàêòîðà ýòî-
ãî ìàññèâà, ò.å. öåëèêîì, áåç ïðåðûâàíèé;
2) íàéòè âõîæäåíèå îáðàçöà â îáúåêò â âèäå ïîäïîñëåäîâàòåëüíîñòè, ò.å. ñ âîç-
ìîæíûìè ïðåðûâàíèÿìè;
3) ïðè çàäàííîì ðàçìåðå îêíà — ôàêòîðà îáúåêòà — íàéòè âõîæäåíèÿ îáðàçöà
â âèäå ïîäïîñëåäîâàòåëüíîñòåé, îãðàíè÷åííûõ âðåìåííûìè óñëîâèÿìè, ò.å. âõîæ-
äåíèÿ â îêíà-ôàêòîðû çàäàííîãî ðàçìåðà;
4) ïîäñ÷èòàòü ÷èñëî îêîí, ñîäåðæàùèõ îáðàçåö.
Ïîñëåäíÿÿ ïîñòàíîâêà òåñíî ñâÿçàíà ñ ïðîáëåìîé ÷àñòûõ ýïèçîäîâ (frequent
episodes), ãäå ïîä ýïèçîäîì ïîíèìàåòñÿ âõîæäåíèå îáðàçöà âíóòðü îêíà, ò.å. âíóòðü
çàäàííîãî èíòåðâàëà âðåìåíè.
Ïðîáëåìû ñðàâíåíèÿ ñ îáðàçöîì â ñâîáîäíûõ ìîíîèäàõ (äëÿ ñëîâ) ðàçðàáàòû-
âàëàñü ìíîãèìè àâòîðàìè. Øèðîêî èçâåñòåí àëãîðèòì Êíóòà, ðåøàþùèé çàäà÷ó ïî-
èñêà îáðàçöà êàê ôàêòîðà. Ðàáîòû [1–7] ýôôåêòèâíî ðåøàþò çàäà÷è âõîæäåíèÿ ñëî-
âà-îáðàçöà â îêíî ñëîâà-îáúåêòà â êà÷åñòâå ïîäïîñëåäîâàòåëüíîñòè — ïðè
çàäàííîì ðàçìåðå îêíà.
Çàäà÷è âõîæäåíèÿ, îòíîñÿùèåñÿ ê äåðåâüÿì, ðàññìàòðèâàëèñü â [7–10]. Çäåñü
ïðåäëîæåíû ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ çàäà÷è î ÷àñòûõ ýïèçîäàõ ïðè ðàç-
ëè÷íûõ ïîíÿòèÿõ îêíà â äåðåâüÿõ.
Çàäà÷à âõîæäåíèÿ òðåêà-îáðàçöà â îáúåêò, êàê ôàêòîðà, â ìîíîèäàõ òðåêîâ ðàñ-
ñìîòðåíà â [11], ãäå ïðåäëîæåí ëèíåéíûé àëãîðèòì åå ðåøåíèÿ.
Ìîíîèäû òðåêîâ (êîíå÷íî-ïîðîæäåííûå ÷àñòè÷íî êîììóòàòèâíûå ìîíîè-
äû) — ïðèçíàííûé èíñòðóìåíò äëÿ îïèñàíèÿ ñòðóêòóð ñîáûòèé â ïàðàëëåëüíûõ
è ðàñïðåäåëåííûõ ñèñòåìàõ [13], à òàêæå èñïîëüçóþòñÿ ïðè èññëåäîâàíèè çàäà÷ òå-
îðåòè÷åñêîãî ïðîãðàììèðîâàíèÿ [13, 14].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 31
© Ê.Â. Øàõáàçÿí, Þ.Ã. Øóêóðÿí, 2010
Äàííàÿ ðàáîòà ïðåäëàãàåò ýôôåêòèâíûå àëãîðèòìû äëÿ ðåøåíèÿ íåêîòîðûõ çà-
äà÷ âõîæäåíèÿ è ïîäñ÷åòà îêîí â ìîíîèäàõ òðåêîâ. Îíà ñîñòîèò èç ÷åòûðåõ ÷àñòåé.
Ïîñëå ïðåäâàðèòåëüíûõ ñâåäåíèé âî âòîðîé ÷àñòè ïðåäëàãàåòñÿ äâà àëãîðèòìà äëÿ
ïðîáëåìû âõîæäåíèÿ, êîãäà îáðàçåö p è îñíîâíîé òðåê t ïðåäñòàâëåíû ñëîâàìè
x p� è y t� . Ïåðâûé àëãîðèòì çàêëþ÷àåòñÿ â ïîñòðîåíèè àâòîìàòà ïî çàäàííîìó
ñëîâó x p� . Ýòîò àâòîìàò ñêàíèðóåò ñëîâî y t� , äîïóñêàÿ ñëîâî y , åñëè t ñîäåðæèò
òðåê p. Âòîðîé àëãîðèòì ïàðàëëåëüíî ñêàíèðóåò ñëîâà, ïðåäñòàâëÿþùèå òðåê-îáðà-
çåö è òðåê-îáúåêò, ÷èòàÿ êàæäûé ñèìâîë x îäèí ðàç, íî òðàíñôîðìèðóÿ y è âîçâðàùàÿñü
ê åãî íà÷àëó. Ñëîæíîñòü àëãîðèòìà — O t p( | | | | ) . Òðåòüÿ ÷àñòü ïðåäñòàâëÿåò àëãîðèòì, êî-
òîðûé ïîäñ÷èòûâàåò ÷èñëî w-òðåê-îêîí çàäàííîãî ïðåäñòàâëåíèÿ-ñëîâà y òðåêà t , âêëþ÷à-
þùèõ òðåê-îáðàçåö.  ïîñëåäíåé ÷àñòè îïèñàí àëãîðèòì, êîòîðûé ïîäñ÷èòûâàåò ÷èñëî
ìèíèìàëüíûõ ôàêòîðîâ t, âêëþ÷àþùèõ îáðàçåö p .
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
 ýòîì ðàçäåëå ïðèâîäÿòñÿ îñíîâíûå ïîíÿòèÿ è îáîçíà÷åíèÿ, ïîäðîáíåå ñì. [12].
Ïóñòü � — êîíå÷íûé àëôàâèò, D � �� � — ðåôëåêñèâíîå è ñèììåòðè÷íîå îò-
íîøåíèå çàâèñèìîñòè, l D� �( ) \� � — îòíîøåíèå íåçàâèñèìîñòè è ïåðåñòàíîâî÷-
íîñòè. Îòíîøåíèå I èíäóöèðóåò îòíîøåíèå ýêâèâàëåíòíîñòè �
I
íà �
* . Äâà ñëîâà
x y, *
�� ýêâèâàëåíòíû îòíîñèòåëüíî �
I
, åñëè ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü
z zk1 , ,� ñëîâ òàêèõ, ÷òî x z� 1 , y zk� è äëÿ âñåõ i i k( )1
ñóùåñòâóþò ñëîâà �zi ,
��zi è áóêâû ai , bi , óäîâëåòâîðÿþùèå óñëîâèÿì z z a b zi i i i i� � �� , z z b a zi i i i i� � � ��1 è
( , )a b Ii i � , ò.å. äâà ñëîâà ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäà îäíî ìîæåò
áûòü ïîëó÷åíî èç äðóãîãî äîïóñòèìûìè ïåðåñòàíîâêàìè ñîñåäíèõ íåçàâèñèìûõ
áóêâ. Òîãäà ìíîæåñòâî M D( , )� — òðåêîâûé ìîíîèä, åãî ýëåìåíòàìè ÿâëÿþòñÿ
êëàññû ýêâèâàëåíòíûõ ñëîâ èç �
* ïî îòíîøåíèþ �
I
, íàçûâàåìûå òðåêàìè. Íà òðå-
êàõ îïðåäåëåíî óìíîæåíèå. Òðåê t îáîçíà÷àåòñÿ [ ]x äëÿ ëþáîãî ïðåäñòàâëÿþùåãî
ñëîâà x t� . Äëèíà | |t òðåêà t åñòü äëèíà ëþáîãî åãî ïðåäñòàâëåíèÿ x t� . Äëÿ ëþáî-
ãî x ��
* ÷åðåç | |x îáîçíà÷àåì äëèíó x , à | |x a — ÷èñëî âõîæäåíèé áóêâû a â ñëîâî x .
Èñïîëüçóåì äâà ïðåäñòàâëåíèÿ òðåêîâ: â âèäå ãðàôîâ çàâèñèìîñòè è íàáîðà
ñëîâ. Ëþáîé òðåê t M D� ( , )� èìååò åäèíñòâåííîå ïðåäñòàâëåíèå â âèäå îòìå÷åí-
íîãî íàïðàâëåííîãî àöèêëè÷åñêîãî ãðàôà Gt , îáîçíà÷àþùåãî ÷àñòè÷íûé ïîðÿäîê.
Ãðàô Gt îïðåäåëÿåòñÿ ðåêóðñèâíî: Gt — ïóñòîé ãðàô, Gt a[ ] ïîëó÷àåòñÿ èç ãðàôà Gt
äîáàâëåíèåì ê íåìó âåðøèíû, îòìå÷åííîé áóêâîé a è íîâûìè äóãàìè, âåäóùèìè
ê ýòîé âåðøèíå èç âñåõ âåðøèí Gt , îòìå÷åííûõ ñèìâîëàìè, îò êîòîðûõ çàâèñèò
áóêâà a . Ãðàô Gt íàçûâàåòñÿ ãðàôîì çàâèñèìîñòè òðåêà t . Ñ ãðàôîì Gt àññîöèèðî-
âàíî ìíîæåñòâî ñëîâ, èíäóöèðóåìûõ âñåìè ïðè÷èííûìè ïîðÿäêàìè íà Gt . Ýòî
ìíîæåñòâî ñëîâ ôîðìèðóåò òðåê t .
Ðàññìîòðèì âòîðîå ïðåäñòàâëåíèå òðåêà — c ïîìîùüþ íàáîðà ñëîâ. Ïóñòü
{ , , }� �1 � m — ïîêðûòèå àëôàâèòà çàâèñèìîñòè (�, )D êëèêàìè, ò.å. ñåìåéñòâî ïîä-
ìíîæåñòâ � òàêèõ, ÷òî
� �i
i
m
�
�
1
� , � �i i D� � (i m� �1 2, , , )
( , )a b D i�
� : a b i, �� .
Òîãäà òðåê t M D� ( , )� ìîæåò áûòü ïðåäñòàâëåí m-êîé ñëîâ � ( )t �
� �{ ( ), , ( )}� �1 t tm , ãäå � i it( ) *
�� , è � i t( ) — ïðîåêöèÿ ïðîèçâîëüíîãî ñëîâà
y t� íà �
* [12].
Ñ÷èòàåòñÿ, ÷òî äëÿ çàäàííûõ äâóõ òðåêîâ: p t M D, ( , )� � p åñòü ïðåôèêñ t ,
åñëè t pq� , ãäå q M D� ( , )� , Pref t( ) îáîçíà÷àåò ìíîæåñòâî ïðåôèêñîâ òðåêà t .
Åñëè t pqr� , ãäå p q r M D, , ( , )� � , òî q íàçûâàåòñÿ ôàêòîðîì t . Çàìåòèì, ÷òî åñëè
p Pref t� ( ) , òî ñóùåñòâóþò x, y ��
* , t y� [ ] , p x� [ ] è x åñòü ïðåôèêñ ñëîâà y .
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Ïóñòü òðåê t çàäàí ñâîèì ïðåäñòàâëåíèåì � ( )t . Òîãäà ëþáîé ïðåôèêñ s òðåêà t
(îòíîñèòåëüíî � ( )t ) ìîæíî ïðåäñòàâèòü ìàññèâîì öåëûõ ÷èñåë s k km� � �( , , )1
�N m , èìåÿ ââèäó, ÷òî k si i� | ( ) |� , (i m� �1 2, , , ), è � i s( ) åñòü ïðåôèêñ äëèíû ki
ñëîâà � i t( ) . Òàêèì îáðàçîì, ( , , , )0 0 0� � e ïðåäñòàâëÿåò ïóñòîé ïðåôèêñ e , â òî
âðåìÿ êàê ïîëíûé òðåê t ïðåäñòàâëÿåòñÿ íàáîðîì t n n nm� �( , , , )1 2 , ãäå
n ti i� | ( )|� [12].
Ãðàô ïðåôèêñîâ òðåêà t åñòü îðèåíòèðîâàííûé àöèêëè÷åñêèé ãðàô
G V UPref t( ) ( , , )� � ñ ìíîæåñòâîì îòìå÷åííûõ äóã, ãäå V s s Pref t� �{ }/ ( ) , U —
ìíîæåñòâî óïîðÿäî÷åííûõ ïàð ( , )s r , � — îòìå÷àþùàÿ ôóíêöèÿ äëÿ äóã è äóãà
( , )s r èìååò ìåòêó � (( , ))s r a� , a �� , åñëè s r Pref t, ( )� , s r a� [ ] , ãäå [ ]a — òðåê,
ñîäåðæàùèé åäèíñòâåííîå îäíîáóêâåííîå ñëîâî a .
Äëÿ ìîíîèäà M M D� ( , )� M-àâòîìàò A M Q q F� ( , , , , )� 0 ïðåäñòàâëÿåòñÿ êî-
íå÷íûì ìíîæåñòâîì Q ñîñòîÿíèé, íà÷àëüíûì ñîñòîÿíèåì q Q0 � , ïîäìíîæåñòâîì
F Q� çàêëþ÷èòåëüíûõ ñîñòîÿíèé, ôóíêöèåé ïåðåõîäîâ � èç Q M� â Q , óäîâëåòâî-
ðÿþùèìè ñëåäóþùèì óñëîâèÿì:
� � �q Q q e q: ( , )� (e — ïóñòîé òðåê),
� �q Q , � � �t , t M D q t , t q t , t1 2 1 2 1 2( , ): ( , ) ( ( , ) )� � � � .
Ìíîæåñòâî T M M D� � ( , )� , ðàñïîçíàâàåìîå àâòîìàòîì A, îïðåäåëÿåòñÿ ñëåäó-
þùèì îáðàçîì: T t M q t F� � �{ }/ ( , )� 0 .
Àâòîìàò Çåëåíêè (àñèíõðîííûé àâòîìàò îòíîñèòåëüío M) åñòü M-àâòîìàò
A M Q q F� ( , , , , )� 0 , êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì äîïîëíèòåëüíûì óñëîâèÿì:
1) ñîñòîÿíèå Q åñòü ïðÿìîå ïðîèçâåäåíèå Q Qi
i
n
�
�
�
1
;
2) ñ êàæäûì a �� àññîöèèðîâàíî ìíîæåñòâî èíäåêñîâ K a i i n( ) / , , ,� � �{ { }}1 2 ,
òàêîå ÷òî K a K b( ) ( )� � � òîãäà è òîëüêî òîãäà, êîãäà ( , )a b I� ;
3) ôóíêöèÿ ïåðåõîäîâ � çàäàåòñÿ íàáîðîì îòîáðàæåíèé
{ }�a i K a i i K a i aQ Q: ( ) ( )� � �� � �� .
Äàëåå ôèêñèðóåì ìîíîèä M M D� ( , )� , ïîêðûòèå êëèêàìè {� �1 , ,� m } àëôà-
âèòà ( , )� D è öåëîå m — ÷èñëî êëèê â ïîêðûòèè.
ÂÕÎÆÄÅÍÈÅ ÒÐÅÊÀ-ÎÁÐÀÇÖÀ Â ÒÐÅÊ-ÎÁÚÅÊÒ
Îïðåäåëèì ïîíÿòèå âõîæäåíèÿ òðåêîâ è èññëåäóåì çàäà÷ó âõîæäåíèÿ.
Îïðåäåëåíèå 1. Òðåê p âõîäèò â òðåê t, åñëè äëÿ íåêîòîðûõ t p M Di i, ( , )� � ,
i n� �0 1, , , , ñïðàâåäëèâî
t t p t t p tn n n� � �0 1 1 1 , (1)
p p p pn� �1 2 . (2)
 ýòîì ñëó÷àå ñ÷èòàåòñÿ, ÷òî t ñîäåðæèò p è çàïèñûâàåì p t� . Ïðåäñòàâëå-
íèå (1) íàçûâàåì âõîæäåíèåì.
Ïóñòü r — íåêîòîðûé ïðåôèêñ òðåêà t r Pref t: ( )� , R rt ( ) — ìíîæåñòâî ìåòîê
äóã, âûõîäÿùèõ èç óçëà r â ãðàôå ïðåôèêñîâ G Pref t( ) . Ñëåäîâàòåëüíî,
a R t s r a Pref tt�
� �( ) [ ] ( ) .
Ñ êàæäîé áóêâîé a �� ñâÿæåì ìíîæåñòâî èíäåêñîâ I ( ) ={a i m a i� �{ , ,... , }| }1 2 �
òàêèõ, ÷òî ( , ) ( ) ( )a b I a b�
� � �I I .
Óòâåðæäåíèå 1. Ïóñòü òðåê t çàäàí ñâîèì ïðåäñòàâëåíèåì � � �( ) ( ) ( )t t tm� �{ }1 ,
ãäå � � �i i i nt t t
i
( ) ( ) ( ), ,
*
� � �1 � .
1.1. Åñëè r Pref t� ( ) , z ��
* , òî s r z Pref t� �[ ] ( ) òîãäà è òîëüêî òîãäà, êîãäà
ñóùåñòâóåò íàïðàâëåííûé ïóòü â G tPref ( ) èç r â s, êîòîðûé íåñåò ñëîâî z .
Ïóòü â G tPref ( ) ìàêñèìàëüíûé òîãäà è òîëüêî òîãäà, êîãäà îí ñîîòâåòñòâóåò
íåêîòîðîìó ñëîâó z t� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 33
1.2. Äëÿ ëþáîãî r Pref t� ( ) , åñëè r k km� �( , , )1 , ìíîæåñòâî R rt ( ) ìîæåò áûòü
âû÷èñëåíî êàê R r a i a at i ki
( ) / ( ) ,� � � ��{ }I � 1 .
1.3. Äëÿ ëþáîãî r Pref t� ( ) è a R rt� ( ), åñëè r k ki m� �( , , ) , ïðåäñòàâëåíèå
s r a k ki m� � � � �[ ] ( , , ) ìîæåò áûòü âû÷èñëåíî êàê
k ki i� � , åñëè i a�I ( ) , k ki i� � � 1, åñëè i a�I ( ) , i m� �1 2, , , .
1.4. Äëÿ ëþáûõ r Pref t� ( ) è ( , )a b I� , ãäå a R rt� ( ) è s r a� [ ] , ñïðàâåäëèâî
b R s b R tt t�
�( ) ( ) , r a b r b a[ ][ ] [ ][ ]� .
Äîêàçàòåëüñòâî ñëåäóåò èç îïðåäåëåíèÿ G Pref t( ) .
Ïóñòü p t M D, ( , )� � . Ïîñòðîèì äâà M-àâòîìàòà, ðåøàþùèõ ïðîáëåìó âõîæ-
äåíèÿ. Ïåðâûé àâòîìàò A p( ) îïðåäåëÿåòñÿ îáðàçöîì p è ðàñïîçíàåò òðåê-îáúåêò
t M D� ( , )� òîãäà è òîëüêî òîãäà, êîãäà p âõîäèò â t .
Âòîðîé àâòîìàò B t( ) îïðåäåëÿåòñÿ òðåêîì-îáúåêòîì t è ðàñïîçíàåò îáðàçåö
p M D� ( , )� òîãäà è òîëüêî òîãäà, êîãäà p âõîäèò â t .
Äîïóñòèì, ÷òî | | | |t p� � 1 è ÷òî òðåêè p è t çàäàíû ñâîèìè ñëîâàðíûìè ïðåä-
ñòàâëåíèÿìè x p� , y t� .
Óòâåðæäåíèå 2. Äëÿ ëþáîãî òðåêà p M D� ( , )� ñóùåñòâóåò äåòåðìèíèðîâàí-
íûé àñèíõðîííûé àâòîìàò Çåëåíêè A p( ) , êîòîðûé ðàñïîçíàåò t M D� ( , )� òîãäà è
òîëüêî òîãäà, êîãäà p t� .
Äîêàçàòåëüñòâî. Äëÿ ïîñòðîåíèÿ M-àâòîìàòà A p( ) ðàññìîòðèì ãðàô ïðåôèêñîâ
äëÿ p G p V p EPref: ( ) ( ( ), , )� � , ãäå V p s s Pref p( ) / ( )� �{ }. Äîáàâèì ê ìíîæåñòâó
äóã E ìíîæåñòâî îòìå÷åííûõ ïåòåëü E s s s V p b R s bb t� � � � �{ }( , ) / ( ), ( ), � , ÷òîáû
ïîëó÷èòü ãðàô G p� ( ) :
G p V p E E� � � � �( ) ( ( ), , )� ,
� �� �(( , )) (( , ))s r s r , åñëè ( , )s r E� , � �� (( , ) )s s bb .
Òîãäà A p M V p q e F p( ) ( , ( ), , , )� � �� 0 { } , ãäå � îïðåäåëÿåòñÿ äèàãðàììîé ïåðå-
õîäîâ G p s a s a� �( ) : ( , ) [ ]� , åñëè a R st� ( ), è � ( , )s a s� , åñëè a R st� ( ) . Èç
óòâåðæäåíèÿ 1.1 çàêëþ÷àåì, ÷òî àâòîìàò A p( ) ðåøàåò íàñòîÿùóþ çàäà÷ó.
Çàìåòèì, ÷òî èç óòâåðæäåíèÿ 1.4 ñëåäóåò ÷òî äëÿ ëþáîãî s Pref p� ( ) ñïðàâåä-
ëèâî sab sba� , åñëè ( , )a b I� . Ñëåäîâàòåëüíî, A p( ) — M-àâòîìàò. Î÷åâèäíî, ÷òî
A p( ) ÿâëÿåòñÿ òàêæå àñèíõðîííûì àâòîìàòîì Çåëåíêè.
Óòâåðæäåíèå 3. Ñóùåñòâóåò online àëãîðèòì äëÿ ðåøåíèÿ çàäà÷è âõîæäåíèÿ
p t� ñî âðåìåííîé ñëîæíîñòüþ O m t( | | ) äëÿ ëþáûõ p t M D, ( , )� � , ïðåäñòàâëåí-
íûõ ñëîâàìè x p� è y t� . Ïðîñòðàíñòâåííàÿ ñëîæíîñòü — O m p( | | ) .
Àëãîðèòì 1 äëÿ çàäà÷è âõîæäåíèÿ
Øàã 1. Îáðàáîòêà òðåêà p : online ñêàíèðîâàíèåì ñòðîèòñÿ ïðîåêöèÿ � ( )p .
Ñîãëàñíî óòâåðæäåíèÿì 1.2 è 1.3 ýòîò øàã òðåáóåò âðåìåíè O p(| | ) . (Ïîñòðîåíèå
àâòîìàòà A p( ) íå òðåáóåòñÿ.)
Øàã 2. Îáðàáîòêà òðåêà t — ìîäåëèðîâàíèå ðàáîòû àâòîìàòà A p( ) íà ñëî-
âå y . Ñêàíèðóÿ online ñëîâî y t� , àëãîðèòì ïðîõîäèò ïóòü íà ãðàôå G p� ( ) ñëåäóþ-
ùèì îáðàçîì.
Íà÷èíàÿ ñ ñîñòîÿíèÿ e � �( , , )0 0 , åñëè ñîñòîÿíèå s k k G pm� � � �( , , ) ( )1 äîñ-
òèãíóòî è òåêóùàÿ áóêâà y åñòü a , òî èìåþòñÿ ñëåäóþùèå âîçìîæíîñòè:
1) s p� , òîãäà ÂÛÕÎÄ: p t� ;
2) a åñòü ïîñëåäíÿÿ áóêâà ñëîâà y è s a p[ ] � , òîãäà ÂÛÕÎÄ: p t� ;
3) a R sp� ( ) ; òîãäà ïåðåõîä ê ñëåäóþùåìó ñîñòîÿíèþ r s a� [ ] ;
4) a R sp� ( ) ; òîãäà ñëåäóþùåå ñîñòîÿíèå îñòàåòñÿ ïðåæíèì s .
Êîíåö àëãîðèòìà 1.
Ýòîò àëãîðèòì èñïîëüçóåòñÿ äàëåå äëÿ ïîñëåäóþùèõ àëãîðèòìîâ â ðàçä. 3, 4.
Óòâåðæäåíèå 4. Ïóñòü p t M D, ( , )� � .
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
4.1. p t� òîãäà è òîëüêî òîãäà, êîãäà ãðàô çàâèñèìîñòè òðåêà-îáðàçöà Gp åñòü
ïîäãðàô ãðàôà çàâèñèìîñòè òðåêà-îáúåêòà Gt .
4.2. p t� òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî ñëîâà y t� ñóùåñòâóåò ñëîâî
x p� òàêîå, ÷òî x åñòü ïîäïîñëåäîâàòåëüíîñòü ñëîâà y .
Äîêàçàòåëüñòâî. ßñíî, ÷òî 4.2 ñëåäóåò èç 4.1. Äîêàçàòåëüñòâî âûòåêàåò èç
îïðåäåëåíèé.
Çàìå÷àíèå. Èç ñïðàâåäëèâîñòè p t� íå ñëåäóåò, ÷òî äëÿ êàæäîãî ñëîâà x p�
ñóùåñòâóåò ñëîâî y t� òàêîå, ÷òî x — ïîäïîñëåäîâàòåëüíîñòü y . Ýòî âèäíî èç ñëå-
äóþùåãî ïðèìåðà.
Ïðèìåð. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � � { }a b c, , , D a b b c� { }( , ), ( , ) .
Ïóñòü t abc� [ ] . Òðåê t ñîñòîèò èç åäèíñòâåííîãî ñëîâà y abc� . Åñëè ïîëîæèòü
p ac� [ ] , òî ca p� , îäíàêî ca íå ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñëîâà y .
Ïóñòü s t M D, ( , )� � . Èç óòâåðæäåíèÿ 4.1 è îïðåäåëåíèÿ âõîæäåíèÿ s t� òîãäà
è òîëüêî òîãäà, êîãäà äëÿ ëþáûõ ñëîâ x a a ss� � �1 | | , y b b tt� � �1 | | ñóùåñòâóåò
âëîæåíèå èíäåêñíûõ ìíîæåñòâ �x y s tX X, : � . Çäåñü X ss � �{ }1, , | | ,
X tt � �{ }1, , | | òàêîå, ÷òî
1) �x y, ñîõðàíÿåò ìåòêó: a b ii x y
� �( , )
( ) ;
2) �x y, ñîõðàíÿåò ïîðÿäîê Gp : åñëè i jGp
è ( , )a a Di j � , òo
� �x y x yi j, ,( ) ( )
. (3)
Òàêèå âëîæåíèÿ íàçûâàåì êîððåêòíûìè.
Ïóñòü X — ïðîèçâîëüíîå ïîäìíîæåñòâî X t . Îáîçíà÷èì X k l X k l� � �
{ / : ,
è ( , )y y Dk l
� } .
Óòâåðæäåíèå 5. Ïóñòü s t M D, ( , )� � , x a a ss� � �1 | | , y b b tt� � �1 | | . Åñëè
s t� , a �� , òî s a t[ ] � òîãäà è òîëüêî òîãäà, êîãäà
� �i t b ai0 0
| | : , i X Xxy s xy s0 � �� �( ) ( ) . (4)
Äîêàçàòåëüñòâî. Äîïóñòèì, s a t[ ] � . Ñîãëàñíî äîïóùåíèþ äëÿ ëþáîãî ñëîâà
x a a aa a s aa
j j s� � � ��1 1 | | [ ] , ãäå ïîñëåäíåå âõîæäåíèå áóêâû a âûäåëåíî è äëÿ
ñëîâà y b b tt� � �1 | | ñóùåñòâóåò êîððåêòíîå âëîæåíèå �
x y x ta aX X
,
: � , ãäå
X s
xa � � �{ }1 1, , | | . Âû÷åðêíåì ñèìâîë a èç ñëîâà xa . Î÷åâèäíî ðåçóëüòèðóþùåå
ñëîâî x a a a a sj j s� � � �� �1 1 1| | è, ñëåäîâàòåëüíî, âëîæåíèå �x y s yX X, : � , ãäå
� �x y x y
i ia, ,
( ) ( )� , åñëè i j , è � �x y x y
i ia, ,
( ) ( )� � 1 , åñëè i j� , êîððåêòíî.
Ïîëîæèì i j
x ya0 1� ��
,
( ) . Äîïóñòèì i X Xx y s x y s0 � �� �, ,( ) ( ) . Òîãäà (3)
íàðóøåíî. Îòñþäà ñëåäóåò êîððåêòíîñòü (4).
Òåïåðü äîïóñòèì, ÷òî (4) âåðíî. Òîãäà ïîñòðîèì �
x ya ñëåäóþùèì îáðàçîì:
� �
x y x ya i i( ) ( ),� , åñëè i i
0 ,
�
x ya i i( ) � 0 , åñëè i i� 0 ,
� �
x y x ya i i( ) ( ),� �1 , åñëè i i� 0 .
Îòñþäà ñëåäóåò, ÷òî s a t[ ] � .
Àëãîðèòì 2 äëÿ çàäà÷è âõîæäåíèÿ. Ñîãëàñíî óòâåðæäåíèþ 5 àëãîðèòì ñêà-
íèðóåò ñëîâî x a a p� �1 | | , ÷èòàÿ êàæäûé ñèìâîë îäèí ðàç è ïðåîáðàçóåò ñëîâî y â
ïîñëåäîâàòåëüíîñòü ñëîâ y y y y p� � �, , , | |1 . Íà i-ì øàãå (i p� �1 2, , , | |), êîãäà ÷è-
òàåòñÿ ai , ñëîâî yi�1 ïðåîáðàçóåòñÿ ñëåäóþùèì îáðàçîì: åñëè y b bi n� � �1 1 ,
òî ñëåäóþùåå ñëîâî y b bi n� � � �1 ïîëó÷àåòñÿ èç yi�1 óäàëåíèåì áóêâ ìíîæåñòâà
{ / ( , ) }b b b Dj j i0
� , 1 0 j i , ãäå bi0
— ïåðâîå âõîæäåíèå áóêâû ai â ñëîâo yi�1 ,
ò.å. a bi i�
0
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 35
Âðåìåíí�ÿ ñëîæíîñòü àëãîðèòìà — O p t(| | | | ) , ïðîñòðàíñòâåííàÿ —
O t p(| | | | )� .
Óòâåðæäåíèå 6. Äëÿ ëþáîãî òðåêà t M D� ( , )� ñóùåñòâóåò äåòåðìèíèðîâàí-
íûé àñèíõðîííûé àâòîìàò Çåëåíêè B t( ) , êîòîðûé ðàñïîçíàåò p M D� ( , )� òîãäà è
òîëüêî òîãäà, êîãäà p t� .
Äîêàçàòåëüñòâî. Äëÿ ïîñòðîåíèÿ M-àâòîìàòà B t( ) ðàññìîòðèì ãðàô çàâèñè-
ìîñòè G V Et t t t� ( , , )� è ìíîæåñòâî âñåõ ïîäìíîæåñòâ ìíîæåñòâà Vt :
W V V Vt t� � � �{ }/ . Êàæäîå ïîäìíîæåñòâî ïðåäñòàâëÿåò òðåê, âõîäÿùèé â t .
Ïóñòü M-àâòîìàò B t M W q Ft( ) ( , , , , )� � 0 , ãäå q Vt0 � , F Wt� , ôóíêöèÿ ïåðå-
õîäîâ îïðåäåëÿåòñÿ â ñîîòâåòñòâèè ñ óòâåðæäåíèåì 5 ñëåäóþùèì îáðàçîì: åñëè ñó-
ùåñòâóåò v V� � òàêîå, ÷òî � ( )v a� , è åñëè v v v aGt
�
� � �� ( ) , òî
� � �( , ) \ , ( ( ), ( )) }V a V v v v v DGt
� � � � � �{ .
Çäåñü G îçíà÷àåò îòíîøåíèå ïðåäøåñòâîâàíèÿ â Gt . Èç óòâåðæäåíèÿ 5 çà-
êëþ÷àåì, ÷òî B t( ) ðåøàåò ïîñòàâëåííóþ çàäà÷ó.
Î÷åâèäíî, ÷òî äëÿ ëþáîãî V V a b V b a� � � �: ( , [ ][ ]) ( , [ ][ ])� � , ò.å. B t( ) åñòü M-àâ-
òîìàò. Ïî òåîðåìå Çåëåíêè ñóùåñòâóåò ñèíõðîííûé àâòîìàò, ðàñïîçíàþùèé p t� .
ÏÎÄÑ×ÅÒ w-ÒÐÅÊÎÂÛÕ ÎÊÎÍ, ÑÎÄÅÐÆÀÙÈÕ ÎÁÐÀÇÅÖ
Çàäà÷à. Äàíû äâà òðåêà: p t M D, ( , )� � , ïðåäñòàâëåííûõ ñëîâàìè x p� è y t� .
Òðåáóåòñÿ ïîäñ÷èòàòü êîëè÷åñòâî w-òðåêîâûõ îêîí, ñîäåðæàùèõ òðåê-îáðàçåö p .
Îïðåäåëåíèå 2. Ïóñòü ñëîâî y b bn� � �1 �
* . Òîãäà w-îêíî ðàçìåðà w íà ñëî-
âå y åñòü ïîäñëîâî b bi i w� �1 ... äëèíû w . Òðåê [ ... ]b bi i w� �1 íàçûâàåòñÿ w-òðåêîâûì
îêíîì ðàçìåðà w íà ñëîâå y . Î÷åâèäíî, ÷òî ÷èñëî w-îêîí, ñîäåðæàùèõ p , ìîæåò
áûòü ðàçëè÷íûì äëÿ ñëîâ y y t, � � , åñëè y y� � .
Øòàìïîâàííûé ïðåôèêñ òðåêà p M D� ( , )� åñòü óïîðÿäî÷åííàÿ ïàðà ( , )r n ,
ãäå r Pref p� ( ) , n N� . Êîíôèãóðàöèÿ åñòü ïîñëåäîâàòåëüíîñòü øòàìïîâàííûõ
ïðåôèêñîâ äàííîãî òðåêà.
Óòâåðæäåíèå 7. Ñóùåñòâóåò àëãîðèòì ïîäñ÷åòà êîëè÷åñòâà w-òðåêîâûõ îêîí
ñëîâà y t� , ñîäåðæàùèõ òðåê p . Âðåìåííaÿ� ñëîæíîñòü àëãîðèòìà — O mw t( | | ) ,
ïðîñòðàíñòâåííàÿ — O w p(| | | | ) .
Èäåÿ àëãîðèòìà. Ñêàíèðóÿ y b bn� � �1 �
* , àëãîðèòì ñòðîèò êîíôèãóðàöèè
Ci äëÿ êàæäîé áóêâû bi ñëîâà y . Øòàìïîâàííûé ïðåôèêñ ( , )r u ( ( ))r Pref p� âõî-
äèò â êîíôèãóðàöèþ Ci òîãäà è òîëüêî òîãäà, êîãäà òðåêîâîå îêíî, ò.å. òðåê
[ ]b bi u i� � �1 äëèíû u w ñîäåðæèò ïðåôèêñ r . Ïî çàäàííûì Ci è bi�1 âîçìîæíî
ïîäñ÷èòàòü Ci�1 . Åñëè Ci ñîäåðæèò øòàìïîâàííûé ïðåôèêñ ( , )p u , ãäå u w , òî
w-òðåêîâîå îêíî [ ]b bi w i� � �1 ñîäåðæèò p .
Àëãîðèòì ïîäñ÷åòà w-òðåêîâûõ îêîí
Ïóñòü p t M D, ( , )� � .
ÂÕÎÄ — äâà ñëîâà: x p� , y t� .
ÂÛÕÎÄ — counter (÷èñëî w-òðåêîâûõ îêîí y , ñîäåðæàùèõ [ ]x )
Øàã 1. Ïðåäîáðàáîòêà p x� [ ] — âû÷èñëåíèå � ( )p .
Èíèöèàëèçàöèÿ: counter :� 0 ; C e0 0: (( , ))� .
Øàã 2. Îáðàáîòêà òðåêà t.
for i t� �1, , | |
do
a bi:� ; C ei : (( , ))� 0 (èíèöèàëèçàöèÿ è âû÷èñëåíèå Ci )
for all ( , )r u Ci� �1
do
if r a p[ ] � and u w� � 1 then counter counter:� � 1
(w-òðåêîâîå îêíî ñîäåðæèò p) end if;
if a R rp� ( ) , u w
� 1, then äîáàâèòü øòàìïîâàííûé
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
ïðåôèêñ ( [ ], )r a u � 1 ê Ci , ò.ê. y yi u i� � �1 ìîæåò áûòü
íà÷àëîì òðåáóåìîãî w-òðåêîâîãî îêíà è ïîäñëîâî
y yi u i� � �1 äîëæíî áûòü ïåðåäàíî â Ci�1 end if;
if a R rp� ( ) , u w
� 1 then äîáàâèòü ( , )r u � 1 ê Ci�1 ;
end do
end for all
if a R ep� ( ) then äîáàâèòü ( , )a 1 ê Ci
(ñîçäàòü íà÷àëî íîâîãî îêíà) end if
end do
end for.
ÂÛÕÎÄ: counter
Êîíåö àëãîðèòìà.
ÏÎÄÑ×ÅÒ ×ÈÑËÀ ÌÈÍÈÌÀËÜÍÛÕ ÔÀÊÒÎÐΠÎÁÚÅÊÒÀ, ÑÎÄÅÐÆÀÙÈÕ ÎÁÐÀÇÅÖ
Ïóñòü (1) è (2) âåðíû, ò.å. p t� . Ôàêòîð f p t t pn n� � �1 1 1 òðåêà t , ñîäåðæàùèé p ,
íàçûâàåòñÿ ìèíèìàëüíûì, åñëè êàæäûé ñîáñòâåííûé ôàêòîð òðåêà f íå ñîäåðæèò p .
Çàäà÷à. Äàíû äâà òðåêà: p t M D, ( , )� � , ïðåäñòàâëåííûõ ñëîâàìè x p� è
y t� . Ïîäñ÷èòàòü ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ òðåêà t , ñîäåðæàùèõ òðåê p .
Óòâåðæäåíèå 8. Ñóùåñòâóåò àëãîðèòì ïîäñ÷åòà ÷èñëà ìèíèìàëüíûõ ôàêòîðîâ
òðåêà t , ñîäåðæàùèõ òðåê p . Âðåìåíía'ÿ ñëîæíîñòü àëãîðèòìà åñòü O m t( | | )2 , ïðî-
ñòðàíñòâåííàÿ ñëîæíîñòü — O m t( | | ) .
Èäåÿ àëãîðèòìà. Ïóñòü t qrs� è q r s p M D, , , ( , )� � è r — ìèíèìàëüíûé ôàê-
òîð òðåêà-îáúåêòà t , ñîäåðæàùèé òðåê-îáðàçåö p . Òîãäà äëÿ êàæäîãî ñëîâà
y b b tt� � �1 | | ñóùåñòâóåò òðåêîâîå îêíî (áåç îãðàíè÷åíèÿ íà äëèíó) [ ]b bk i� òà-
êîå, ÷òî p r b bk i� � �[ ] .
Î÷åâèäíî, ÷òî ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ òðåêà t , åñëè t y� [ ] , ðàâíî ÷èñëó
òàêèõ ïîäñëîâ ñëîâà y , ñîáñòâåííûå òðåê-ïîäñëîâà êîòîðûõ íå ñîäåðæàò p . Òàêèì îá-
ðàçîì, íóæíî íàéòè è ïîäñ÷èòàòü êîëè÷åñòâî òàêèõ ìèíèìàëüíûõ ïîäñëîâ. Ñêàíèðóÿ
ñëîâî y , àëãîðèòì àññîöèèðóåò ñ êàæäîé áóêâîé bi ñëîâà y êîíôèãóðàöèþ
C r ri l� �( , , )1 , r Pref pk � ( ) , k l� �1, , , ò.å. ïîñëåäîâàòåëüíîñòü ïðåôèêñîâ
p M D� ( , )� (íå øòàìïîâàííûõ, êàê â ïðåäûäóùåé ñåêöèè) òàêèõ, ÷òî r b bk v ik
� �[ ]
è v v il1
�
. Äîïóñòèì, ÷òî äëÿ íåêîòîðîãî j l� �{ }1, , ñïðàâåäëèâî
p r p r p r p rj j l� � � �� � ���1 1, , , , , 1 j l . (5)
Òîãäà âñå [ ]b bv ik
� äëÿ k j ñîäåðæàò îäèíàêîâûé ìèíèìàëüíûé òðåê-ôàêòîð
òðåêà t , òðåê-ôàêòîð y , ñîäåðæàùèé ìèíèìàëüíûé òðåê-ôàêòîð t íàéäåí è ñ÷åò-
÷èê äîëæåí áûòü óâåëè÷åí íà 1. Ïðè ýòîì âîçìîæíî ðàññìàòðèâàòü òîëüêî òðå-
êîâûå îêíà ñ [ ]b bk l� ñ b R ek p� ( ) .
Êîíôèãóðàöèÿ Ci�1 äëÿ j , óäîâëåòâîðÿþùàÿ (5), ñòðîèòñÿ ñëåäóþùèì
îáðàçîì:
If C r ri l� �( , , )1 and b ai� �1 , put s r ak j k� � [ ] if s r a Pref pk j k� �� [ ] ( ) and
s rk j k� � if r a Pref pj k� �[ ] ( ) for k l j� � �1, , . Then
C s si i j� �� �1 1( , , ) if a R ep� ( ) , j l
,
C s s ai i j� �� �1 1( , , , [ ]) if a R ep� ( ) , j l
,
C ei� �1 { } if j l� , a R ep� ( ) ,
C ai� �1 { }[ ] if j l� , a R ep� ( ) ,
ãäå e — ïóñòîé òðåê.
Ñêàíèðóÿ ñëîâî y, ìîæíî ïîäñ÷èòàòü ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 37
Çàìå÷àíèå. Àëãîðèòì ïîäñ÷èòûâàåò òîëüêî ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ, íî
íå ñàìè ìèíèìàëüíûå ôàêòîðû. Äëÿ òîãî ÷òîáû ïîëó÷èòü ìèíèìàëüíûå ôàêòîðû t ,
íåîáõîäèìî äîïîëíèòü àëãîðèòì ïðîöåäóðîé óäàëåíèÿ èç ìèíèìàëüíûõ ïîäñëîâ
ëèøíèõ áóêâ. Ýòî óâåëè÷èò ñëîæíîñòü äî O m t( | | )3 .
Àëãîðèòì âû÷èñëåíèÿ ìèíèìàëüíûõ ôàêòîðîâ
ÂÕÎÄ: äâà ñëîâà: x p� , y t� .
ÂÛÕÎÄ: counter — ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ òðåêà t , ñîäåðæàùèõ
òðåê p .
Øàã 1. Ïðåäîáðàáîòêà [ ]x : âû÷èñëåíèå � ( )p .
Øàã 2. Èíèöèàëèçàöèÿ C e0 � ( ) ; counter:� 0 ;
for i t� �1, , | | (äëÿ êàæäîé áóêâû ñëîâà y b b t� �1 | | —
ïîñòðîåíèå Ci�1 .)
� :� 0 ; Ci� � �1 : ; a bi:� �1 ; (èíèöèàëèçàöèÿ)
for all s Ci�
do
if p s a� [ ] then � :� 1 (ìèíèìàëüíûé ôàêòîð íàéäåí) else
if s a Pref p[ ] ( )� then add s a[ ] to Ci�1 else add s to Ci�1 end
if end if
end do
end for all
if a R ep� ( ) then add [ ]a to Ci�1
else if Ci� � �1 then add e to Ci�1 end if end if
counter counter:� � �
end for
Êîíåö àëãîðèòìà.
Ñëîæíîñòü: ÷èñëî ïðåôèêñîâ â Ci îãðàíè÷åíî | |t -äëèíîé ñëîâà y . Ñëåäîâà-
òåëüíî, ñëîæíîñòü àëãîðèòìà O m t( | | )2 .
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå ïðèâîäÿòñÿ àëãîðèòìû ðåøåíèÿ ñëåäóþùèõ çàäà÷: ðåøèòü,
âõîäèò ëè p M D� ( , )� â t M D� ( , )� ; ïîäñ÷èòàòü ÷èñëî w-òðåêîâûõ îêîí y t� ,
êîòîðûå ñîäåðæàò îáðàçåö p ; ïîäñ÷èòàòü ÷èñëî ìèíèìàëüíûõ ôàêòîðîâ òðåêà t ,
êîòîðûå ñîäåðæàò îáðàçåö p .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. C h i Y . , W a n g H . , Y u P . S . , M u n t z R . R . Catch the moment: maintaining closed frequent itemsets
over a date stream sliding window // Knowledge and Inform. Systems. — 2006. — 10, N 3. — P. 265–294.
2. L i H - F . , S h a n M - K . , L e e S - Y . DSM-FI: an efficient algorithm for mining frequent itemsets in data
streams // Ibid. — 2008. — 17, N 1.
3. B a C . , F e r r a r i M . H . , M u s i c a n t e M . A . Composing Web Services with PEWS : a trace-theoretical
approach // 4-th Europ. Conf. on WEB Services. — 2006.
4. M a n n i l a H . , T o i v o n e n H . , V e r k a m o A . Discovering Frequent Episodes in Sequences // Proc.
KDD Conf.— 1955.
5. A v e l l o n e A . , G o l d w u r m M . Analysis of algorithms for the recgnition of rational ànd context-free
trace languages // Theoretical Inform. and Appl. — 1998. — 32. — P. 141–152.
6. C h i Y . , M u n t z R . , N i j s s e n S . , K o k J . Frequent Subtree Mining. — An Overview // Fundamentà
Inform. — 2001. — 21. — P. 161–198.
7. C r o c h e m o r e M . , I l i e L . Maximal repetitions in strings // J. of Comput. and System. Scie. — 2008. —
74. — P. 796–807.
8. B o a s s o n L . , C e g i e l s k i P . , G u e s s a r i a n I . , M a t i y a s e v i c h Y . Window-Accumulated
Subsequence Problem is linear // Annals of Pure and Appl. Logic. — 2001. — 113. — P. 74–87.
9. C e g i e l s k i P . , G u e s s a r i a n I . , M a t i y a s e v i c h Y . Tree Inclusion Problems // RAIRO — Theoreti-
cal Inform. and Appl. — 2008. — 42. — P. 5–20.
10. G u e s s a r i a n I . , C e g i e l s k i P . Tree Inclusions in Windows and Slices // CSIT Conf. — 2000.
11. M e s s n e r J . Pattern Matching in Trace Monoids // Symposium on Theoretical Aspects of Comput. Scie. — 1997.
12. D i k e r t V . , R o z e n b e r g G . The Book of Traces // Handbook of formal languages. — N.Y.:
Springer-Verlag, 1997. — 568 p.
13. L e t i c h e v s k y A . A . On the equivalence of automata over semigroup // Theoretic Cybernetics. — 1970.
— 6. — P. 3–71 (in Russian).
14. S h a k h b a z y a n K . V . , S h o u k o u r i a n Y u . H . On process languages in finite graphs //
J. of Mathemat. Scie. — 2000. — 101, 4. — P. 205–215.
Ïîñòóïèëà 19.05.2009
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
|