0

単語の膨大なコレクションを格納するプレフィックス ツリーがあります。現在、「a」という一般的な接頭辞を持つすべての単語を見つけたい場合は、最初に a を含む最初のノードを取得し、次に最初のノードの子ノードで深さ優先方式で徹底的に検索します。このアイデアは素朴で簡単に見えますが、共通の接頭辞を持つ単語の数が非常に多い (>20K) 場合、実際には非常に遅くなります。共通の接頭辞で始まるすべての単語を効率的に取得する他の方法はありますか? または、他のデータ構造を採用する必要がありますか? よろしくお願いします。

EDIT1 基本的に、すべてのノードにアクセスして文字を段階的に追加することにより、完全な単語を作成しています。すべての単語は、後でベクター コンテナーに格納されます。はい、再帰的な実装があります。

EDIT2

vector<int> getNonEmptyEdgeIndices(Node* parent) {
    vector<int> indices;
    for(int i=0; i<EDGE; i++) {
        if (parent->edges[i] != NULL) {
            indices.push_back(i);
        }
    }
    return indices; 
}

vector<string> getSubsequentStrings(vector<string> wordsStartingWith, Node* node, string prefix) {
    vector<int> indices = getNonEmptyEdgeIndices(node);

    // push the word to the container if node is a leaf 
    if (indices.empty()) {
        wordsStartingWith.push_back(prefix);
        return wordsStartingWith;
    }

    // if frequency is set in node, push the word but still continue recursion
    if (node->frequency != 0) {
        wordsStartingWith.push_back(prefix);
    }

    // look all the children of the node
    for(unsigned int i=0; i<indices.size(); i++) {
        string newPrefix = prefix + getNodeChar(indices[i]);
        Node* child = node->edges[indices[i]];

        // recursively get the prefix for all children
        wordsStartingWith = getSubsequentStrings(wordsStartingWith, child, newPrefix);  
    }

    return wordsStartingWith;
}

vector<string> Trie::getWordsStartingWith(string prefix) {
    vector<string> wordsStartingWith;
    Node* lastNode = getLastNode(prefix);

    if (lastNode != NULL) {
        wordsStartingWith = getSubsequentStrings(wordsStartingWith, lastNode, prefix);
    }
    return wordsStartingWith;
}

編集3 解決!!! 実際、私の実装には問題がありました。私はこの巨大なベクトル文字列コンテナを再帰呼び出しで渡していましたが、これが実際の問題でした。皆さん、親切なアドバイスをありがとうございます。

4

1 に答える 1

0

実際、TRIE+DFT はすでに十分なソリューションです。その時間計算量はO(M+B^M)、Mは単語の最大長であり、Bは可能な文字の定数 (通常はB=26) です。これは指数関数的ですが、実際には、TRIE ツリーが非常にまばらで、数が少ないため、思ったよりもはるかに高速になる可能性がありますM。

より簡単な (より良いとは限りません) 解決策は、すべての単語を配列に並べ替えることです。次に、英語の辞書を使用するのと同じように、ターゲット prefix を持つ最初と最後の単語の配列をバイナリ検索することで、必要なものを取得できます。並べ替えには単語数が必要でO(NlogN)、検索には単語数が必要です。多項式です。O(MlogN)N

本当にスピードが必要な場合は、ほとんどの場合、交換のためにメモリ容量を支払うことができます。この場合、TRIE ツリーの構築中にポインターによって各単語をすべてのプレフィックス ノードにリンクできます。O(M+N)次に、時間の複雑さが非常に高速になるまで削減されます。しかし一方で、それは のスペースの複雑さを必要としO(NM)ます。平均して 5 文字の単語が 100 万個あると仮定すると、ポインタに約 150KB のメモリを使用することになります。

于 2013-12-24T23:42:09.447 に答える