Структура данных для хранения узлов DFA
Мне нужна структура данных для хранения узлов конечного детерминированного автомата, чтобы найти узлы, которые удовлетворяют определенному условию, быстро (логарифмически).
Данное условие является следующим:
У меня есть узел
pи я должен найти узелqтакой, что:(p ∈ F ≡ q ∈ F) & (∀ a : a ∈ Σ : δ(p,a) = δ(q,a)), То есть,pа такжеqлибо оба являются окончательными, либо оба нет, и они имеют переходы к одним и тем же узлам.
Я не хочу проходить через все узлы, потому что это будет медленно. Очевидно, если набор букв алфавита, для которого q имеет переходы, отличается от множества, для которого p имеет переходы, q это не тот узел, который я ищу.
Кроме того, если p а также q иметь другое количество переходов, q опять не тот узел, который я хочу. Поэтому я думал о структуре данных, которая сортирует узлы в соответствии с их окончательностью и количеством переходов, поэтому мне не нужно просматривать все узлы, только те, которые имеют одинаковую конечность и одинаковое количество переходов. Но это все еще не логарифмический. Есть идеи.
Я использую с ++.
Решение
На узле есть два типа информации q:
- Логическая информация
(q ∈ F) - Список пар
(a,n)такой, что δ (q, a) == n (то есть список пар символов / узлов-узлов, достижимых из q)
Эти две части информации (логическое значение и список пар) могут быть представлены как одна последовательность, и вы можете вычислить ключ хеш-функции для этой последовательности.
Это позволит хэшировать узлы по интересующему вас свойству. Поиск узлов-кандидатов q для данного узла p будет тогда около O (1).
(Для алгоритма минимизации, который вы упомянули в комментариях, это означает, что вам нужно будет перестраивать этот хэш после каждой итерации, потому что указатели узла назначения в парах будут меняться в результате действий, выполненных во время итерации.)
Другие решения
Я построил строку для каждого узла и поместил строки в дерево AVL. Он выполнялся быстрее, чем решение с хэш-функцией и неупорядоченной картой, и использовал гораздо меньше памяти.
Строка, представляющая узел, выглядит следующим образом: она начинается с 0 или же 1в зависимости от того, является ли узел конечным или нет, а затем пары (a,n) кодируются следующим образом: a является int в соответствии с положением символа a в алфавите и n Другой int, индекс узла, к которому он имеет переход с символом a,