2

name:location のような文字列ペアのマップがあります (unix のような絶対位置 a la myfolder/)。いくつかの場所が与えられmyfolder/mysubfolder/myfileます。指定されたURLに最も適合するマップの場所を見つける方法は?

例として、次のようなマップがあります。

service1:myfolder/
service2:myfolder/mysubfolder/
service3:myfolder/myothersubfolder/
service4:myfolder/mysubfolder/myfile

値myfolder/mysubfolder/myfile/blablabla/(文字列) が与えられます。マップ内のどの項目に最も関連があるかを調べたいと考えています。検索結果はservice4、最も関連性の高いコンテンツを含むマップ アイテムとして表示されます。

では、与えられた文字列値によって、それが最も関連するマップ要素を見つける方法は?

私は C++ nube であり、そのようなものを実装する方法がわからないため、いくつかのコードを提供してください。

だから私は問題を少し単純化しました -今私が必要とするすべての関係は、与えられたパスがどれほど深いかということです。これは、文字列の場合、すべてのマップパスを反復するだけで認識できます。指定されたパスでアイテム パスが見つかりました。

4

3 に答える 3

2

次の 2 つのオプションがあります。

  1. 多くのクエリを実行する必要がある場合:
    1. 逆マップを作成するか、双方向マップを使用します。
    2. upper_bound を使用して最初の大きな要素を見つけ、
      • 共通接頭辞が最も長い要素が必要な場合は、この要素と前の (最後に小さい) 要素を確認し、共通接頭辞が長い要素を選択します。
      • 接頭辞である要素が必要な場合は、接頭辞である要素が見つかるまで戻ってスキャンします。
  2. クエリが 1 つだけ必要な場合は、単純な線形検索の方が高速です (逆マップの構築にはO(n log(n))が必要ですが、1 回の反復にはO(n)しかかかりません)。さらに、実装も簡単です。単純にマップを反復処理し、値ごとにプレフィックスの長さを計算し、これまでの最適な一致を記憶します ( を使用することをお勧めしましstd::max_elementたが、メトリックによる最大値が必要な場合は、比較演算子による最大値を実装します)。
于 2011-05-12T14:47:51.473 に答える
1

マップが次のように定義されている場合:

typedef std::map<std::string,std::string> MyMap;
MyMap my_map;

...そして、検索語は次のように定義されます。

std::string my_key_to_find = "service4";

...次に、このキーに関連付けられた値を次のように取得できます。

std::string found_val;
MyMap::const_iterator it = my_map.find(my_key_to_find);
if( it != my_map.end() )
  found_val = it->second;
else
  std::cout << "Key not found!\n";
于 2011-05-12T14:26:10.113 に答える
1

私があなたの質問を正しく理解している場合は、キーを値 (文字列) で検索する必要があります。一致する値は、提供された検索語の部分文字列です。一般的な問題 (つまり、任意の文字列とそのすべての部分文字列) として、これに対する簡単な解決策はないと思います。

ただし、例で値として使用される文字列には特定の構造があります (つまり、ファイル システム パス)。この構造を利用して、クリーンなソリューションを考え出すことができます。まず、双方向マップを作成します。次に、次のルックアップ プロセスを実装します。

  1. パスが空の場合、失敗します。
  2. リクエストパスに基づくマップ内の逆引き
  3. 見つかった場合は、関連する値を返します。
  4. パスから最後のコンポーネントをポップします。
  5. ループ。

リストが短い場合は、(キー、値) のペアのリストをループして、値が最も類似しているキー (つまり、共通の部分文字列が最も長い) を選択することもできます。

于 2011-05-12T14:48:36.810 に答える