Пространственно-временное кодирование переходов для конечных автоматов

Я думал о том, как эффективно кодировать переходы для конечных автоматов, а также гарантировать быстрое время поиска. Идея, которая звучит хорошо для меня, состояла в том, чтобы использовать, например, int, если я знаю, что у меня есть не более 32 исходящих переходов для каждого состояния в пространство, чтобы эффективно кодировать символы перехода как 1 или 0 в битах целого числа.

Итак, у меня есть класс, который отображает тип T (например, строки) в int. Идентификатор (строка) возвращает идентификатор этой строки в качестве целочисленной кодировки.
Добавление строк «fish», «cat» и «tree» одна за другой в пустой объект идентификатора присвоит 0 для «fish», 1 для «cat» и 2 для «tree».

Позже я бы связал степени 2 с отдельными символами перехода. Мощность определяется идентификатором, назначенным символу перехода.

Если бы в классе идентификаторов использовался английский алфавит, а не «рыба», «кошка» и «дерево», результирующее отображение было бы

a : 0
b : 1
c : 2
...
j : 9
...
z : 26

outgoing_symbols поле состояния, имеющего исходящие ребра «a», «c», «e» и «f», будет выглядеть следующим образом:

00000000 00000000 00000000 00110101
zy xwvutsrq ponmlkji hgfedcba

Теперь я могу просто сделать state.outgoing_symbols + = pow (2, ID (transition_symbol)) при добавлении перехода в существующее состояние.

я бы сделал state.outgoing_symbols+=pow(2,ID(j)) добавить 2 ^ 9 к outgoing_symbols, в результате чего

00000000 00000000 00000010 00110101
zy xwvutsrq ponmlkji hgfedcba

Преимущество этого представления состоит в том, что я могу хранить 32 символа в одном int, и я могу делать постоянные запросы времени для состояний, имеют ли они переход с данным символом:

Предположим, что дельта — это вектор таких структур

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │...│   │   │   │   │   │   │   │   │   │   │ n │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
└───┴───┴───┴───┴───┴───┴───┴─┬─┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
│
│
│
│
│
├───────────────────────────────────────────────────────────────────────┐
│   sym_enc outgoing_symbols     00000000 00001000 10000010 00110100    │
│                                                                       │
│   T mapping_of_symbols_onto_target_states                             |
└───────────────────────────────────────────────────────────────────────┘

который сопоставляет идентификаторы состояния от 0 до n структурам outgoing_symbols и отображение символов в целевые состояния. Тогда я могу написать эту функцию:

bool has_outgoing_symbol(int state, int symbolID)
{
return delta[state].outgoing_symbols & pow(2, symbolID) == symbolID;
}

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

Я мог бы иметь 2 вектора, один с идентификаторами символов перехода и один вектор векторов, которые хранят идентификаторы целевых состояний. Два вектора будут «синхронизированы», так что для всех vector1[i] соответствует vectpr2[i], Причина иметь 2 вектора вместо 1 вектора структур вида

struct transition
{
std::vector to_states;
int transition_symbol;
};

заключается в использовании некоторого волшебства процессора, которое я не понимаю, где, очевидно, лучше иметь несколько векторов простых типов, а не один вектор структур простых типов.

В любом случае необходимость поиска целевого состояния в виде линейного или логарифмического поиска дает преимущество постоянного поиска для символа перехода посредством кодирования, так как степени 2 теряются. Но я не могу придумать, как использовать эту кодировку для отображения символов в целевых состояниях.

Кто-нибудь может дать мне предложение о том, где читать что-то вроде этого или, может быть, даже прямо есть идея, как это сделать?