3

これは宿題のためなので、正確なコードは必要ありませんが、正しい方向に向けるのに役立つアイデアをいただければ幸いです。

宿題は、ボーグルを解くプログラムを書くことです。再帰的な部分は理解できたと思いますが、現在の文字列を辞書と比較する方法についての洞察が必要です。

辞書をセットまたはソートされたリストに保存する必要があります。私はセットを使用してこれを実装する方法を試みてきました。プログラムをより速く実行し、行き止まりの道をたどらないようにするために、現在の文字シーケンスがセット (辞書) 内の何かのプレフィックスとして存在するかどうかを確認する必要があります。

set.find() 操作は、文字列が完全に一致する場合にのみ true を返すことがわかりました。ラボの要件で、教授は次のように述べています。

「辞書がセットに格納されている場合、多くのデータ構造ライブラリは、検索している文字列に最も近いセット内の文字列を見つける方法を提供します。このような操作を使用して、特定の接頭辞を持つ単語をすばやく見つけることができます。 ."

私は今日、教授が説明していることを探していました。試行に関する多くの情報を見つけましたが、リストまたはセットを使用する必要があるため、うまくいかないと思います。

オートコンプリート機能のアルゴリズムも調べてみましたが、ここで達成しようとしているものは非常に複雑に思えます。

また、現在のシーケンスを辞書セットの単語と比較するために strncmp() を使用することも考えていましたが、この状況でそれがどのように機能するかはわかりません。

これがセットでどのように機能するかを調査し続けることは価値がありますか、それともソートされたリストを使用して辞書を保存してみるべきですか?

ありがとう

4

2 に答える 2

4

@Raymond Hettingerが彼の答えで言及しているように、トライここで非常に役立ちます。ただし、トライを書くのが苦手な場合や、既製のコンポーネントを使用したい場合は、単語がアルファベット順に並べられるかわいいプロパティを使用して、特定のプレフィックスが存在するかどうかを O(log n) 時間でチェックできます。考え方は次のとおりです。たとえば、接頭辞「thr」をチェックしているとします。お気付きかもしれませんが、接頭辞「thr」で始まるすべての単語は、文字列「thr」と「ths」の間に挟まれている必要があります。たとえば、thr ≤ through < ths、および thr ≤ throat < ths です。並べ替えられた巨大な配列に単語を格納している場合、バイナリ検索の修正版を使用して、最初の単語をアルファベット順に少なくとも選択したプレフィックスと、アルファベット順に最初の単語を少なくとも次のプレフィックス (プレフィックスの最後の文字を取得してインクリメントすることによって形成) を見つけることができます。これらが同じ単語である場合、それらの間には何もなく、接頭辞は存在しません。そうでない場合は、それらの間に何かがあり、プレフィックスがそれを行います。

std::vectorC++ を使用しているため、 aとstd::lower_boundアルゴリズムを使用できる可能性があります。すべての単語を a に入れ、のバージョンのstd::setを使用することもできます。例えば：setlower_bound

std::set<std::string> dictionary;
std::string prefix = /* ... */

/* Get the next prefix. */
std::string nextPrefix = prefix;
nextPrefix[nextPrefix.length() - 1]++;

/* Check whether there is something with the prefix. */
if (dictionary.lower_bound(prefix) != dictionary.lower_bound(nextPrefix)) {
    /* ... something has that prefix ... */
} else {
    /* ... no word has that prefix ... */
}

そうは言っても、トライはおそらくここではより良い構造です。興味がある場合は、DAWG (Directed Acyclic Word Graph)と呼ばれる別のデータ構造があります。これは、トライに似ていますが、使用するメモリが大幅に少なくなります。スタンフォード大学の CS 入門コース (Boggle が割り当てられています) では、学生は実際にその言語のすべての単語を含む DAWG を提供されます。三分探索木と呼ばれる別のデータ構造もあります。これは、二分探索木とトライの中間にあり、調べたい場合はここで役立つ可能性があります。

お役に立てれば！

于 2012-01-29T03:26:27.680 に答える
3

トライは、この問題に適したデータ構造です。

セットと辞書に限定されている場合は、プレフィックスを可能な一致の配列にマップする辞書を選択します。

asp -> aspberger aspire
bal -> balloon balance bale baleen ...
于 2012-01-29T03:02:41.483 に答える