0

我有：

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

将是完美的.. 最好的方法是什么？

4

2 回答 2

0

这个怎么样？

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"]
于 2012-07-06T23:55:53.453 回答
0 
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
于 2012-07-07T00:23:22.783 回答