algorithm - セットのコレクション内の共通要素の頻度をカウントするアルゴリズムは?

Question

重複するデータのセット間の共通点と相違点を識別するのに役立つアルゴリズムに関する情報が欲しいです。

例として、stackoverflow のタグシステムを使用します。

この質問に 5 つのタグが付けられたとします。これらのタグの少なくとも 1 つを持つ他の 1000 の質問があるとします。これらの 1000 の質問のうち、元の投稿にはないタグが共通している質問はいくつありますか?

これを説明するもう 1 つの簡単な方法は、自動提案タグ付けシステムです。

「[選択した 5 つのタグ] で質問にタグを付けました。他の同様の質問には [関心がある可能性のあるタグのリスト] がタグ付けされました。[関心がある可能性のあるタグのリスト] は、頻繁に発生するタグで私の元のリスト。

可能であればC#でのコード例:)

score 1 · Accepted Answer

賭けハミング距離を調べます。これは、ある文字列を別の文字列に変換するのに必要な編集操作の回数として、文字列に対して定義されるハミング距離です。

また、等価クラスとセットの包含の半順序を潜在的に使用することもできます: 質問 A と B が並べ替えまでまったく同じタグのセットを持っている場合、それらは等しく、和集合、差集合、共通部分を設定し、半順序を定義します< および > 比較用。

score 0 · Accepted Answer

特定のアルゴリズムやデータ構造はわかりませんが、これを処理する基本的な方法を提案できます。

仮定：各エントリには5つの一意のタグがあります。

（ずさんな）擬似コードでは、（可能であれば）2つのループを使用します。

for each entry
    if any tag in original_tags
        tag_list[tag]++
end

for next in tag_list
    tag_count[tag_list[next]] += next
end

これにより、連結されたタグ名のまばらな配列が生成されます（わかりました、区切り文字は含まれていませんが、疑似コードです:-)。最大数を維持してから、逆方向に繰り返して最良の提案を探します。

（最適化するためにキャッシュしますが、更新を監視します）

ポール。

2 に答える 2