使用动态规划进行词语分割

Question

首先，我很新于Python，所以如果我做错了什么，请原谅。我们想设计一个动态规划解决方案来解决以下问题：有一个字符序列，可能是去除了所有空格的单词序列，我们想找到一种方法（如果有的话），将空格插入其中，以分隔有效的英语单词。例如，theyouthevent 可能是“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]

- xe0

---

去掉 x = x.strip("\n \r") 并将 if s == x 替换为 if s.find(x) != -1 应该会加快速度。当然，这不会给你精确的匹配，例如如果单词是 'hello'，则会找到 'hell'。 - confused_at_times

有趣。这是字符串“lukelucklikeslakes”的两个版本的结果。我的版本： real 0m15.266s user 0m2.858s sys 0m0.031s你的版本： real 0m12.906s user 0m3.264s sys 0m0.030s - xe0

是的。我想直接字符串比较总是比尝试在另一个字符串中查找字符串序列更快。我假设删除strip调用会有益处。但是，是否有任何原因需要strip调用？您能否尝试使用10倍的条目再次进行测试？此外，您可能希望在for循环开始之前打开并存储文件中的行，因为现在您正在重复执行该操作i * j * k次。 - confused_at_times

Answer 1

以下是关于英文单词分割的另一个真实世界示例，可以查看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”，那么您只需枚举所有得分为正的候选答案即可。

- GrantJ

Answer 2

这里是C++的解决方案。阅读并理解概念，然后实现。

这个视频对于理解DP方法非常有帮助。

我认为还有一种方法可以帮助解决上述问题，那就是Trie数据结构。这是一种更好的解决方法。

- divyum