11

単語ゲーム ソルバーのデータ構造を構築しようとしています。

{A、A、D、E、I、L、P、T、V、Y} の形式の約 150,000 セットを保存する必要があります。(これらは正規化された英単語、つまりソートされた文字です。これは、同じ文字を 2 回含むことができるマルチセットであることに注意してください。)

次の種類のクエリに対する yes/no の回答を効率的に取得する必要があります: 指定されたサブセットを持つセットはありますか? たとえば、{D、E、I、L、L、P} のセットを含む既知の単語はありますか?

要件：

  • クエリは高速でなければならない
  • データ構造は、妥当な容量 (50 MB 未満など) に収まる必要があります。
  • データ構造はリアルタイムで構築する必要はありません。それは事前に計算されています。

このニーズに適したデータ構造はありますか? これは、ターゲット セットが実際にはマルチセットであるという点で、StackOverflowの他の セット マッチングの質問とは少し異なります。

4

3 に答える 3

3

これは、私がかつて作成した、変更されたプレフィックス ツリー/トライを思い出させます。少し違いますが、うまくいくかもしれません。境界が大きい/境界がない場合、またはそれを自分の言語に変換できない場合 (私は c++ でコーディングしています)、機能しない可能性があります。

つまり、基本的にはトライでは次の文字に対応する子を格納するのが普通ですが、私は各文字の頻度に対応する子を格納しました。

基本的に（私の観点から）質問は、「サブセットと同じかそれ以上の文字を持つセットはありますか?」です。たとえば、サブセットが { A,D,E,E } の場合、少なくとも 1 つの A、1 つの D、および 2 つの E を含むセットがあるかどうかを確認する必要があります。

だから、トライのためにあなたはこのようなものを持っています

            Root
           / | \
          / /|\ \
         / / | \ \
        1 2  ... MAX <-- This represents the frequency of "A"
       /|\ ..... /|\
      1..MAX    1..MAX <-- Frequency of "B"
      ...............
      ...............
      ...............
     1 ... ... ... MAX <-- Frequency of "Y"
    /|\ .... .... / | \
   1..MAX ...... 1 .. MAX <-- Frequency of "Z"

基本的にすべての ... は、表示に時間がかかりすぎる多くのものを表しています。/,| と \ は親子関係を表し、MAX は文字の最大頻度を表します。

つまり、次のような構造体 (私は C++ でコーディング) があります。

struct NODE {
    NODE *child[MAX + 1]; // Pointers to other NODE's that represents
                          // the frequency of the next letter
};

ノードを作成するときは、そのすべての子を NULL に初期化する必要があります。これは、コンストラクター (C++ の場合) または makeNode() 関数を使用して行うことができます。

NODE* makeNode() {
    NODE* n = new NODE;         // Create a NODE
    for(int i = 0;i <= MAX;i++) // For each child
        n->child[i] = NULL;     // Initialize to NULL
};

最初は、トライは単なるルートです

NODE* root = new NODE;

トライにセットを追加すると、各文字の頻度が取得され、トライが実行されます。特定のノードで、次の文字に対応する子が NULL の場合、新しい NODE を作成するだけです。

トライを検索するときは、サブセット内の文字の頻度以上に対応する各ノードのすべての子を検索します。たとえば、サブセットに 3 つの A がある場合、root->child[3]、次に root->child[4]、次に ... root->child[MAX] のすべてを検索します。

それはおそらく非常に複雑で紛らわしいので、1) 私が怒っていないと思うなら、何が紛らわしいのかについてコメントしてください.

于 2011-03-05T01:46:57.527 に答える
2

KD-Treesまたはバリアントを使用してみてください。

探索する関連トピックは、多次元範囲の検索/クエリです。

警告: 私はこれらを自分で使用したことはありませんが、上記のトピックに関する文献を読んで何か役立つものを見つけられることを願っています.

それが役立つことを願っています。

于 2011-03-05T01:42:01.323 に答える
0

おそらく、トライを使用して各セットをトライに挿入し、ターゲットサブセットを使用してトライを繰り返し走査して、一致するサブセットがあるかどうかを調べることができます。少なくとも私はそうすると思います。

「トライ」は、実際には reTRIEvable データ構造用に考案されたもので、通常のツリーとほとんど同じですが、次のように異なる順列を持つノードがあります。

     A
    / \
   AT AN
     / | \
    |  |  AND
   ANN ANY
    |
  ANNA

上記の例では、ANN と ANNA をセットのように取得できるため、これがおそらくあなたのケースに役立つことがわかります。このタイプの ADT (Abstract Data Type) とともに、いくつかの置換コードを使用することができます。

詳細はこちら

于 2011-03-05T01:32:17.230 に答える