从较大的句子中找出重叠最少的两个短语

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