サイズと頻度で複数の配列の共通の共有サブ配列をランク付けする効率的な方法は何ですか？

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

私は、これらの配列のエントリの最大の共通サブセットを見つけるしたいと思います。

この場合、最大のサブセットは、これらの3つの中で["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}, 
    ... 
] 

：

しかし、私は、タグの最も一般的に使用されるバンドルを表示できるように、検討中のすべてのアレイ内での大きさと頻度に基づいてこれらのサブセットのランキングを作成したいのですが

おそらく、これらのバンドルの最小サイズに制限があり、たとえば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} 

は、ここでは簡単なスケッチです。