効率的な検索と挿入をサポートする、動的文字列用の文字列ルックアップ データ構造を実装したいと考えています。現在、トライを使用していますが、可能であればメモリ フットプリントを減らしたいと考えています。 このウィキペディアの記事では、DAWG/DAFSA について説明しています。これは、接尾辞を圧縮することで、試行よりも明らかに多くのスペースを節約します。ただし、文字列が合法かどうかは明確にテストされますが、違法な文字列を除外する方法があるかどうかはわかりません。たとえば、「cite」と「cat」という単語を使用すると、「t」と「e」は最終状態であり、DAWG/DAFSA は次のようになります。
c
/ \
a i
\ /
t
|
e
また、"cit" と "cate" は、メタ情報を持たない正当な文字列として誤って認識されます。
質問:
1) 文字列/パス (合法性など) に関するメタ情報を DAWG/DAFSA に格納するための推奨される方法はありますか?
2) DAWG/DAFSA が要件 (効率的な検索/挿入およびメタ情報の保存) と互換性がない場合、使用するのに最適なデータ構造は何ですか? 最小限のメモリ フットプリントがあればよいのですが、絶対に必要というわけではありません。