Как вернуть пересечение массива Ruby с повторяющимися элементами?(проблема с биграммами в коэффициенте кости)
-
05-07-2019 - |
Вопрос
Я пытаюсь написать сценарий коэффициента Дайса, но у меня возникла небольшая проблема с пересечением массива.
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 справляется с этим, но происходит потеря информации, которая может привести к нежелательным совпадениям в конкретном наборе данных, над которым я работаю.
Как я могу получить пересечение со всеми дубликатами?
Решение
Как 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"]
Другие советы
Из этой ссылки я считаю, что вы не должны использовать наборы Руби а скорее мультимножества, так что каждый биграмм подсчитывается, сколько раз он появляется. Может быть, вы можете использовать этот камень для мультимножеств. Это должно дать правильное поведение для повторяющихся биграмм.
Я некоторое время играл с этим, основываясь на ответе @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
но не верьте мне на слово, потому что я недостаточно проверял, чтобы быть в этом уверенным.