0

非常に大きなデータ セット (100,000 要素から 250,000 要素の範囲) があり、現在、一連の単語を検索する目的でデータをベクターに格納しています。フレーズ (例: "on, para") を指定すると、関数は指定されたフレーズで始まるすべての単語を検索し、すべての一致をキューにプッシュする必要があります。

最初の単語を見つけるために、うまく機能しているように見えるバイナリ検索を使用していますが、最初の単語が見つかった後、行き詰まります。要素の前後を効率的に反復して、類似したすべての単語を見つけるにはどうすればよいですか? 入力はアルファベット順に並べられているため、要素が返される前または後に他のすべての一致が発生することがわかっています。<algorithm>たぶん、私が利用できる機能があるに違いないと感じています。関連するコードの一部を次に示します。

二分探索機能：

int search(std::vector<std::string>& dict, std::string in)
{
    //for each element in the input vector
    //find all possible word matches and push onto the queue
    int first=0, last= dict.size() -1;
    while(first <= last)
    {
        int middle = (first+last)/2;
        std::string sub = (dict.at(middle)).substr(0,in.length());
        int comp = in.compare(sub);
        //if comp returns 0(found word matching case)
        if(comp == 0) {
            return middle;
        }
        //if not, take top half
        else if (comp > 0)
            first = middle + 1;
        //else go with the lower half
        else
            last = middle - 1;
    }
    //word not found... return failure
    return -1;
}

のmain()

//for each element in our "find word" vector
for (int i = 0; i < input.size()-1; i++)
{
    // currently just finds initial word and displays
    int key = search(dictionary, input.at(i));
    std::cout << "search found " << dictionary.at(key) <<
                 "at key location " << key << std::endl;
}
4

3 に答える 3

0

順序付けられたベクトル (リスト) は確かにデータを格納する 1 つの方法ですが、アイテムを整理しておくには効率が犠牲になります。また、配列が静的か動的かについては言及していません。しかし、ソートされたデータを格納でき、ルックアップ時間が非常に長い他のデータ構造があります。

  • ハッシュ/マップ - アイテムをハッシュ/マップとして保存し、非常に高速にルックアップできますが、次と前を見つけるのは問題があります。
  • バイナリ ツリー/N-ary ツリー/B ツリー - 非常に優れた動的な挿入/削除パフォーマンス、およびルックアップ時間も良好で、ツリーが順序付けられているため、次/前の検索が安定しています。
  • ブルーム フィルター - 項目がコレクション内にあるかどうかを確認するだけでよい場合があります。ブルーム フィルターは誤検知が非常に少ないため、適切な選択です。

データを短いサブシーケンス (音節) に分解すると、音節のツリー、非常に高速な検索が可能になり、ツリーが順序付きリストまたはハッシュ/マップとして実装されているかどうかに応じて、見つけることもできる場合があります。次/前。

于 2013-10-07T20:36:39.333 に答える
0

フレーズごとではなく、サブフレーズごとにインデックスを作成する必要がありました。という言葉から始まりました。たとえば、dict-string "New York" の場合、"New York" と "York" の 2 つの文字列のインデックスを保持する必要があります。このアイデアを説明するオートコンプリート デモを参照してください。

http://olegh.cc.st/autocomplete.html

ご覧のとおり、このサブシステムは、250K 要素よりも大きい辞書をすばやく処理します。もちろん、二分探索は遅いので使用しません。代わりにハッシュを使用します。

于 2013-10-07T17:14:08.103 に答える