크기 및 빈도별로 여러 배열의 공통 공유 하위 배열의 순위를 매기는 효율적인 방법은 무엇입니까?

Question

Instagram 해시 태그 관련 문제를 해결하기 위해 노력하고 있습니다. 사용자는 종종 이미지를 게시 할 때 복사하여 붙여 넣는 해시 태그의 "번들"을 가지고 있습니다. 다른 주제에 대한 다른 묶음.

그래서 "정원에서 가져온 것"번들, "정원", "beautifullawns", "treesoutside", "greenlondon"등이있을 수 있습니다. 종종 20 ~ 30 개의 항목이 있습니다.

때로는 다양한 것들을 유지하기 위해 이들 중 몇 가지가있을 수 있습니다.

내가 원하는 것은 게시 한 과거 이미지를보고, 사용할 태그 묶음을 추천하는 것입니다.

나는 그들이 이전에 사용한 태그의 몇 가지 배열을 가질 것이라는 점을 수행합니다

x = ["a", "b", "c", "d", "e"] 
y = ["a", "b", "d", "e", "f", "g"] 
z = ["a", "c", "d", "e", "f", "h"] 
... 

나는이 배열에 대한 항목의 가장 큰 공통의 부분 집합을 찾을 싶습니다.

그래서이 경우 가장 큰 부분 집합은 [ "a", "d", "e"]가됩니다. 그것은 x & y & z과 같은 것을 사용하여 순진하게 달성하기에 충분합니다.

[ 
    {bundle: ["a","d","e"], frequency: 3, size: 3}, 
    {bundle: ["e","f"], frequency: 2, size: 2}, 
    {bundle: ["a","b"], frequency: 2, size: 2}, 
    {bundle: ["b","d"], frequency: 2, size: 2}, 
    ... 
] 

:

그러나, 나는 내가 태그의 가장 일반적으로 사용되는 번들을 표시 할 수 있도록, 고려 배열의 모든 내에서의 크기와 빈도에 따라이 부분 집합의 순위를 작성하고 싶습니다

아마도 이러한 번들의 최소 크기에 대한 제한으로 두 가지 항목을 말하십시오.

인덱싱에 Elasticsearch를 사용하고 있지만 집계를 사용하여이를 시도하는 것이 어렵다는 것을 알았습니다. 따라서 이미지를 Ruby로 가져 와서 목록을 만들 때 작업하고 있습니다.

첫 번째 단계에서 나는 모든 배열을 반복 한 다음 MD5 해시 키를 고유 식별자로 사용하여 다른 배열의 모든 하위 집합을 찾습니다. 그러나 이것은 결과를 제한합니다. 추가 패스를 추가하면이 접근법이 상당히 비효율적입니다.

require 'digest' 

x = ["a", "b", "c", "d", "e"] 
y = ["a", "b", "d", "e", "f", "g"] 
z = ["a", "c", "d", "e", "f", "h"] 


def bundle_report arrays 
    arrays = arrays.collect(&:sort) 
    working = {} 
    arrays.each do |array| 
    arrays.each do |comparison| 
     next if array == comparison 
     subset = array & comparison 
     key = Digest::MD5.hexdigest(subset.join("")) 
     working[key] ||= {subset: subset, frequency: 0} 
     working[key][:frequency] += 1 
     working[key][:size] = subset.length 
    end 
    end 
    working 
end 

puts bundle_report([x, y, z]) 
=> {"bb4a3fb7097e63a27a649769248433f1"=>{:subset=>["a", "b", "d", "e"], :frequency=>2, :size=>4}, "b6fdd30ed956762a88ef4f7e8dcc1cae"=>{:subset=>["a", "c", "d", "e"], :frequency=>2, :size=>4}, "ddf4a04e121344a6e7ee2acf71145a99"=>{:subset=>["a", "d", "e", "f"], :frequency=>2, :size=>4}} 

두 번째 패스를 추가하면이 더 나은 결과를 가져옵니다

def bundle_report arrays 
    arrays = arrays.collect(&:sort) 
    working = {} 
    arrays.each do |array| 
    arrays.each do |comparison| 
     next if array == comparison 
     subset = array & comparison 
     key = Digest::MD5.hexdigest(subset.join("")) 
     working[key] ||= {subset: subset, frequency: 0} 
     working[key][:frequency] += 1 
     working[key][:size] = subset.length 
    end 
    end 

    original_working = working.dup 

    original_working.each do |key, item| 
    original_working.each do |comparison_key, comparison| 
     next if item == comparison 
     subset = item[:subset] & comparison[:subset] 
     key = Digest::MD5.hexdigest(subset.join("")) 
     working[key] ||= {subset: subset, frequency: 0} 
     working[key][:frequency] += 1 
     working[key][:size] = subset.length 
    end 
    end 
    working 
end 

puts bundle_report([x, y, z]) 
=> {"bb4a3fb7097e63a27a649769248433f1"=>{:subset=>["a", "b", "d", "e"], :frequency=>2, :size=>4}, "b6fdd30ed956762a88ef4f7e8dcc1cae"=>{:subset=>["a", "c", "d", "e"], :frequency=>2, :size=>4}, "ddf4a04e121344a6e7ee2acf71145a99"=>{:subset=>["a", "d", "e", "f"], :frequency=>2, :size=>4}, "a562cfa07c2b1213b3a5c99b756fc206"=>{:subset=>["a", "d", "e"], :frequency=>6, :size=>3}} 

당신이 큰 부분 집합의 순위를 설정하는 효율적인 방법을 제안 할 수 있습니까?

Answer 1

다른 모든 배열과 모든 배열의 교집합을 수행하는 것이 아니라 빨리 사라질 수 있으므로 지금까지 볼 수있는 모든 가능한 조합 중에서 영구 색인 (Elasticsearch?)을 유지하려고합니다. 주파수의 카운트와 함께. 그런 다음 모든 새로운 태그 집합에 대해 해당 태그의 모든 하위 조합에 대해 빈도 카운트를 1 씩 증가시킵니다.

require 'digest' 

def bundle_report(arrays, min_size = 2, max_size = 10) 

    combination_index = {} 

    arrays.each do |array| 

    (min_size..[max_size,array.length].min).each do |length| 

     array.combination(length).each do |combination| 

     key = Digest::MD5.hexdigest(combination.join('')) 

     combination_index[key] ||= {bundle: combination, frequency: 0, size: length} 
     combination_index[key][:frequency] += 1 

     end 

    end 

    end 

    combination_index.to_a.sort_by {|x| [x[1][:frequency], x[1][:size]] }.reverse 

end 

input_arrays = [ 
    ["a", "b", "c", "d", "e"], 
    ["a", "b", "d", "e", "f", "g"], 
    ["a", "c", "d", "e", "f", "h"] 
] 

bundle_report(input_arrays)[0..5].each do |x| 
    puts x[1] 
end 

결과 :이 비록 아주 잘하거나 확장하지 않을 수 있습니다

{:bundle=>["a", "d", "e"], :frequency=>3, :size=>3} 
{:bundle=>["d", "e"], :frequency=>3, :size=>2} 
{:bundle=>["a", "d"], :frequency=>3, :size=>2} 
{:bundle=>["a", "e"], :frequency=>3, :size=>2} 
{:bundle=>["a", "d", "e", "f"], :frequency=>2, :size=>4} 
{:bundle=>["a", "b", "d", "e"], :frequency=>2, :size=>4} 

여기에 빠른 스케치입니다.