2

クイズを解いていて、アドバイスが必要です。

クイズの概要は次のとおりです。

ブックマークサービス（delicious、digg ...など）のデータを分析し、2つ以上の一般的なタグを持つURLのグループを抽出します。

  1. 各ブックマークデータには、1）user-id、2）url、および3）タグの配列が含まれています。
  2. すべてのタグのサイズは、すべてのURLと比較して比較的小さいです。つまり、人々は限られたセットでサイトをブックマークします
  3. URLに割り当てられたすべてのタグが異なります
  4. 異なるユーザーが同じURLをブックマークした場合は、それらからグループを作成しないでください（ただし、これはオプションの条件です。user_idを無視して、すべてのURLが異なると想定できます）。

例：

siteA - [tag1, tag2, tag3]
siteB - [tag1, tag2, tag4]
siteC - [tag1, tag3, tag5]
siteD - [tag1, tag2, tag6]

次の2つのURLグループが結果になります

(siteA, siteB, siteD), (siteA, siteC)

（siteA、siteB、siteD）は2つの共通タグ（tag1、tag2）を共有し、（siteA、siteC）も2つの共通タグ（tag1、tag3）を共有するためです。

--条件3,4および例が追加されました。ありがとう@btilly。

私の質問は

  1. どのように解決できるか（またはどのアルゴリズムを適用できるか）、実際に高速ですか？
  2. この質問と同様のアルゴリズムで解決できる代表的な問題はありますか？
4

1 に答える 1

1

新しいデータ構造を作成します。これは、タグごとに、そのタグを持つURLのハッシュです。

次に、タグのペアごとに、URLの少ない方を取得してそれらをウォークスルーし、ルックアップを実行して、タグのペアが他方にあるかどうかを確認し、そのタグのペアを共有するグループを生成します。

nタグごとに平均mURLのタグがある場合O(n * m)は、新しいデータ構造O(n * n * m)を生成し、グループを生成するのに時間がかかります。

于 2012-06-08T21:17:13.933 に答える