структура данных для представления NFA

Question

В моем генераторе лексического анализатора я использую алгоритм МакНотона и Ямады для построения NFA и один из его свойств, который имеет форму перехода I в J, обозначенную символом в позиции J.

Итак, каждый узел NFA может быть представлен просто как список следующих возможных состояний.

Какая структура данных подходит для хранения данных такого типа? Он должен обеспечивать быстрый поиск всех возможных состояний и использовать меньше места, но время вставки не так важно.

Answer 1

Я понимаю, что вы хотите кодировать граф, где узлы являются состояниями и ребрами являются переходами, и где каждое ребро помечено символом. Это верно?

Тупой, но практичный ответ состоит в том, чтобы иметь объект для каждого состояния и кодировать переходы в некоторой небольшой структуре в этом объекте.

Простейшим из них будет массив, индексированный по символьному коду: это так же быстро, как и получается, но не естественным образом экономит пространство. Вы можете сделать это более экономичным, используя сортировку, усеченный массив: сохраните только часть массива, которая содержит переходы, а также начальные и конечные индексы этой части. При поиске персонажа в нем проверьте, что его код находится в пределах; если это не так, относиться к нему как к нулевому краю (или к возврату в исходное состояние или к чему-либо другому), и если это так, выведите элемент по индексу (код символа - начало). Имеет ли это смысл?

Более сложным вариантом будет небольшая хэш-таблица, которая будет более компактной, но немного медленной. Я хотел бы предложить закрытое хеширование, потому что списки конфликтов будут использовать слишком много памяти; линейного зондирования должно быть достаточно. Вы можете изучить использование идеального хеширования (посмотрите его), что занимает много времени для создания таблицы, но затем дает возможность поиска без конфликтов. Однако процесс генерации довольно сложный.

Умный подход состоит в том, чтобы использовать как массивы, так и хеш-таблицы и выбирать один или другой на основе количества ребер: если сжатый массив будет больше, чем, скажем, третий полный, используйте его, но если нет , используйте хеш-таблицу.

Теперь что-то более радикальное, что вы могли бы сделать, было бы использовать массивы, но чтобы перекрывать их - если они разрежены, у них будет много отверстий, и если вы умны, их так, что записи в каждом массиве выравниваются с отверстиями в других. Это даст вам быстрый поиск, а также отличную эффективность памяти. Вам понадобится какая-то схема для выделения, когда поиск нашел что-то, когда он нашел пустой слот с переходом какого-то другого состояния, но я уверен, что вы можете что-то придумать.