Was ist eine effiziente Möglichkeit, gemeinsame geteilte Sub-Arrays von mehreren Arrays nach Größe und Häufigkeit zu bewerten?

Question

Ich arbeite an einem Problem um Instagram Hashtags. Benutzer haben häufig "Bündel" von Hashtags, die sie kopieren und einfügen, wenn sie Bilder veröffentlichen. Verschiedene Pakete für verschiedene Themen.

So könnte ich meine "Things from the garden" Bundle, die ["Garten", "Beautifullawns", "Bäume outside", "Greenlondon"] und so weiter sein würde. Sie sind oft zwanzig bis dreißig Artikel lang.

Manchmal könnten sie mehrere davon haben, um die Dinge abwechslungsreich zu halten.

Was ich tun möchte, ist durch Blick auf Bilder, die sie gepostet haben, um ein Bündel von Tags zu empfehlen.

tun, dass ich mehrere Arrays von Tags haben würde, die sie zuvor verwendet haben:

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

mag ich würde größte gemeinsame Teilmengen von Einträgen für diese Arrays zu finden.

Also in diesem Fall wäre die größte Teilmenge ["a", "d", "e"] innerhalb dieser drei. Das ist einfach genug, um naiv zu werden, indem man etwas wie x & y & z verwendet.

Allerdings würde Ich mag ein Ranking dieser Teilmengen zu schaffen, auf der Grundlage ihrer Größe und Häufigkeit innerhalb aller Arrays in Betracht, so dass ich die am häufigsten verwendeten Bündel von Tags anzeigen kann:

[ 
    {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}, 
    ... 
] 

Vermutlich mit einer Beschränkung der Mindestgröße dieser Bündel, sagen wir zwei Elemente.

Ich verwende Elasticsearch für die Indexierung, aber ich habe festgestellt, dass der Versuch, dies mit Aggregationen zu tun, eine Herausforderung ist, also ziehe ich die Bilder in Ruby heraus und arbeite dann dort, um den Eintrag zu erstellen.

Als ersten Durchlauf habe ich alle diese Arrays durchlaufen und dann alle Teilmengen der anderen Arrays mit einem MD5-Hash-Schlüssel als eindeutigen Bezeichner gefunden. Dies begrenzt jedoch die Ergebnisse. Das Hinzufügen weiterer Durchgänge macht diesen Ansatz ziemlich ineffizient, vermute ich.

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}} 

einen zweiten Durchgang Hinzufügen wird dies zu einem besseren Ergebnis:

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}} 

Können Sie eine effiziente Möglichkeit, legen nahe, dieses Ranking von großen Untergruppen zu etablieren?

Answer 1

Anstatt eine Kreuzung von jedem Array mit jedem anderen Array zu machen, das schnell außer Kontrolle geraten könnte, wäre ich versucht, einen dauerhaften Index (in Elasticsearch?) Aller möglichen Kombinationen, die bisher gesehen wurden, beizubehalten mit einer Zählung ihrer Häufigkeit. Dann für jeden neuen Satz von Tags die Häufigkeitszählung für alle Unterkombinationen dieses Tags um 1 erhöhen.

Hier ist eine schnelle Skizze:

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 

was zur Folge hat:

{: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} 

Das ist nicht sehr gut skalieren kann entweder though.