有限オートマトンのための空間と時間の効率的な符号化

Question

私は、有限オートマトンの遷移を効率的に符号化する方法について考えていました。私が良いと思ったアイデアは、intのビットにトランジションシンボルを1または0として効率的にエンコードするために、ステートごとに最大32個の出力トランジションがあることがわかっている場合、intなどを使用することでした。

したがって、タイプT（たとえば文字列）をintにマップするクラスがあります。 ID（文字列）は、文字列が整数エンコーディングとして割り当てられたIDを返します。 空のIDオブジェクトに文字列 "fish"、 "cat"、 "tree"を順番に追加すると、 "fish"に1、 "cat"に1、 "tree"に0が割り当てられます。

後で私は、2の累乗を個々の遷移記号に関連づけます。電力は、遷移シンボルに割り当てられたIDによって決定されます。 IDクラスではなく、「魚」、「猫」と「木」よりも、英語のアルファベットを供給した場合

結果のマッピングは以下のようになり

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

出エッジ」を有する状態のoutgoing_symbolsフィールドA」、 "C"、 "E" と "F" は、したがって、このようになります。

今、私は単にstate.outgoing_symbols + = POW（2、ID（transition_symbol））を行うことができます

00000000 00000000 00000000 00110101 
     zy xwvutsrq ponmlkji hgfedcba 

への移行を追加するとき既存の状態。

私はこの表現の利点は、私は単一のintに32個のシンボルを格納することができると私はかどうかの状態の一定時間照会を行うことができることである

00000000 00000000 00000010 00110101 
     zy xwvutsrq ponmlkji hgfedcba 

もたらすoutgoing_symbolsに2^9を追加するstate.outgoing_symbols+=pow(2,ID(j))をするだろう

はデルタ状態をマッピングし、この

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ 
│ 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つのベクトルを持つことができます.1つは遷移シンボルIDと、1つのベクトルのベクトルはターゲット状態のIDを格納します。 2つのベクトルは「同期」され、すべてのiについてvector1[i]はvectpr2[i]に対応します。 2つのベクトルではなく、フォームの構造体の1つのベクトル

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

は明らかにそれが持っているいくつかの簡単な種類のベクトルではなく、1つのベクトルの優れているところ、私は理解していないいくつかのプロセッサの魔法を使用することであるを持っている理由シンプルな型の構造体。

いずれの場合も、線形または対数ルックアップの種類でターゲット状態をルックアップする必要があるため、2の累乗として符号化によって遷移シンボルを絶えず検索する利点があります。しかし、シンボルをターゲット状態にマッピングするために、そのエンコーディングを使用する方法は考えられません。

誰でも私にこのような何かを読んだり、まったくまっすぐに読んだりすることができますか？

Answer 1

私が正しく理解していれば、ビットマスクにビットが設定されているシンボルごとにベクトル内にエントリを格納し、シンボルが与えられたエントリを効率的に検索する必要があります。

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

をインデックスが見えるように返さ使用します。その場合は

、あなたがチェックしているよりも低い全てのシンボルのためのマスクに設定されたビットの数をカウントすることにより、エントリのインデックスを計算することができます状態のために格納されたターゲット状態のベクトルのエントリをアップする。実際にセットに入っているシンボルに対して有効な結果しか得られません。 （1 << symbolID）あなたのビット・テスト用のビットを計算するHow to count the number of set bits in a 32-bit integer?