-1

假设我有一个像 'meetateight' 这样的字符串，我需要使用动态编程将它分割成有意义的单词，比如 'meet' 'at' 'eight'。

为了判断一个块/段“x = x1x2x3”有多“好”，给我一个黑盒子，在输入 x 上返回一个实数 quality(x)，这样： quality(x) 的大正值表示x接近英文单词，负数大表示x远离英文单词。

我需要帮助来设计相同的算法。

我尝试考虑一种算法，在该算法中，只要质量下降，我就会根据它们的质量和分段迭代地添加字母。但这在上面的例子中失败了，因为它切断了我而不是见面。

我需要更好的算法的建议。

谢谢

4

3 回答 3

0

您可以使用动态编程，并跟踪输入的每个前缀的分数，一次添加一个字母。每次添加字母时，请查看是否可以将任何后缀添加到您已经使用过的前缀上（选择得分最高的一个）。例如：

m = 0
me = 1
mee = 0
meet = 1
meeta = 1 (meet + a)
meetat = 1 (meet + at)
meetate = 1 (meet + ate)
meetatei = 1 (meetate + i)
meetateig = 0
meetateigh = 0
meetateight = 1 (meetat + eight)

要处理 0 和 1 之间的值，可以将它们相乘。还要保存您使用过的单词，以便您可以在最后拆分整个字符串。

于 2012-11-09T13:45:59.737 回答
0

使用英语词典构建一个Trie并向下导航如何使用所有可能的叶子路径扫描您的字符串（当您有多个选择时回溯）。

于 2012-11-09T13:35:10.193 回答
-1

我在我的博客上写了一个程序来做到这一点；这里太长了。基本思想是切掉构成单词的前缀，然后递归处理输入的其余部分，当无法拆分整个字符串时回溯。

于 2012-11-09T13:43:03.353 回答