6

所以首先我对 Python 很陌生，所以如果我做了一些糟糕的事情，我会在这篇文章的开头表示抱歉。我被分配了这个问题：

我们想为以下问题设计一个动态规划解决方案：有一个字符串，它可能是一个删除所有空格的单词序列，我们想找到一种方法，如果有的话，在其中插入空格分开有效的英文单词。例如，青年事件可能来自“the you the vent”、“the Youth event”或“they out he vent”。如果输入是eaglehaslande，那么就没有这种方法。您的任务是以两种不同的方式实现动态规划解决方案：

  • 迭代自下而上版本
  • 递归记忆版本

假设原始单词序列没有其他标点符号（例如句点）、大写字母和专有名称 - 所有单词都将在提供给您的字典文件中可用。

所以我有两个主要问题：

  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]
4

2 回答 2

4

有关如何进行英语分词的另一个真实示例，请查看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”，那么您只需枚举所有得分为正的候选人作为您的答案。

于 2015-09-02T23:10:24.840 回答
0

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

该视频对理解 DP 方法非常有帮助。

我觉得可以提供帮助的另一种方法是Trie数据结构。这是解决上述问题的更好方法。

于 2015-04-15T19:22:35.320 回答