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 語の制限内にあり、単語の重複が最も少ない 2 つのフレーズを見つけたいと思います...

何かのようなもの：

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

完璧だろう..それを行うための最良の方法は何ですか?

4

2 に答える 2

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 に答える
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 に答える