2008-12-17 77 views
1

我想了解有助於識別重疊數據集之間的共性和差異的算法信息。什麼算法計算一組集合中常見元素的頻率?

使用計算器的標籤系統爲例:

比方說,這個問題已經給出了5個標籤。假設有1000個其他問題至少有一個這樣的標籤。在這1000個問題中,有多少這些問題的標籤有共同點,我的原始帖子沒有?

描述此的另一種更簡單的方法是自動提示標籤系統:

「你用[5個標籤我選擇]標記了你的問題的其他similiar問題都標有[標籤可能是名單感興趣。其中的標籤可能會感興趣]經常存在的不在我的原單列表標籤。

代碼示例在C#如果可能的話:)

回答

0

我不知道任何特定的算法和數據結構,但我可以建議的處理這個基本的方法:

假設:每個入口有五種獨特的標記。

  • 收集包含五個標籤中的任何一個(沒有重複)的所有條目。
  • 對於列表中的每個條目,請爲每個標記使用關聯數組(散列表),並將值遞增。
  • 對於數組中的每個條目,將標籤名稱追加到該數組的條目索引中。

在(馬虎)僞代碼,使用兩個環路(如果可能):

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 

這將產生連鎖的標記名稱的稀疏陣列(好吧,我不包括分離器,但嘿它是僞代碼:-)。保持最高的數字,然後迭代以獲得最佳建議。

(緩存優化,但注意更新)

Paul。

1

查找到下注的漢明距離[名單。這是在字符串上定義的漢明距離,即將一個字符串轉換爲anot所需的編輯操作數她的。

您也可以使用等價類的部分順序並設置包含:當問題A和B具有完全相同的標記集合直至重新排序時,它們相等,設置聯合,設置差異並設置交集,然後爲<和>比較定義部分訂單。