ruby - 如何返回具有重复元素的 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"]