查找较大的句子两个词用最少的重叠

Question

我：

phrase = "will have to buy online pass from EA to play online but its in perfect condition" 

phrases = ["its", 
"perfect condition", 
"but its", 
"in perfect condition", 
"from EA", 
"buy online pass from EA", 
"to play online but its in perfect condition", 
"online", 
"online pass", 
"play online but its in perfect condition", 
"online but its", 
"EA", 
"will have to buy online pass from EA to play online but its in perfect condition", 
"have to buy online pass from EA to play online but its in perfect condition", 
"u", 
"pass", 
"to buy online pass from EA"] 

我想找到从阵列中两个短语是内6-10字限制，并有至少重叠字为单位的。 ..

喜欢的东西：

result = ["to buy online pass from EA", "play online but its in perfect condition"] 

将是完美的。什么是做到这一点的最好方法是什么？

Answer 1

split_phrases = phrases.map {|phrase| phrase.split } 

# find number of words of overlap between two word vectors 
def overlap(p1,p2) 
    s1 = p1.size 
    s2 = p2.size 

    # make p1 the longer phrase 
    if s2 > s1 
    s1,s2 = s2,s1 
    p1,p2 = p2,p1 
    end 

    # check if p2 is entirely contained in p1 
    return s2 if p1.each_cons(s2).any? {|p| p == p2} 

    longest_prefix = (s2-1).downto(0).find { |len| p1.first(len) == p2.last(len) } 
    longest_suffix = (s2-1).downto(0).find { |len| p2.first(len) == p1.last(len) } 

    [longest_prefix, longest_suffix].max 
end 

def best_two_phrases_with_minimal_overlap(wphrases, minlen=6, maxlen=10) 
    # reject too small or large phrases, evaluate every combination, order by word overlap 
    scored_pairs = wphrases. 
    select {|p| (minlen..maxlen).include? p.size}. 
    combination(2). 
    map { |pair| [ overlap(*pair), pair ] }. 
    sort_by { |tuple| tuple.first } 

    # consider all pairs with least word overlap 
    least_overlap = scored_pairs.first.first 
    least_overlap_pairs = scored_pairs. 
    take_while {|tuple| tuple.first == least_overlap }. 
    map {|tuple| tuple.last } 

    # return longest pair with minimal overlap 
    least_overlap_pairs.sort_by {|pair| pair.first.size + pair.last.size }.last 
end 

puts best_two_phrases_with_minimal_overlap(split_phrases).map{|p| p.join ' '} 

# to play online but its in perfect condition 
# to buy online pass from EA 

Answer 2

这个怎么样？

result = Array.new 
phrases.each do |p| 
    result.push(p) if(phrase.include?(p) && (6..10).include?(p.split.size)) 
end 
#remove entries that are substr of others 
result.each do |r| 
    result.delete(r) if (t = result.clone ; t.delete(r) ; t.any? {|v| v.include?(r)}) 
end 
print result.inspect 
#["to play online but its in perfect condition", "to buy online pass from EA"]