使用动态规划进行分词

Question

首先，我对Python非常陌生，所以如果我做错了什么，我在这里先说声抱歉。我被分配了这个问题：

我们想要为以下问题设计一个动态规划的解决方案：有一个字符的字符串，这个字符串可能是一些单词的序列，所有的空格都被去掉了。我们想找到一种方法，如果有的话，来插入空格，使得这些空格可以分隔出有效的英语单词。例如，"theouthevent" 可能来自于 “the you the vent”、“the youth event” 或者 “they out he vent”。如果输入是 "theeaglehaslande"，那么就没有这样的方式。你的任务是用两种不同的方法实现动态规划的解决方案：

• 自底向上的迭代版本
• 递归的记忆化版本

假设原始的单词序列没有其他标点符号（比如句号），没有大写字母，也没有专有名词 - 所有的单词都会在一个提供给你的字典文件中。

我遇到了两个主要问题：

1. 我知道这个问题可以并且应该在 O(N^2) 的时间复杂度内解决，但我觉得我的方法不是。
2. 查找表似乎没有添加所有的单词，这样就无法降低时间复杂度。

我希望得到：

1. 任何类型的输入（更好的方法、代码中你看到的错误、如何让查找表正常工作、如何使用布尔表来构建有效单词的序列）
2. 关于如何处理递归版本的一些想法，虽然我觉得一旦我能解决迭代的方案，我就能从中推导出递归的方案。

感谢任何人花时间和精力来帮助我，这总是让我很感激。

这是我的尝试：

#dictionary function returns True if word is found in dictionary false otherwise
def dictW(s):
    diction = open("diction10k.txt",'r') 
    for x in diction:
        x = x.strip("\n \r")
        if s == x:
            return True
    return False

def iterativeSplit(s):
    n = len(s)
    i = j = k = 0
    A = [-1] * n
    word = [""] * n
    booly = False
    for i in range(0, n):
        for j in range(0, i+1):
            prefix = s[j:i+1]
            for k in range(0, n):

                if word[k] == prefix:
                    #booly = True
                    A[k] = 1
                    #print "Array below at index k %d and word = %s"%(k,word[k])
                    #print A
            # print prefix, A[i]
            if(((A[i] == -1) or (A[i] == 0))):
                if (dictW(prefix)):
                    A[i] = 1
                    word[i] = prefix
                    #print word[i], i
                else:
                    A[i] = 0
    for i in range(0, n):
        print A[i]

Answer 1

这里有一个用C++写的解决方案。你可以先读一读，理解这个概念，然后再动手实现一下。

这个视频对理解动态规划的方法非常有帮助。

还有一种我觉得也很有用的方法是Trie数据结构。这是一种更好的解决上述问题的方式。

Answer 2

想看看如何在实际中进行英文单词分割吗？可以看看这个源代码，它是Python wordsegment模块的一个例子。这个模块稍微复杂一点，因为它使用了单词和短语的频率表，但它很好地展示了记忆化的方法。

特别是，segment这个函数展示了记忆化的做法：

def segment(text):
    "Return a list of words that is the best segmenation of `text`."

    memo = dict()

    def search(text, prev='<s>'):
        if text == '':
            return 0.0, []

        def candidates():
            for prefix, suffix in divide(text):
                prefix_score = log10(score(prefix, prev))

                pair = (suffix, prefix)
                if pair not in memo:
                    memo[pair] = search(suffix, prefix)
                suffix_score, suffix_words = memo[pair]

                yield (prefix_score + suffix_score, [prefix] + suffix_words)

        return max(candidates())

    result_score, result_words = search(clean(text))

    return result_words

如果你把score这个函数改成返回“1”对于字典里的单词，而返回“0”对于不在字典里的单词，那么你就可以简单地列出所有得分为正的候选单词来作为你的答案。