从较小的短语重构原始句子? [英] Reconstruct original sentence from smaller phrases?

问题描述

我有一个原始句子

sent = "For 15 years photographer Kari Greer has been documenting wildfires and the men and women who battle them."

和短语:

phrases = [
  "For 15 years",
  "wildfires and the men and women who battle them",
  "has been documenting wildfires",
  "been documenting wildfires and the men and women who battle them",
  "documenting wildfires and the men and women who battle them",
  "them",
  "and the men and women who battle them",
  "battle them",
  "wildfires",
  "the men and women",
  "the men and women who battle them",
  "15 years",
  "photographer Kari Greer"
]

我想从短语中重建原始句子(不丢失任何单词)，并将选定的短语存储在新数组中，并保持顺序，以便得到:

I want to reconstruct the original sentence from the phrases (without loosing any words) and store selected phrases in the new array keeping the order so that I get:

 result = [
   "For 15 years",
   "photographer Kari Greer",
   "has been documenting wildfires",
   "and the men and women who battle them"
]

编辑:result具有最少数量的元素很重要.

Edit: It is important that the result has the minimum number of elements.

编辑:这是适用于更复杂情况的答案代码的版本:

Edit: Here is the version of the answer code that works for the more complex case:

 sent ="Shes got six teeth Pink says of her 13-month-old daughter but shes not a biter"      
 phrases = ["her 13-month-old daughter", "she", "says of her 13-month-old daughter", "a biter", "got six teeth", "Pink", "of her 13-month-old daughter", "s not a biter", "She", "six teeth", "s got six teeth", "Shes got six"] 

def shortest(string, phrases)
 string = string.gsub(/\.|\n|\'|,|\?|!|:|;|'|"|`|\n|,|\?|!/, '')
 best_result = nil
 phrases.each do |phrase|
  if string.match(/#{phrase}/)
    result = [phrase] + shortest(string.sub(/#{phrase}/, "").strip, phrases)
        best_result = result  if (best_result.nil? || result.size < best_result.size) # && string == result.join(" ")
      end
    end
  best_result || []
end

推荐答案

def shortest(string, phrases)
  best_result = nil
  phrases.each do |phrase|
    if string.match(/\A#{phrase}/)
      result = [phrase] + shortest(string.sub(/\A#{phrase}/, "").strip, phrases)
      best_result = result if (best_result.nil? || result.size < best_result.size) && string.match(Regexp.new("\\A#{result.join("\\s?")}\\Z"))
    end
  end
  best_result || []
end
result = shortest(sent.gsub(/\./, ""), phrases)

:更新了算法，以允许某些短语之间没有空格.

Updated the algorithm to allow some phrases to not have spaces between them.

这篇关于从较小的短语重构原始句子?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！