Space 和有限自动机转换的时间高效编码

Question

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

所以，我有一个 class 将类型 T（例如字符串）映射到整数。 ID(string) returns 字符串被分配为其整数编码的 ID。将字符串 "fish"、"cat" 和 "tree" 相继添加到空 ID 对象中会将 0 分配给 "fish"、1 分配给 "cat" 以及 2 分配给 "tree".

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

如果 ID class 被输入英文字母而不是 "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 是这样的结构向量

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 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 个向量，一个带有转换符号 ID，另一个向量的向量存储目标状态的 ID。这两个向量将是 "synced up"，因此对于所有 i vector1[i] 对应于 vectpr2[i]。具有 2 个向量而不是 1 个形式为

的结构向量的原因

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

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

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

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

Answer 1

如果我没理解错的话，你想为每个在位掩码中设置了位的符号在向量中存储一个条目，并有效地查找给定符号的条目。

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

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

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

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

Space 和有限自动机转换的时间高效编码

Space and Time Efficient Encoding of Transitions for Finite Automata

c++

performance

finite-automata

state-machine

memory-efficient