查找较大的句子两个词用最少的重叠
问题描述:
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"]
将是完美的。什么是做到这一点的最好方法是什么?
答
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
答
这个怎么样?
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"]
+0
这找到了一个很好的答案,但没有排除其中的短语在头部和尾部重叠,但没有完全包含在彼此。 – dbenhur 2012-07-07 00:26:12
是类似的......你的意思是这一个? http://*.com/questions/11300921/reconstruct-original-sentence-from-smaller-phrases – Stpn 2012-07-06 22:56:46
任何两个不重叠?以任何顺序? – 2012-07-06 22:59:14
任何订单是在6
Stpn
2012-07-06 23:01:37