Изменения
Нет описания правки
===Время работы===
Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex> {{---}} алфавит. Это следует из того, что если пара <tex>\langle C,\ a \rangle</tex> попала в очередь, и класс <tex>C</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>C_1</tex> и <tex>C_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|C| \ge geqslant |C_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку.
== Алгоритм Хопкрофта==
*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>
*<tex>\mathtt{Queue}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>, где <tex>C</tex> {{---}} номер класса (сплиттера)
*<tex>\mathtt{InQueue}</tex> {{---}} двумерный массив булеанов, <tex>\mathtt{InQueue}[C][a] == true</tex>''true'', если <tex>\langle C,\ a \rangle</tex> находится в очереди <tex>\mathtt{Queue}</tex>
*<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма)
Для обработки <tex>T'</tex> за <tex>O(|Q| + |\mathtt{Inverse}|)</tex> нам понадобится следующая структура:
*<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>;
*<tex>\mathtt{SizeCount}</tex> {{---}} целочисленный массив, где <tex>\mathtt{SizeCount}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>;
*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</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>
<tex>\mathtt{InQueue}[F][c] \ \leftarrow \ true</tex>''true'' <tex>\mathtt{InQueue}[Q \setminus F][c] \ \leftarrow \ true</tex>''true''
'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{Queue}</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{SizeCount}[i] == 0</tex>
'''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex>
<tex>\mathtt{SizeCount}[i]++</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{SizeCount}[i] < </tex> '''size of''' <tex>\mathtt{CardP}[i]</tex> '''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{SizeP}</tex> //Создадим пустой класс в разбиении <tex>\mathtt{P}</tex> <tex>\mathtt{Twin[i] } = -1</tex> '''size of''' <tex>\mathtt{P}</tex> //Пометим сразу, т.к. Запишем в следующем цикле классы уже будут менятся<tex>\mathtt{Twin[i]}</tex> индекс нового класса
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{SizeTwin}[i] == -1\neq 0</tex> '''ifremove''' <tex>\mathtt{Twin}[i] == 0r</tex> '''from''' <tex>\mathtt{CounterP}++</tex> <tex>\mathtt{Twin[i]} = \mathtt{Counter}</tex> '''moveadd''' <tex>r</tex> '''from''' <tex>i</tex> '''to''' <tex>\mathtt{TwinP}[i]</tex> '''in''' <tex>\mathtt{PTwin}[i]]</tex>
'''for''' <tex> j \in \mathtt{Involved}</tex>
'''if''' <tex> \mathtt{Twin}[j] \neq 0 </tex>
'''for''' <tex>c \in \Sigma</tex>
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ j,\ \mathtt{Twin}[j],\ c)</tex>
<tex>\mathtt{SizeCount}[j] = 0</tex>
<tex>\mathtt{Twin}[j] = 0</tex>
<tex>\mathtt{InQueue}[C][a] \ \leftarrow \ false</tex>''false''
'''return''' <tex>\mathtt{P}</tex>
Стоит отметить, что массивы <tex>\mathtt{SizeCount}, \mathtt{Twin}</tex> аллоцируются ровно один раз при инициализации алгоритма.
Осталось только реализовать <tex>\mathtt{pushSetsToQueue}</tex>.
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>:
<tex>cnt1 \leftarrow </tex> '''size of''' <tex>\mathtt{CardP}[R_1]</tex> <tex>cnt2 \leftarrow </tex> '''size of''' <tex>\mathtt{CardP}[R_2]</tex> '''if''' <tex> \mathtt{InQueue}[R_1][c] == false </tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
<tex>\mathtt{InQueue}[R_1][c] \ \leftarrow \ true</tex>''true''
'''else'''
'''push''' <tex>\langle R_2, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
<tex>\mathtt{InQueue}[R_2][c] \ \leftarrow \ true</tex>''true''
===Время работы===
Итого, получается, что время работы алгоритма Хопкрофта не превышает <tex> O(|\Sigma| |Q|) + O(|\Sigma| |Q|) + O(|\Sigma| |Q| \log_2(|Q|)) + O(|\Sigma| |Q|) = O(|\Sigma| |Q| \log_2(|Q|))</tex>.
}}
== Альтернативная реализация ==
Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее).
Заметим, что вообще нам не важен порядок доставания элементов из "очереди", потому вместо очереди <tex>\mathtt{Queue}</tex> и массива <tex>\mathtt{InQueue}</tex> можно обойтись одним множеством пар (оставим название <tex>\mathtt{Queue}</tex>).
*<tex>\mathtt{Class}[r]</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> {{---}} хэш-таблица из номеров классов в векторы из номеров вершин.
<tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:
<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>
'''for''' <tex>c \in \Sigma</tex>
'''insert''' <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> '''take any from''' <tex>\mathtt{Queue}</tex> //Взять любую пару из <tex>\mathtt{Queue}</tex>, не удаляя (!)
<tex>\mathtt{Involved} \leftarrow \varnothing</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{Involved}[i] == \varnothing</tex>
<tex>\mathtt{Involved}[i] = \{\}</tex>
'''add''' <tex>r</tex> '''to''' <tex>\mathtt{Involved}[i]</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex> //Перебираем ключи <tex>\mathtt{Involved}</tex>
'''if''' '''size of''' <tex>\mathtt{Involved}[i] <</tex> '''size of''' <tex>\mathtt{P}[i]</tex>
'''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> //Создадим пустой класс в разбиении <tex>\mathtt{P}</tex>
<tex>j = </tex> '''size of''' <tex>\mathtt{P}</tex> //Запишем в <tex>j</tex> индекс нового класса
'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>
'''remove''' <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex>
'''add''' <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex>
'''for''' <tex>c \in \Sigma</tex>
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ i,\ j,\ c)</tex>
'''remove''' <tex>\langle C,\ a \rangle</tex> '''from''' <tex> \mathtt{Queue}</tex>
'''return''' <tex>\mathtt{P}</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''' \lnot(<tex>\langle R_1, c \rangle</tex> '''in''' <tex>\mathtt{Queue}</tex>) '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''insert''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
'''else'''
'''insert''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
== Сравнение с алгоритмом из оригинальной статьи Хопкрофта ==
<tex>cnt1 \leftarrow \mathtt{ClassInv}[R_1][c]</tex>
<tex>cnt2 \leftarrow \mathtt{ClassInv}[R_2][c]</tex>
'''if''' <tex> \mathtt{InQueue}[R_1][c] == false </tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
'''insert''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_1]</tex>
