В моем генераторе лексического анализатора я использую алгоритм Макнотона и Ямады для построения NFA и одно из его свойств, заключающееся в переходе от I к J, отмеченному символом в позиции J.
Таким образом, каждый узел NFA можно представить просто как список следующих возможных состояний.
Какая структура данных лучше всего подходит для хранения данных такого типа? Он должен обеспечивать быстрый поиск всех возможных состояний и занимать меньше места, но время вставки не так важно.
Насколько я понимаю, вы хотите закодировать граф, где узлы — это состояния, а ребра — переходы, и где каждое ребро помечено символом. Это правильно?
Скучный, но практичный ответ состоит в том, чтобы иметь объект для каждого состояния и кодировать переходы в какой-то небольшой структуре этого объекта.
Простейшим из них был бы массив, индексированный по символьному коду: это настолько быстро, насколько это возможно, но, естественно, неэффективно по пространству. Вы можете сделать его более эффективным с точки зрения использования пространства, используя своего рода усеченный массив со смещением: сохраните только часть массива, содержащую переходы, вместе с начальным и конечным индексами этой части. При поиске в нем символа проверяйте, что его код находится в пределах допустимого диапазона; если это не так, обработайте его как нулевое ребро (или ребро обратно в начальное состояние или что-то еще), и если это так, извлеките элемент по индексу (код символа - начало). Имеет ли это смысл?
Более сложным вариантом будет небольшая хеш-таблица, которая будет компактнее, но немного медленнее. Я бы предложил закрытое хеширование, потому что списки коллизий будут занимать слишком много памяти; линейного зондирования должно быть достаточно. Вы можете изучить использование идеального хеширования (поищите его), которое занимает много времени для создания таблицы, но затем дает поиск без коллизий. Однако процесс генерации довольно сложен.
Умный подход состоит в том, чтобы использовать как массивы, так и хеш-таблицы, и выбирать один или другой на основе количества ребер: если сжатый массив будет больше, чем, скажем, на треть, используйте его, а если нет, используйте хеш-таблицу. .
Что-то более радикальное, что вы могли бы сделать, это использовать массивы, но перекрывать их — если они разрежены, в них будет много дыр, и если вы сообразительны, вы можете расположить их так, чтобы записи в каждом массиве совпадают с дырами в других. Это даст вам быстрый поиск, а также отличную эффективность памяти. Вам понадобится какая-то схема, чтобы отличить, когда поиск что-то нашел, а когда он нашел пустой слот с переходом в какое-то другое состояние, но я уверен, что вы можете что-то придумать.
