Изменения

# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний (<tex>\mathtt{P} \leftarrow \{ \mathtt{F, Q } \setminus \mathtt{F} \}</tex>).

# Из очереди извлекается пара <tex>(C, a)</tex>, <tex>C</tex> далее именуется как мастер Сплиттерсплиттер.# Все классы Каждый класс <tex>R</tex> текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер(<tex>R_1</tex>), а второй из всех оставшихся(<tex>R_2</tex>). # Те классы, которые разбились Если <tex>R</tex> разбился на два непустых подкласса(т.е. <tex> R_1 \ne \emptyset</tex> and <tex>R_2 \ne \emptyset </tex>).## В разбиении <tex>P</tex> класс <tex>R</tex> заменяется на свои подклассы <tex>R_1</tex> и <tex>R_2</tex>.## Перебираются символы алфавита <tex>c \in \Sigma</tex>, заменяются этими подклассами в разбиениивсе пары <tex>(R_1, c)</tex> и <tex>(R_2, а подклассы добавляются c)</tex> помещаются в очередь.

'''while''' <tex> \mathtt{S} \ne \varnothing </tex> <tex>(C, a) \leftarrow</tex> '''pop'''('''from''' <tex>\mathtt{S}</tex>)

<tex>R_1 = R , R_2 \cap \delta^{-1} (C, a) leftarrow </tex> '''split'''(<tex>R_2 = R \setminus R_1, C, a</tex>)

