data-structures - NFA表現のデータ構造

Question

私の字句解析ジェネレーターでは、NFA の構築に McNaughton と Yamada のアルゴリズムを使用し、I から J に遷移するそのプロパティの 1 つは、J の位置に char でマークされています。

したがって、NFA の各ノードは、次の可能な状態のリストとして単純に表すことができます。

このタイプのデータを格納するのに最適なデータ構造はどれですか? 可能なすべての状態をすばやく検索し、使用するスペースを少なくする必要がありますが、挿入時間はそれほど重要ではありません。

Answer 1

私の理解では、ノードが状態でエッジが遷移であり、すべてのエッジが文字でラベル付けされているグラフをエンコードしたいということです。あれは正しいですか？

退屈だが実用的な答えは、各状態のオブジェクトを持ち、そのオブジェクトの小さな構造に遷移をエンコードすることです。

最も単純なものは、文字コードでインデックス付けされた配列です。これは、可能な限り高速ですが、当然のことながらスペース効率は良くありません。一種のオフセット、切り詰められた配列を使用することで、スペース効率を高めることができます。トランジションを含む配列の部分のみを、その部分の開始インデックスと終了インデックスと共に保存します。その中の文字を検索するときは、そのコードが境界内にあることを確認してください。そうでない場合は、null エッジ (または開始状態に戻るエッジなど) として扱い、そうである場合は、インデックス (文字コード - 開始) で要素をフェッチします。それは理にかなっていますか？

より複雑なオプションは小さなハッシュテーブルです。これはよりコンパクトですが、少し遅くなります。衝突リストは大量のメモリを使用するため、閉じたハッシュをお勧めします。線形プロービングで十分です。テーブルを生成するのに多くの時間がかかりますが、衝突のないルックアップが得られます。ただし、生成プロセスは非常に複雑です。

巧妙なアプローチは、配列とハッシュテーブルの両方を使用し、エッジの数に基づいてどちらかを選択することです: 圧縮された配列が 3 分の 1 以上になる場合はそれを使用し、そうでない場合はハッシュテーブルを使用します。 .

さて、あなたができるもう少し急進的なことは、配列を使用することですが、配列をオーバーラップさせることです.それらがまばらである場合、配列には多くの穴があります.各配列のエントリは、他のエントリの穴と並んでいます。これにより、検索が高速になりますが、優れたメモリ効率も得られます。ルックアップで何かが見つかったときと、他の状態の遷移がある空のスロットが見つかったときを区別するためのスキームが必要になりますが、何か考えられると確信しています。