Изменения

Перейти к: навигация, поиск
sta
=== Реализация ===
<tex>\mathtt{pushSetsToQueue}(S,\ R_1,\ R_2)</tex> {{---}} функция, которая добавляет пары <tex>\langle R_1, \forall c \in \Sigma \rangle</tex>, <tex>\langle R_2, \forall c \in \Sigma \rangle</tex> в очередь S.
*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА,
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
'''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
<tex>\mathtt{pushSetsToQueue}(S,\ R,\ R_1,\ R_2)</tex>
'''return''' <tex>\mathtt{P}</tex>
 
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R,\ R_1,\ R_2)</tex>:
<tex>\mathrm{cnt1} \leftarrow |\mathtt{P}[R_1]|</tex>
<tex>\mathrm{cnt2} \leftarrow |\mathtt{P}[R_2]|</tex>
'''for''' <tex>c \in \Sigma</tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex>
'''remove''' <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex>
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''if''' <tex> |\mathrmmathtt{cnt1P} [R_1]| \leqslant |\mathrmmathtt{cnt2P} [R_2]| </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''return''' <tex>\mathtt{P}</tex>
 
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</tex>).
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
'''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{pushSetsToQueueS}(</tex> '''remove''' <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex> '''push''' <tex>\langle R_1,c \rangle</tex> '''into''' <tex>\ Rmathtt{S}</tex> '''push''' <tex>\langle R_2,c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''else''' '''if''' <tex> |\mathtt{P}[R_1]| \leqslant |\mathtt{P}[R_2]| </tex> '''push''' <tex>\ langle R_1,c \ rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''else''' '''push''' <tex>\langle R_2), c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''return''' <tex>\mathtt{P}</tex>
*<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>,
*<tex>\mathtt{Count}</tex> {{---}} целочисленный массив, где <tex>\mathtt{Count}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>,
*<tex>\mathtt{Reversed}</tex> {{---}} массив булеан, <tex>\mathtt{Reversed}[i] == </tex> ''true'', если требуется добавлять состояния из <tex>\mathtt{Inverse}</tex> в исходный класс <tex>i</tex>, а не в новый класс (<tex>\mathtt{Twin}[i]</tex>),*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.,*<tex>\mathtt{Used}</tex> {{---}} массив булеан, <tex>\mathtt{Used}[r] == </tex> ''true'', если состояние <tex>r</tex> попало в <tex>\mathtt{Inverse}</tex>
<tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:
'''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex>
<tex>\mathtt{Count}[i]++</tex>
<tex>\mathtt{Used}[r] = </tex> ''true''
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{Count}[i] <</tex> <tex>|\mathtt{P}[i]|</tex>
'''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>//Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font>
<tex>\mathtt{Twin[i]} = |\mathtt{P}|</tex> <font color=darkgreen>//Запишем в <tex>\mathtt{Twin[i]}</tex> индекс нового класса</font>
'''if''' <tex>\mathtt{Count}[i] > |\mathtt{P}[i]|/2</tex>
<tex>\mathtt{Reversed}[i] = </tex> ''true''
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{Twin}[i] \neq 0</tex>
'''removeif''' <tex>\lnot \mathtt{Reversed}[i]</tex> <tex>\mathtt{move}(r,\ i,\ \mathtt{Twin}[i])</tex> <tex>\mathtt{Used}[r] = </tex> ''false'from' '''for''' <tex> i \in \mathtt{Involved}</tex> '''if''' <tex>\mathtt{PTwin}[i]\neq 0 </tex> '''addif''' <tex>r\mathtt{Reversed}[i]</tex> '''tofor''' <tex>r \in \mathtt{P}[i] </tex> '''if''' <tex>\lnot \mathtt{TwinUsed}[i]r]</tex> <tex>\mathtt{Classmove}[(r] = ,\ i,\ \mathtt{Twin}[i])</tex> <tex>\mathtt{Used}[r] = </tex>''false'' '''for''' <tex> j c \in \mathtt{Involved}Sigma</tex> '''ifpush''' <tex> \langle \mathtt{Twin}[ji] , c \neq 0 rangle</tex> '''to''' <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ j,\ </tex> <tex>\mathtt{TwinCount}[ji])= 0</tex> <tex>\mathtt{CountReversed}[ji] = 0</tex>''false'' <tex>\mathtt{Twin}[ji] = 0</tex>
'''return''' <tex>\mathtt{P}</tex>
Стоит отметить, что массивы <tex>\mathtt{Count}, \mathtt{Twin}</tex> аллоцируются ровно один раз при инициализации алгоритма. Осталось только реализовать <tex>\mathtt{pushSetsToQueue}</tex>.   <tex>\mathtt{pushSetsToQueuemove}(\mathtt{Queue},\ R_1,\ R_2)</tex>: <tex>\mathrm{cnt1} \leftarrow |\mathtt{P}[R_1]|</tex> <tex>\mathrm{cnt2} \leftarrow |\mathtt{P}[R_2]|</tex> '''if''' <tex> \mathrm{cnt1} \leqslant \mathrm{cnt2} </tex> <tex>\mathtt{swapClasses}(R_1,\ R_2)</tex> '''for''' <tex>c \in \Sigma</tex> '''push''' <tex>\langle R_2r, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>  <tex>\mathtt{swapClasses}(i,\ j)</tex>: <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>//Поменять друг с другом содержимое индексов <tex>i,\ j</tex> в <tex>\mathtt{P}</tex></font> '''forremove''' <tex>r</tex> '''infrom''' <tex>\mathtt{P}[i]</tex> <tex>\mathtt{Class}[r] = j</tex> '''foradd''' <tex>r</tex> '''into''' <tex>\mathtt{P}[j]</tex> <tex>\mathtt{Class}[r] = ij</tex>
Стоит пояснитьотметить, зачем требуется менять содержимое множеств (что массивы <tex>\mathtt{swapClassesCount}(R_1,\ R_2)</tex>). Почему нельзя просто проверить <tex> \mathrmmathtt{cnt1Twin} ,\leqslant \mathrmmathtt{cnt2Used} </tex>, и на основе этого добавить либо первое, либо второе? Ответ кроется в том, что де-факто мы создаем только один новый класс, старый класс (<tex>R_1</tex>) мы только меняем в размерах. Потому если <tex>\langle R_1, c \ranglemathtt{Reversed}</tex> уже есть в очереди, у нас не остается иного выбора, кроме как добавить <tex>\langle R_2, c \rangle</tex>. Однако, может случится, что <tex>|R_2| > |R_1| </tex>, что как аллоцируются ровно один раз и может потенциально дать квадратичную ассимптотику (логарифмическая достигается как раз за счет того, что добавляемый в очередь подкласс - меньший)при инициализации алгоритма.
ПричемКогда мы вычислили массив <tex>\mathtt{Count}</tex>, стоит отметитьмы смотрим, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого какая часть класса <tex>ci</tex> пара больше и помечаем (<tex>\langle R_1mathtt{Reversed}[i] = </tex> ''true''), c когда больше часть, состоящая из состояний множества <tex>\ranglemathtt{Inverse}</tex> уже была в очереди. Далее, смотря на эту пометку, то мы добавим её "вторую половинку" заполняем класс <tex>\langle R_2, c mathtt{Twin}</tex> либо состояниями из <tex>\ranglemathtt{Inverse}</tex>, либо всеми остальными. Если её в очереди не было, то мы вольны сами выбиратьБлагодаря такой стратегии, какой подкласс добавлять в очередь, и таким образом добавляем опять же новом классе <tex>\langle R_2mathtt{Twin}[i]</tex> будет гарантировано меньше вершин, c \rangleчем в <tex>i</tex>. Пары с этим подклассом потому и следует добавлять в очередь.
И еще одна детальПричем, стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>\mathtt{swapClasses}(R_1,\ R_2)c</tex> вызывается только в том случае, когда пара <tex> \mathrm{cnt1} langle i, c \leqslant \mathrm{cnt2} rangle</tex>уже была в очереди, из чего следует то мы добавим её "вторую половинку" <tex>\mathrm{cnt1} + \mathrm{cnt2} <= 2 \cdot |langle \mathtt{InverseTwin}| </tex>[i], т.к. <tex>c \mathrm{cnt2} = |\mathtt{Inverse}|rangle</tex>. Таким Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом, вызов добавляем опять же <tex>\langle \mathtt{swapClassesTwin}(R_1[i],c \ R_2)rangle</tex> не ухудшает ассимптотику.
===Время работы===
<tex>j = |\mathtt{P}|</tex> <font color=darkgreen>//Запишем в <tex>j</tex> индекс нового класса</font>
'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>
'''removeif''' <tex>r|\mathtt{Involved}[i]| \leqslant |\mathtt{P}[i]|/2</tex> '''from''' <tex>\mathtt{Pmove}[(r,\ i],\ j)</tex> '''addelse''' <tex>\mathtt{move}(r,\ j,\ i)</tex> '''tofor''' <tex>c \mathtt{P}[j]in \Sigma</tex> '''push''' <tex>\mathtt{Class}[r] = langle j, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ i,\ j)</tex>
'''remove''' <tex>\langle C,\ a \rangle</tex> '''from''' <tex> \mathtt{Queue}</tex>
'''return''' <tex>\mathtt{P}</tex>
=== Сравнение с алгоритмом из оригинальной статьи Хопкрофта === В оригинальной статье <ref>[http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf ''John Hopcroft'' An O(nlogn) algorithm for minimizing states in a finite automation]</ref> использовалась дополнительная структура, которую мы обозначим, как <tex>\mathtt{ClassInv}</tex>, в <tex>\mathtt{ClassInvmove}[C][a]</tex> будем хранить множество состояний, из которых есть ребро по символу <tex>a</tex> в состояние <tex>C</tex> (аналогично <tex>Inv</tex>r, только для классов). <tex>\mathtt{ClassInv}[C][a] = \{ s\ |\ \mathtt{Class}[s] == C \ \land \ \delta^{-1} (s, a) \neq \emptyset \}</tex> <tex>\mathtt{pushSetsToQueue}</tex> реализуем так:  <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue}i,\ R_1,\ R_2j)</tex>: <tex>\mathrm{cnt1} \leftarrow \mathtt{ClassInv}[R_1][c]</tex> <tex>\mathrm{cnt2} \leftarrow \mathtt{ClassInv}[R_2][c]</tex> '''ifremove''' <tex> \mathrm{cnt1} \leqslant \mathrm{cnt2} </tex> <tex>\mathtt{swapClasses}(R_1,\ R_2)</tex> '''for''' <tex>c \in \Sigma</tex> '''push''' <tex>\langle R_2, c \rangler</tex> '''tofrom''' <tex>\mathtt{Queue}</tex> Циклы  '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{InvP}[q][ai]</tex> (...) реализуются так:  '''foradd''' <tex>q \in \mathtt{ClassInv}[C][a]r</tex> '''andto''' <tex>r \in \mathtt{InvP}[q][aj]</tex> (...) Тогда время работы внутреннего цикла можно будет оценить как <tex>O(|\mathtt{ClassInvClass}[Cr][a]| + |\mathtt{Inverse}|)</tex>. А реализация <tex>\mathtt{pushSetsToQueue}</tex> выбирает множество, на котором <tex>O(|\mathtt{ClassInv}[C][a]|)= j</tex> будет меньшим. Кроме того, вместо [[Хеш-таблица | хэш-таблиц]] для хранения множеств (<tex>\mathtt{ClassInv}</tex>, разбиение <tex>P</tex>) можно использовать комбинацию из двусвязного списка и вектора (добавление/удаление через список, поиск через вектор). Что и используется в оригинальной статье.
== См. также ==
19
правок

Навигация