'''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex> '''for''' <tex> c \in \Sigma </tex> '''insert''' <tex>(R_1, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''insert''' <tex>(R_2, c)</tex> '''in''' <tex>\mathtt{S}</tex>

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы пары в очередь.После замены класса <tex>R</tex> в разбиении <tex>P</tex> на его подклассы <tex>R_1</tex> и <tex>R_2</tex>, как и раньше перебираем символы алфавита <tex>c \in \Sigma</tex>. Если класс пара <tex>(R, c)</tex> уже есть в очереди, то согласно лемме можно просто заменить его её на пары <tex>(R_1, c)</tex> и <tex>(R_2, c)</tex>.  Если класса пары <tex>(R, c)</tex> нет в очереди, то согласно лемме в очередь можно достаточно добавить класс любую из пар <tex>R(R_1, c)</tex> и любой из <tex>R_1(R_2, c)</tex> и . Это следует из следующих соображений: <tex>R_2R</tex>, а так как для любого класса может быть в разбиении только если в очередь были положены пары <tex>B(R, a)</tex> из текущего разбиения выполняется :для <tex>\forall r a \in B \Sigma</tex>, а поскольку в очереди пары <tex>(R,\c)</tex> нет,\то мы её уже успели рассмотреть, \deltaследовательно классы из разбиения <tex>P</tex> уже были разбиты по <tex>(rR, ac) \in R </tex> or . === Реализация ===:<tex> \forall r \in B \pushSetsToQueue(S,\R_1,\, \delta(rR_2, ac) \notin R</tex> то в очередь можно добавить только меньшее {{---}} функция, которая добавляет одно из <tex>(R_1, c)</tex> и , <tex>(R_2, c)</tex>в очередь S.

<tex>S</tex> {{---}} очередь из пар <tex>(C, a)</tex>.

'''insert''' <tex> pushSetsToQueue(\mathtt{min} (\mathtt{S, F, Q} \setminus \mathtt{F}), c)</tex> '''in''' <tex>\mathtt{S}</tex>

<tex>(C, a) \leftarrow</tex> '''pop'''('''from''' <tex>\mathtt{S}</tex>) <tex>T \leftarrow \{R \ | \ R \in \mathtt{P}, \ R</tex> splits by <tex>(C, a) \}</tex> '''for each''' <tex>R</tex> '''in''' <tex>T\mathtt{P}</tex> <tex> R_1, R_2 \leftarrow </tex> '''split'''(<tex>R, C, a</tex>) '''replace''' <tex>R</tex> '''inif''' <tex>R_1 \ne \mathtt{P}</tex> '''with''' <tex>R_1varnothing </tex> '''and''' <tex>R_2</tex> '''for''' <tex>c \in ne \Sigmavarnothing </tex> '''ifreplace''' <tex>(R, c)</tex> '''in''' <tex>\mathtt{SP}</tex> '''replacewith''' <tex> (R, c)R_1</tex> '''inand''' <tex>\mathtt{S}R_2</tex> '''withfor''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)\in \Sigma</tex> '''else''' '''insert''' <tex>pushSetsToQueue(\mathtt{min}(S, R_1, R_2), c)</tex> '''in''' <tex>\mathtt{S}</tex>

К сожалениюПонятно, совсем не очевидно, как быстро находить множество <tex>T</tex>что нам нет никакой необходимости просматривать все классы в разбиении. С другой стороны, понятно, что <tex>T \subset T'</tex>, где <tex>T'</tex> {{---}} это множество классов текущего разбиенияВполне достаточно рассмотреть лишь те классы, из состояний которых в автомате существует переход есть хотя бы одно ребро в состояния сплиттера <tex>C</tex> по символу <tex>a</tex>. Модифицируем наш алгоритм: Обозначим множество таких классов за T' (его нужно будет эффективно находить для каждой очередной пары <tex> (C, a) </tex> будем находить <tex> T' </tex>, и с каждым классом состояний из <tex> T' </tex> будем производить те же действия, что и раньше).

'''insert''' <tex>pushSetsToQueue(\mathtt{min} (\mathtt{S, F, Q} \setminus \mathtt{F}), c)</tex> '''in''' <tex>\mathtt{S}</tex>

<tex>(C, a) \leftarrow</tex> '''pop'''('''from''' <tex>\mathtt{S}</tex>)

'''for each''' <tex>R</tex> '''in''' <tex>T'</tex> '''if''' <tex>R</tex> splits by <tex>(C, a)</tex> <tex> R_1, R_2 \leftarrow </tex> '''split'''(<tex>R, C, a</tex>) '''replace''' <tex>R</tex> '''inif''' <tex>R_1 \ne \mathtt{P}</tex> '''with''' <tex>R_1varnothing </tex> '''and''' <tex>R_2</tex> '''for''' <tex>c \in ne \Sigmavarnothing </tex> '''ifreplace''' <tex>(R, c)</tex> '''in''' <tex>\mathtt{SP}</tex> '''replacewith''' <tex>(R, c)R_1</tex> '''inand''' <tex>SR_2</tex> '''withfor''' <tex>(R_1, c)\in \Sigma</tex> '''and''' <tex>pushSetsToQueue(R_2S, c)</tex> '''else''' '''insert''' <tex>(\mathtt{min}(R_1, R_2), c)</tex> '''in''' <tex>\mathtt{S}</tex>

Разбиение <tex> P </tex> можно поддерживать четырьмя массивами:*Каждая итерация цикла <tex>\mathttmathrm{Classwhile}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>;*может быть выполнена за <tex>O(|Q| + |\mathtt{PartInverse}[i]</tex> {{---}} указатель на голову [[Список#Двусвязный список|двусвязного списка]], содержащего состояния, принадлежащие классу <tex> i ) </tex>;*для текущей пары <tex>\mathtt{Card}[i]</tex> {{---}} количество состояний в классе <tex>i</tex>;*<tex>\mathtt{Place}[r]</tex> {{---}} указатель на состояние <tex>r</tex> в списке <tex>\mathtt{Part[Class}[r]](C,a)</tex>. Покажем, как можно достичь этой оценки.

Так как мы храним указательКлассы разбиения <tex>P</tex> будем поддерживать с помощью множеств на хэш-таблицах (само же разбиение - обычный вектор, где находится состояние в двусвязном списке, то операцию перемещения индекс - номер класса). Это позволит нам эффективно переносить состояния из одного класса в другой можно выполнить (за <tex>O(1)</tex>).

Чтобы эффективно находить множество *<tex>\mathtt{InverseClass}[r]</tex>{{---}} номер класса, построим массив которому принадлежит состояние <tex>r</tex>*<tex>\mathtt{InvCard}[i]</tex> {{---}}размер класса <tex>i</tex>, который для состояния *<tex>r\mathtt{Queue}</tex> и символа {{---}} очередь пар <tex>(C, a)</tex>, где <tex>C</tex> в - номер класса (сплиттера)*<tex>\mathtt{InvInQueue}[r][aC]</tex> хранит {{---}} множество состоянийна хэш-таблице, из которых существует переход в содержащее символ <tex>ra</tex> по символу , если в очереди содержится пара <tex>(C, a)</tex>. Так как наш алгоритм не меняет изначальный автомат, то массив *<tex>\mathtt{Inv}[r][a]</tex> можно построить перед началом основной части алгоритма{{---}} массив состояний, что займет из которых есть ребра по символу <tex>a</tex> в состояние <tex>O(|\Sigma| |Q|)r</tex> времени.(мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма)

Теперь научимся Для обработки <tex>T'</tex> за <tex>O(|Q| + |\mathtt{Inverse}|)</tex> обрабатывать множество <tex>T'</tex> и разбивать классы. Для этого нам понадобится следующая структура:

Сам же алгоритм обработки //Добавим <tex>TF, Q \setminus F </tex> в <tex> \mathtt{Queue} </tex>, <tex>\mathtt{InQueue}</tex> '''while'''<tex>\mathtt{Queue} \ne \varnothing</tex> будет выглядеть так: <tex>(C, a) \leftarrow</tex> '''pop''' '''from''' <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{Size}[i] == 0</tex> '''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex> <tex>\mathtt{Size}[i]++</tex> '''for''' <tex> i \in \mathtt{Involved}</tex> '''if''' <tex>\mathtt{Size}[i] < \mathtt{Card}[i]</tex> <tex>\mathtt{Size}[i] = -1</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{Size}[i] < \mathtt{Card}[i]== -1</tex> '''if''' <tex>\mathtt{Twin}[i] == 0</tex> <tex>\mathtt{Counter}++</tex> <tex>\mathtt{Twin[i]} = \mathtt{Counter}</tex> '''move''' <tex>r</tex> '''from''' <tex>i</tex> '''to''' <tex>\mathtt{Twin}[i]</tex> '''for''' <tex> j \in \mathtt{Involved}</tex> '''if''' <tex> \mathtt{Twin}[j] \neq 0 </tex> '''for''' <tex>c \in \Sigma</tex> <tex>pushSetsToQueue(\mathtt{Queue}, j, \mathtt{Twin}[j], c)</tex> <tex>\mathtt{Size}[j] = 0</tex> <tex>\mathtt{Twin}[j] = 0</tex> '''remove''' <tex>a</tex> '''from''' <tex>\mathtt{InQueue}[C]</tex> Стоит отметить, что массивы <tex>\mathtt{Size}, \mathtt{Twin}</tex> аллоцируются ровно один раз при инициализации алгоритма.

Для быстрой проверки, находится ли пара Осталось только реализовать <tex>(C,a)pushSetsToQueue</tex> в очереди . <tex>SpushSetsToQueue(\mathtt{Queue}, R_1, R_2, c)</tex>, будем использовать массив : <tex>cnt1 \leftarrow \mathtt{InQueueCard}[R_1]</tex> размера <tex>|Q| cnt2 \times |leftarrow \Sigma|mathtt{Card}[R_2]</tex>, где '''if''' <tex>\lnot ( \mathtt{InQueue}[C][aR_1] = true</tex>, если пара '''contains''' <tex>(C,ac)</tex> содержится в очереди. Так как при разбиении очередного класса '''and''' <tex>Rcnt1 <= cnt2 </tex> на подклассы '''push''' <tex>(R_1, c)</tex> и '''to''' <tex>R_2\mathtt{Queue}</tex> мы в действительности создаем лишь один новый класс, то замена класса '''insert''' <tex>Rc </tex> в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом '''into''' <tex>\mathtt{InQueue}[R_1]</tex>. В результате каждая операция с очередью требует '''else''' '''push''' <tex>O(1R_2, c)</tex> времени.'''to''' <tex>\mathtt{Queue}</tex> '''insert''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_2]</tex>

Количество итераций цикла <tex>\mathrm{while}</tex> не превышает <tex> 2 |\Sigma| |Q| </tex>.

<tex>\sum |\mathtt{Inverse}|</tex> по всем итерациям цикла <tex>\mathrm{while}</tex> не превосходит <tex>|\Sigma| |Q| \log_2(|Q|)</tex>.

*По [[#Лемма2 | второй лемме]] количество итераций цикла <tex>\mathrm{while}</tex> не превосходит <tex>O(|\Sigma| |Q|)</tex>.