Изменения
Нет описания правки
=== Реализация ===
<tex>\mathtt{pushSetsToQueue}(S,\ R_1,\ R_2,\ c)</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>
'''return''' <tex>\mathtt{P}</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>
'''return''' <tex>\mathtt{P}</tex>
*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>,
*<tex>\mathtt{Queue}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>, где <tex>C</tex> {{---}} номер класса (сплиттера),
*<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма),
'''for''' <tex>c \in \Sigma</tex>
'''push''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex>
'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{Queue}</tex>
'''remove''' <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex>
'''add''' <tex>r</tex> '''to''' <tex>\mathtt{P}[\mathtt{Twin}[i]]</tex>
<tex>\mathtt{Class}[r] = \mathtt{Twin}[i]</tex>
'''for''' <tex> j \in \mathtt{Involved}</tex>
'''if''' <tex> \mathtt{Twin}[j] \neq 0 </tex>
<tex>\mathtt{Count}[j] = 0</tex>
<tex>\mathtt{Twin}[j] = 0</tex>
'''return''' <tex>\mathtt{P}</tex>
Осталось только реализовать <tex>\mathtt{pushSetsToQueue}</tex>.
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>:
<tex>cnt1 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_1]</tex>
<tex>cnt2 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_2]</tex> '''if''' <tex> cnt1 \leqslant cnt2 </tex> <tex> \mathtt{InQueueswapClasses}[(R_1][c] == ,\ R_2)</tex> ''false'' '''andfor''' <tex> cnt1 c \in \leqslant cnt2 Sigma</tex> '''push''' <tex>\langle R_1R_2, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex> <tex>\mathtt{InQueueswapClasses}(i,\ j)</tex>: <tex>\mathtt{swap}(\mathtt{P}[R_1i],\ \mathtt{P}[cj] )</tex> <font color=darkgreen>//Поменять друг с другом содержимое индексов <tex>i,\ j</tex> в <tex>\leftarrow \ mathtt{P}</tex> </font> ''true'for' '' <tex>r</tex> '''elsein'''<tex>\mathtt{P}[i]</tex> <tex>\mathtt{Class}[r] = j</tex> '''pushfor''' <tex>\langle R_2, c \rangler</tex> '''toin''' <tex>\mathtt{QueueP}[j]</tex> <tex>\mathtt{InQueueClass}[r] = i</tex> Стоит пояснить, зачем требуется менять содержимое множеств (<tex>\mathtt{swapClasses}(R_1,\ R_2)</tex>). Почему нельзя просто проверить <tex> cnt1 \leqslant cnt2 </tex>, и на основе этого добавить либо первое, либо второе? Ответ кроется в том, что де-факто мы создаем только один новый класс, старый класс (<tex>R_1</tex>) мы только меняем в размерах. Потому если <tex>\langle R_1, c \rangle</tex> уже есть в очереди, у нас не остается иного выбора, кроме как добавить <tex>\langle R_2, c \rangle</tex>. Однако, может случится, что <tex>|R_2][| > |R_1| </tex>, что как раз и может потенциально дать квадратичную ассимптотику (логарифмическая достигается как раз за счет того, что добавляемый в очередь подкласс - меньший). Причем, стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle R_1, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>\langle R_2, c] \ rangle</tex>. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\leftarrow langle R_2, c \ rangle</tex> ''true''.
===Время работы===
=== Альтернативная реализация ===
Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее).
Все классы разбиения будем по-прежнему хранить в векторе хэш-сетов <tex>\mathtt{P}</tex>.
*<tex>\mathtt{Class}[r]</tex> {{---}} индекс класса в <tex>\mathtt{P}</tex>, которому принадлежит состояние <tex>r</tex>,
*<tex>\mathtt{Queue}</tex> {{---}} множество очередь из пар <tex>\langle C,\ a \rangle</tex>,
*<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма),
*<tex>\mathtt{Involved}</tex> {{---}} ассоциативный массив из номеров классов в векторы из номеров вершин.
'''remove''' <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex>
'''add''' <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex>
'''remove''' <tex>\langle C,\ a \rangle</tex> '''from''' <tex> \mathtt{Queue}</tex>
'''return''' <tex>\mathtt{P}</tex>
=== Сравнение с алгоритмом из оригинальной статьи Хопкрофта ===
<tex>\mathtt{pushSetsToQueue}</tex> реализуем так:
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>: <tex>cnt1 \leftarrow \mathtt{ClassInv}[R_1][c]</tex> <tex>cnt2 \leftarrow \mathtt{ClassInv}[R_2][c]</tex> <font color=darkgreen>//Рассмотреть случаи, <tex> cnt1 == 0 </tex>, <tex> cnt2 == 0 </tex></font> '''if''' <tex> \mathtt{InQueue}[R_1][c] ==</tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex> '''push''' <tex>\langle mathtt{swapClasses}(R_1, c \rangle</tex> '''to''' <tex>\mathtt{Queue}R_2)</tex> '''insertfor''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_1]in \Sigma</tex> '''else''' '''push''' <tex>\langle R_2, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex> '''insert''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_2]</tex>
Циклы
