NLTK-Chapter8.4中合适语句规矩的字串表-动态规划算法的申明
添加时间:2013-5-17 点击量:
一些前提数据：
tokens = [I， shot， an， elephant， in， my， pajamas]
- tokens为将要研究的一句英词句子。
index={（DeT， N）: NP，
（Det， N， PP）: NP，
（NP， VP）: S，
（P， NP）: PP，
（V， NP）: VP，
（VP， PP）: VP，
（I，）: NP，
（an，）: Det，
（elephant，）: N，
（in，）: P，
（my，）: Det，
（pajamas，）: N，
（shot，）: V}
- index为文法的描述。
- numtokens=7（len（tokens））为句子中单词的数量
图8.6中为图表的数据布局
在这个算法傍边，有一个代表图表数据布局的二维表，我们把他定名为WFST。
经过下面的初始化函数，对WFST进行初始化：
def init_wfst（tokens，grammar）:
numtokens=len（tokens）
wfst=[
[None for i in range（numtokens+1）] for j in range（numtokens+1）
]
for i in range（numtokens）:
productions=grammar.productions（rhs=tokens[i]）
wfst[i][i+1]=productions[0].lhs（）
return wfst
经过初始化之后，我们可以打印WFST，发明已经变成了下面这种景象：
[[None， NP， None， None， None， None， None， None]，
[None， None， V， None， None， None， None， None]，
[None， None， None， Det， None， None， None， None]，
[None， None， None， None， N， None， None， None]，
[None， None， None， None， None， P， None， None]，
[None， None， None， None， None， None， Det， None]，
[None， None， None， None， None， None， None， N]，
[None， None， None， None， None， None， None， None]]
WFST1 2 3 4 5 6 7
0 NP . . . . . .
1 . V . . . . .
2 . . Det . . . .
3 . . . N . . .
4 . . . . P . .
5 . . . . . Det .
6 . . . . . . N
上方两个是等价的，只不过下面的这个图更直观，好懂得。每相邻两个节点之间是一个词，他们都有本身的词性。
然则这些还远远不敷，为了可以或许更好的表现文法，还须要归约操纵，将一开端的图表变成如下如许的情势：
就须要我们有一种算法，去遍历我们如今有的图表布局，来完成这个操纵。
书中已经给出了算法的实现，我们须要重视的是，这是一个三角矩阵，不须要每个处所都遍历，同时，算法的难点是，要实现不合的单词数量的跨度，去完成图表WFST的赋值。
书中给出的算法代码为：
def complete_wfst（wfst，tokens， grammar，trace=False）:
index = dict（（p.rhs（），p.lhs（）） for p in grammar.productions（））
numtokens= len（tokens）
for span in range（2， numtokens+1）:
for start in range（numtokens+1-span）:
end = start + span
for mid in range（start+1， end）:
nt1，nt2 = wfst[start][mid]，wfst[mid][end]
if nt1 and nt2 and （nt1，nt2） in index:
wfst[start][end]= index[（nt1，nt2）]
if trace:
print [％s] ％3s[％s] ％3s[％s] ==>[％s] ％3s[％s] ％（start， nt1， mid，nt2，end， start， index[（nt1，nt2）]， end）
return wfst
嵌套了很多的轮回，其实经过细心解析，此算法并不难懂得。为了更好的懂得，可以本身手动演示一下就能懂得算法的内涵，若是各位读者看着很难懂得，本身走一下法度的步调就很轻易懂得了：
span=2:＃当值为2的时辰，搜检两个词之间有没有关系
＃range（numtokens+1-span=6）（0~5）
start=0:
end=start+span=0+2=2
＃range（start+1，end）（0+1，2）
mid=1:
nt1=wfst[0][1]，nt2=[1][2]
start=1:
start=2:
end=start+span=2+2=4
＃range（start+1，end）（3，4）
mid=3:
nt1=wfst[2][3]，nt2=[3][4]
start=3:
start=4:
start=5:
span=3:
＃range（numtokens+1-span=5）（0~4）
start=0:
end=start+span=0+3=3
＃range（start+1，end）（0+1，3）
mid=1:
nt1=wfst[0][1]，nt2=wfst[1][3]
mid=2:
nt1=wfst[0][2]，nt2=wfst[2][3]
start=1:
start=2:
start=3:
span=4:
span=5:
span=6:
span=7:
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
一些前提数据：
tokens = [I， shot， an， elephant， in， my， pajamas]
- tokens为将要研究的一句英词句子。
index={（DeT， N）: NP，
（Det， N， PP）: NP，
（NP， VP）: S，
（P， NP）: PP，
（V， NP）: VP，
（VP， PP）: VP，
（I，）: NP，
（an，）: Det，
（elephant，）: N，
（in，）: P，
（my，）: Det，
（pajamas，）: N，
（shot，）: V}
- index为文法的描述。
- numtokens=7（len（tokens））为句子中单词的数量
图8.6中为图表的数据布局
在这个算法傍边，有一个代表图表数据布局的二维表，我们把他定名为WFST。
经过下面的初始化函数，对WFST进行初始化：
def init_wfst（tokens，grammar）:
numtokens=len（tokens）
wfst=[
[None for i in range（numtokens+1）] for j in range（numtokens+1）
]
for i in range（numtokens）:
productions=grammar.productions（rhs=tokens[i]）
wfst[i][i+1]=productions[0].lhs（）
return wfst
经过初始化之后，我们可以打印WFST，发明已经变成了下面这种景象：
[[None， NP， None， None， None， None， None， None]，
[None， None， V， None， None， None， None， None]，
[None， None， None， Det， None， None， None， None]，
[None， None， None， None， N， None， None， None]，
[None， None， None， None， None， P， None， None]，
[None， None， None， None， None， None， Det， None]，
[None， None， None， None， None， None， None， N]，
[None， None， None， None， None， None， None， None]]
WFST1 2 3 4 5 6 7
0 NP . . . . . .
1 . V . . . . .
2 . . Det . . . .
3 . . . N . . .
4 . . . . P . .
5 . . . . . Det .
6 . . . . . . N
上方两个是等价的，只不过下面的这个图更直观，好懂得。每相邻两个节点之间是一个词，他们都有本身的词性。
然则这些还远远不敷，为了可以或许更好的表现文法，还须要归约操纵，将一开端的图表变成如下如许的情势：
就须要我们有一种算法，去遍历我们如今有的图表布局，来完成这个操纵。
书中已经给出了算法的实现，我们须要重视的是，这是一个三角矩阵，不须要每个处所都遍历，同时，算法的难点是，要实现不合的单词数量的跨度，去完成图表WFST的赋值。
书中给出的算法代码为：
def complete_wfst（wfst，tokens， grammar，trace=False）:
index = dict（（p.rhs（），p.lhs（）） for p in grammar.productions（））
numtokens= len（tokens）
for span in range（2， numtokens+1）:
for start in range（numtokens+1-span）:
end = start + span
for mid in range（start+1， end）:
nt1，nt2 = wfst[start][mid]，wfst[mid][end]
if nt1 and nt2 and （nt1，nt2） in index:
wfst[start][end]= index[（nt1，nt2）]
if trace:
print [％s] ％3s[％s] ％3s[％s] ==>[％s] ％3s[％s] ％（start， nt1， mid，nt2，end， start， index[（nt1，nt2）]， end）
return wfst
嵌套了很多的轮回，其实经过细心解析，此算法并不难懂得。为了更好的懂得，可以本身手动演示一下就能懂得算法的内涵，若是各位读者看着很难懂得，本身走一下法度的步调就很轻易懂得了：
span=2:＃当值为2的时辰，搜检两个词之间有没有关系
＃range（numtokens+1-span=6）（0~5）
start=0:
end=start+span=0+2=2
＃range（start+1，end）（0+1，2）
mid=1:
nt1=wfst[0][1]，nt2=[1][2]
start=1:
start=2:
end=start+span=2+2=4
＃range（start+1，end）（3，4）
mid=3:
nt1=wfst[2][3]，nt2=[3][4]
start=3:
start=4:
start=5:
span=3:
＃range（numtokens+1-span=5）（0~4）
start=0:
end=start+span=0+3=3
＃range（start+1，end）（0+1，3）
mid=1:
nt1=wfst[0][1]，nt2=wfst[1][3]
mid=2:
nt1=wfst[0][2]，nt2=wfst[2][3]
start=1:
start=2:
start=3:
span=4:
span=5:
span=6:
span=7:
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
