c++ - 有限自动机转换的空间和时间有效编码

Question

我一直在思考如何有效地对有限自动机的转换进行空间编码，并保证快速查找时间。一个对我来说听起来不错的想法是使用整数，如果我知道我每个状态最多有 32 个传出转换以空间有效地将转换符号编码为 1 或 0 的位。

因此，我有一个将类型 T(例如字符串)映射到整数的类。 ID(string) 返回字符串被分配为其整数编码的 ID。 将字符串“fish”、“cat”和“tree”相继添加到空 ID 对象中会将 0 分配给“fish”，将 1 分配给“cat”，将 2 分配给“tree”。

稍后我会将 2 的幂与各个转换符号相关联。功率由分配给转换符号的 ID 决定。

如果 ID 类输入的是英文字母而不是“fish”、“cat”和“tree”，则生成的映射将是

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

具有出边“a”、“c”、“e”和“f”的状态的 outgoing_symbols 字段因此看起来像这样:

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

这种表示的优点是我可以在单个 int 中存储 32 个符号，并且我可以不断查询状态是否具有给定符号的转换:

假设 delta 是这样的结构 vector

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 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                             |
                              └───────────────────────────────────────────────────────────────────────┘

它将状态 ID 0 到 n 映射到 outgoing_symbols 的结构以及从符号到目标状态的映射。然后我可以写这个函数:

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

最大的问题是，到目前为止，我还没有将转换符号与目标状态相关联，而且我想不出任何方法来将这种非常有效的转换编码与必要映射的有效编码结合使用。

我可以有 2 个 vector ，一个带有转换符号 ID，另一个 vector 的 vector 存储目标状态的 ID。这两个 vector 将“同步”，因此对于所有 i vector1[i] 都对应于 vectpr2[i]。具有 2 个 vector 而不是 1 个形式结构 vector 的原因

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

是利用一些我不明白的处理器魔法，显然有几个简单类型的 vector 比一个简单类型的结构 vector 更好。

在任何情况下，必须以线性或对数查找的方式查找目标状态都会浪费通过编码不断查找转换符号的优势，因为 2 的幂会被浪费掉。但我想不出任何方法来利用该编码来将符号映射到目标状态。

任何人都可以给我建议在哪里阅读这样的东西，或者甚至直接知道如何做到这一点？

Answer 1

如果我没理解错的话，您希望为每个在位掩码中设置了位的符号在 vector 中存储一个条目，并高效地查找给定符号的条目。

在这种情况下，您可以通过计算掩码中低于您正在检查的符号的所有符号设置的位数来计算条目的索引:

int getSymbolIndex(int state, int symbolID)
{
      if(symbolID == 0)
        return 0;
    return NumberOfSetBits(delta[state].outgoing_symbols & ((1 << symbolID) -1));
}

使用返回的索引在为状态存储的目标状态 vector 中查找条目。它只为集合中实际存在的符号提供有效结果。

有关计算整数位的有效方法，请参阅以下问题:How to count the number of set bits in a 32-bit integer?