1

200本の弦を持っています。各文字列には、他のすべての文字列との関係 (0 と 1 の間の浮動小数点数で測定) があります。この関係は双方向です。つまり、関係 A/B == 関係 B/A です。これにより、n(n-1)/2、つまり 19,800 の関係が得られます。

私がやりたいのは、これらのリレーションシップをルックアップ テーブルに格納して、任意の 2 つの単語からリレーションシップの値をすばやく見つけられるようにすることです。

私は c++ を使用しているので、おそらく std::map を使用して LUT を保存します。問題は、この目的に使用するのに最適なキーは何かということです。

キーは一意である必要があり、両方の単語からすばやく計算できる必要があります。

私のアプローチは、単語のペアごとに一意の識別子を作成することです。たとえば、"apple" と "orange" という単語が与えられた場合、それらを "appleorange" (アルファベット順、小さい方から) として結合し、それをキー値として使用します。

これは良い解決策ですか、それとももっと賢い方法を提案できますか? :)

4

5 に答える 5

1

どのくらい「迅速に」迅速ですか？2つの単語の順序を気にしない場合は、次のようなマップを試すことができます。

std::map<std::set<std::string>, double> lut;

ここで、キーはset2つの単語のいずれかであるため、「apple」と「orange」を挿入すると、順序は「orange」「apple」と同じになりset、less than演算子がサポートされている場合、キーとして機能できます。地図で。注：順序が重要であるため、意図的にキーにaを使用しませんでしたpair...

私はこのようなかなり基本的なものから始めて、プロファイルを作成し、ルックアップなどがどれほど速い/遅いかを確認してから、よりスマートなことをする必要があるかどうかを確認します...

于 2011-01-17T09:20:03.830 に答える
1

基本的に、パラメーターの順序が重要ではないという追加のプロパティを使用して、2 つのパラメーターの関数を記述しています。

順序を変更するときに単語間にあいまいさがなければ、あなたのアプローチはうまくいきます (可能性のあるあいまいさを取り除くために、2 つの単語の間にコマなどを入れることをお勧めします)。任意の 2D 配列も機能します。

関係の値を見つけようとする前に、おそらく各キーワードを(単純なマップを使用して)一意の識別子に変換しますが、提案しているものとあまり変わりません。

于 2011-01-17T09:10:54.723 に答える
1

boost/tr1 が受け入れられる場合は、文字列のペアをキーとして unordered_map を使用します。その場合の主な問題は、文字列の順序はどうなるかということです。これは、語彙の最初の文字列で始まるハッシュ関数によって処理できます。

注意: これはデザインの問題を読んだ後の単なる提案であり、調査ではありません。

于 2011-01-17T09:11:28.083 に答える
0

200個の文字列が配列内にある場合、20,100個の類似性値も1次元配列内にある可能性があります。それはすべて、その配列にインデックスを付ける方法にかかっています。xとyは、類似性が必要な文字列のインデックスであると言います。必要に応じてxとyを交換してy>=xにし、大きな配列のエントリi = x + y（y + 1）/2を調べます。

（x、y）of（0,0）、（0,1）、（1,1）、（0,2）、（1,2）、（2,2）、（0,3）、（1 、3）...エントリ0,1,2,3,4,5,6,7..に移動します。

したがって、これはスペースを最適に使用し、マップよりも高速なルックアップを提供します。C ++を使用しているので、効率は少なくとも少し重要だと思います。

[y = xの自己相似値に関心がない場合は、代わりにi = x + y（y-1）/2を使用してください]。

于 2011-01-17T10:57:13.603 に答える
0

200個の文字列を使用して並べ替えられた配列を作成する場合は、2分探索して、2つの文字列の一致するインデックスを見つけ、2D配列でそれらの2つのインデックスを使用して関係の値を見つけることができます。

于 2011-01-17T09:21:02.490 に答える