Как вернуть пересечение массива 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. Взгляните на здесь и здесь .

Если производительность не столь критична для вашего приложения, вы все равно можете сделать это, используя 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

С по этой ссылке Я считаю, что вы должны использовать не наборы Руби, а мультимножества, чтобы каждый биграмм подсчитывался, сколько раз он появляется. Может быть, вы можете использовать этот камень для мультимножеств. Это должно дать правильное поведение для повторяющихся биграмм.

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, но не верьте мне на слово, потому что я не проверил это достаточно, чтобы быть уверенным.