将没有空格的字符串解析为单个单词的数组。

Question

如果我有一串“蓝莓松饼”，那么解析它的最有效的方法是“蓝莓”、“松饼”、“是”、“疯狂”、“美味”。

我已经有了我的单词列表(mac的/usr/share/dict/ word )，但是我如何确保完整的单词存储在我的数组中，也就是:蓝莓，而不是两个单独的单词，蓝色和浆果。

Answer 1

尽管在某些情况下可能存在多种解释，而选择最佳解释可能会带来麻烦，但您总是可以使用这样一种相当天真的算法来处理：

WORDS = %w[
  blueberry
  blue
  berry
  fin
  fins
  muffin
  muffins
  are
  insane
  insanely
  in
  delicious
  deli
  us
].sort_by do |word|
  [ -word.length, word ]
end

WORD_REGEXP = Regexp.union(*WORDS)

def best_fit(string)
  string.scan(WORD_REGEXP)
end

这将解析您的示例：

best_fit("blueberrymuffinsareinsanelydelicious")
# => ["blueberry", "muffins", "are", "insanely", "delicious"]

请注意，这将跳过任何不匹配的组件。

Answer 2

这里有一个递归方法，在我缓慢的笔记本电脑上找到0.4s的正确句子。

• 它首先输入近100000个英语单词，并通过缩小大小对它们进行排序。
• 对于每个word，它都会检查text是否以它开头。
• 如果是这样的话，它将word从text中移除，将word保存在一个数组中，并递归地调用自己。
• 如果text是空的，就意味着已经找到了一个句子。
• 它使用一个惰性数组来停止第一个找到的句子。

text = "blueberrymuffinsareinsanelydeliciousbecausethey'rereallymoistandcolorful"

dictionary = File.readlines('/usr/share/dict/american-english')
                 .map(&:chomp)
                 .sort_by{ |w| -w.size }

def find_words(text, possible_words, sentence = [])
  return sentence if text.empty?
  possible_words.lazy.select{ |word|
    text.start_with?(word)
  }.map{ |word|
    find_words(text[word.size..-1], possible_words, sentence + [word])
  }.find(&:itself)
end

p find_words(text, dictionary)
#=> ["blueberry", "muffins", "are", "insanely", "delicious", "because", "they're", "really", "moist", "and", "colorful"]
p find_words('someword', %w(no way to find a combination))
#=> nil
p find_words('culdesac', %w(culd no way to find a combination cul de sac))
#=> ["cul", "de", "sac"]
p find_words("carrotate", dictionary)
#=> ["carrot", "ate"]

为了更快地查找，使用特瑞可能是个好主意。