-
【说话处理惩罚与Python】4.7算法设计
添加时间:2013-5-26 点击量:天然说话处理惩罚傍边常用的算法
分而治之：
1、分成两半分给别的两小我来排序，他们又可以做同样的工作
2、获得两个排序号的卡片堆，归并成单一的排序堆
递归
在这里用一个例子来申明递归、构建一个字母查找树。
def
（trie，key，value）: if key: fist，rest=key[0]，key[1:] if fist not in trie: trie[first]={} （trie[first]，rest，value） else: trie[value]=value >>>trie = nltk.defaultdict（dict） >>>（trie， chat， cat） >>>（trie， chien， dog） >>>（trie， chair， flesh） >>>（trie， chic， stylish） >>>trie = dict（trie） ＃for nicerprinting >>>trie[c][h][a][t][value] cat >>>pprint.pprint（trie） {c: {h:{a: {t: {value: cat}}， {i: {r: {value: flesh}}}， i: {e: {n:{value: dog}}} {c: {value: stylish}}}}}动态规划
动态规划用于解决包含多个重叠的子题目的题目，不是反复策画这些子题目，而是简单的将他们的策画成果存储在一个查找表中。
题目靠山：S占一个音节，L占2个音节。若是想要机关4个音节的旋律，有如许几种景象。
V4=｛LL，SSL，SLS，LSS，SSSS｝
可以再次把这个凑集分成两种：
1、一种是以L为开端的子集：LL，LSS
2、以S为开端的子集：SSL，SLS，SSSS
依次递归往下分。
V4 =
LL，LSS
i.e. Lprefixed to eachitem of V2 = {L， SS}
SSL，SLS，SSSS
i.e. S prefixed to each item ofV3 = {SL，LS，SSS}
这里有四种办法，策画旋律
1、
def virahanka1（n）:
if n==0:
return []
elif n==1:
return [S]
else:
s = [S + prosody for prosody in virahanka1（n-1）]
l = [L + prosody for prosody in virahanka1（n-2）]
return s + l2、
def virahanka2（n）:
lookup = [[]， [S]]
for i in range（n-1）:
s = [S + prosodyfor prosody in lookup[i+1]]
l = [L + prosodyfor prosody in lookup[i]]
lookup.append（s + l）
return lookup[n]3、
def virahanka3（n，lookup={0:[]， 1:[S]}）:
if n not in lookup:
s = [S + prosody for prosody in virahanka3（n-1）]
l = [L + prosody for prosody in virahanka3（n-2）]
lookup[n] = s +l
return lookup[n]
4、
nltk import memoize
＠memoize
def virahanka4（n）:
if n==0:
return []
elif n==1:
return [S]
else:
s = [S + prosody for prosody in virahanka4（n-1）]
l = [L + prosody for prosody in virahanka4（n-2）]
return s + l法度运行的结果：
文艺不是炫耀，不是花哨空洞的文字堆砌，不是一张又一张的逆光照片，不是将旅行的意义转化为名牌包和明信片的物质展示；很多时候它甚至完全不美——它嘶吼、扭曲，它会痛苦地抽搐，它常常无言地沉默。——艾小柯《文艺是一种信仰》>>>virahanka1（4）
[SSSS， SSL， SLS， LSS， LL]
>>>virahanka2（4）
[SSSS， SSL， SLS， LSS， LL]
>>>virahanka3（4）
[SSSS， SSL， SLS， LSS， LL]
>>>virahanka4（4）
[SSSS， SSL， SLS， LSS， LL]
