python - 使用动态规划的分词

Question

所以首先我是 Python 的新手，所以如果我做了一些糟糕的事情，我会在这篇文章的开头说一句抱歉。我被分配了这个问题:

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

• 迭代自下而上的版本
• 递归内存版本

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

所以我有两个主要问题:

1. 我知道这可以而且应该在 O(N^2) 内完成，但我不认为我的是
2. 查找表并没有添加所有看起来的单词，这样可以降低时间复杂度

我想要什么:

1. 任何类型的输入(更好的方法，您在代码中看到的错误，我如何使查找表工作，如何使用 bool 值表构建有效单词序列)
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

有关如何进行英语分词的另一个真实示例，请查看 source的 Python wordsegment module .它稍微复杂一些，因为它使用单词和短语频率表，但它说明了内存方法。

特别是，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”，那么您只需枚举所有得分为正的候选答案即可。