1

C++ で基本的な Trie を実装するプログラムを作成しました。すべてのノードには 26 個の子ポインター (英語のアルファベット用) があり、Node クラスは次のようになります。

class Node
{
public:
       Node* parent;
       Node* child[26];
       unsigned int number_of_children;
....
}

ここで、{snapple, dapple}、{distract、attract} など、3 つ以上のアルファベットが一致する多くの単語が存在する可能性があります。これらのサブワードの個別のエントリ (上記の例のように - apple、tract) を保存し、他のユーザーがそれらを指すようにしたい ({sn-ptr_to_apple, d-ptr_to_apple}、{dis-ptr_to_tract、at-ptr_to_tract} など) ）。挿入が完了した後にこれを実行する関数を持つのではなく、単語自体を挿入しながらこれを処理するのが最善だと思います。

これを設計する際に助けが必要です。現在、実行効率については調べていません。コード/設計はコンパクトにする必要があります。現在、私はノードにアクセスし、null 以外のすべての兄弟を (兄弟の子に沿ってトラバースすることによって) 入力単語と一致するかどうかを確認し、たとえば 4 単語の一致がある場合に備えてポインターを保存します (ただし、コードは取得されていますより長く、難読化します)。

4

1 に答える 1

2

従来の試行では、一般的なプレフィックスを圧縮します。本質的に、一般的なサフィックスを圧縮したいと考えています。最も簡単な方法は、トライ エントリを逆方向にビルドすることです。

これは、文字列を逆方向にトライに読み込む必要があることを意味します。

于 2012-12-06T00:46:15.490 に答える