如何返回具有重複元素的Ruby數組交集？ （問題與骰子係數的雙字母組）

Question

我試圖腳本骰子的係數，但我有一點與陣列相交的問題。

def bigram(string) 
    string.downcase! 
    bgarray=[] 
    bgstring="%"+string+"#" 
    bgslength = bgstring.length 
    0.upto(bgslength-2) do |i| 
    bgarray << bgstring[i,2] 
    end 
    return bgarray 
end 

def approx_string_match(teststring, refstring) 
    test_bigram = bigram(teststring) #.uniq 
    ref_bigram = bigram(refstring) #.uniq 

    bigram_overlay = test_bigram & ref_bigram 

    result = (2*bigram_overlay.length.to_f)/(test_bigram.length.to_f+ref_bigram.length.to_f)*100 

    return result 
end 

的問題是，作爲&刪除重複，我得到的東西是這樣的：

string1="Almirante Almeida Almada" 
string2="Almirante Almeida Almada" 

puts approx_string_match(string1, string2) => 76.0% 

它應該返回100

的uniq的方法指甲，但沒有信息丟失，這可能會在我工作的特定數據集中帶來不需要的匹配。

我怎樣才能與所有重複的交集包括在內？

Answer 1

正如Yuval F說，你應該使用multiset。然而，在Ruby的標準庫中沒有multiset，在看採取在here和here。

如果性能是不是爲您的應用程序的關鍵，你仍然可以使用Array帶有一點點的代碼做到這一點。

def intersect a , b 
    a.inject([]) do |intersect, s| 
     index = b.index(s) 
     unless index.nil? 
     intersect << s 
     b.delete_at(index) 
     end 
     intersect   
    end 
end 

a= ["al","al","lc" ,"lc","ld"] 
b = ["al","al" ,"lc" ,"ef"] 
puts intersect(a ,b).inspect #["al", "al", "lc"] 

Answer 2

從this link我相信你不應該使用Ruby的集合，而是使用多集合，這樣每個二元組都會被計算出來的次數。也許你可以使用this gem進行多重播放。這應該爲循環bigrams提供正確的行爲。

Answer 3

我玩了這個，基於@pierr的回答，一會兒結束了。

a = ["al","al","lc","lc","lc","lc","ld"] 
b = ["al","al","al","al","al","lc","ef"] 
result=[] 
h1,h2=Hash.new(0),Hash.new(0) 
a.each{|x| h1[x]+=1} 
b.each{|x| h2[x]+=1} 
h1.each_pair{|key,val| result<<[key]*[val,h2[key]].min if h2[key]!=0} 
result.flatten 

=> ["al", "al", "lc"]

這可能是一種a & b多集相交的，但因爲我沒有測試它足以確保不要把我的話。