¿Cómo devolver una intersección de matriz Ruby con elementos duplicados? (problema con bigramas en el coeficiente de dados)

Question

Estoy intentando escribir el coeficiente de Dice, pero tengo un pequeño problema con la intersección de la matriz.

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

El problema es que, como & amp; elimina duplicados, obtengo cosas como esta:

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

puts approx_string_match(string1, string2) => 76.0%

Debe devolver 100.

El método uniq lo clava, pero hay pérdida de información, lo que puede traer coincidencias no deseadas en el conjunto de datos particular en el que estoy trabajando.

¿Cómo puedo obtener una intersección con todos los duplicados incluidos?

Answer 1

Como Yuval F dijo que debería usar multiset . Sin embargo, no hay multiset en la biblioteca estándar de Ruby. Consulte aquí y aquí .

Si el rendimiento no es tan crítico para su aplicación, aún puede hacerlo usando Array con un poco de código.

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

De este enlace creo que no deberías usar los conjuntos de Ruby sino multisets, de modo que cada bigrama se contabiliza el número de veces que aparece. Tal vez pueda usar esta gema para multisets. Esto debería dar un comportamiento correcto para los bigramas recurrentes.

Answer 3

Jugué con esto, basado en la respuesta de @pierr, por un tiempo y terminé con esto.

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 "]

Esto podría ser una especie de intersección multiset de a & amp; b pero no confíes en mi palabra porque no lo he probado lo suficiente para estar seguro.