python– 使用动态编程进行分词

概述所以首先我对Python很陌生,所以如果我做了一件糟糕的事情,我会抱歉这个帖子.我被分配了这个问题：我们想为下面的问题设计一个动态编程解决方案：有一个字符串可能是一系列单词,删除了所有空格,我们想找到一种方法,如果有的话,在其中插入空格单独的有效英语单词.例如,他们的故事可能来自“你的发泄”,“青年事件”或“他们出去发泄”.如果输入是theeaglehasl

所以首先我对Python很陌生,所以如果我做了一件糟糕的事情,我会抱歉这个帖子.我被分配了这个问题：

我们想为下面的问题设计一个动态编程解决方案：有一个字符串可能是一系列单词,删除了所有空格,我们想找到一种方法,如果有的话,在其中插入空格单独的有效英语单词.例如,他们的故事可能来自“你的发泄”,“青年事件”或“他们出去发泄”.如果输入是theeaglehaslande,则没有这样的方法.您的任务是以两种不同的方式实现动态编程解决方案：

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

假设单词的原始序列没有其他标点符号(例如句点),没有大写字母,也没有专有名称 – 所有单词都将在提供给您的字典文件中提供.

所以我有两个主要问题：

>我知道这可以而且应该在O(N ^ 2)中完成,我不认为我的是
>查找表不会添加所有单词,这样可以减少时间复杂度

我想要的是什么：

>任何类型的输入(更好的方法,你在代码中看到错误的东西,我如何使查找表工作,如何使用布尔表来构建一系列有效的单词)
>关于如何处理递归版本的一些想法,虽然我觉得一旦我能够解决迭代解决方案,我将能够设计递归版本.

一如既往地感谢任何人给予的任何时间和努力,我们总是感激不尽.

这是我的尝试：

#dictionary function returns True if word is found in dictionary false otherwisedef dictW(s):    diction = open("diction10k.txt",'r')     for x in diction:        x = x.strip("\n \r")        if s == x:            return True    return Falsedef 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]

最佳答案有关如何进行英语分词的另一个真实示例,请查看Python wordsegment module的source.它有点复杂,因为它使用单词和短语频率表,但它说明了记忆方法.

特别是,细分说明了备忘录方法：

def segment(text):    "Return a List of words that is the best segmenation of `text`."    memo = dict()    def search(text,prev='

如果您更换了乐谱功能,使其为词典中的单词返回“1”,如果没有则返回“0”,那么您只需枚举所有得分正确的候选人作为答案. 总结

以上是内存溢出为你收集整理的python – 使用动态编程进行分词全部内容，希望文章能够帮你解决python – 使用动态编程进行分词所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1207862.html