ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.277-284



ı滮нƶ㷨о
ҦPѧ
ժҪȫֽ;ֲƶ,ʹʺϸ㷺Ӧ.㷨MckeownĽ㷨Ϊ,ԭջʽƽṹĽͿƽṹ,ͬʱȫֽ;ֲƶ.㷨ĽSchemaתʾ,ΪظԺȼϢ,˶SchemaеݹĿƺͻݻ,֪ʶSchema͵ݹ.,˶SchemaɽŵĴ.ڴ˻,һʵϵͳ,㷨Ч.
ؼʣı滮,ȫֽ,ֲ,ģʽ,ν.
ţTP18
Research on the Shift Controlling Algorithm of Global and Immediate Focuses in Text Planning
YAO Tian-fangTANG Xue-yan
(Department of Computer Science and Engineering Shanghai Jiaotong University,Shanghai,200030)
AbstractThe improvement on the shift rules of global and immediate focuses is presented.The improved rules can be used for more extensive domain.Based on Mckeown's focus algorithm,a new algorithm that adopts tree as a controlling structure instead of stack is proposed.It can control the shift of both global and immediate focuses simultaneously.The new algorithm improves the ATN representation of Schema by adding repeat property and priority information to the edge and incorporates the control of the recursion of Schema and backtrack mechanism.The filling and recursion of Schema are determined by the knowledge base.Moreover,the new algorithm can also handle the interchangeable symbols in the Schema.The design of an experimental system based on the proposed algorithm is introduced and the effectiveness of the algorithm is discussed.
Key wordsText planning,global focus,immediate focus,Schema,predicate.
ıɲҪ֤塢䷨ṹʹʷȷ,ұΧı֯,ʹǡν,Ա֤ı.һ˵,ıɿɷΪ3׶,ı滮(text planning)ӹ滮(sentence planning)ͱ(surface generation)1.ƻı滮еһҪĻ,֯ıʱھӻ߶֮佹ƶ,ȷɵı.
Schemaǲѧе޴ν(rhetorical predicate,predicate)ıṹһַ.ı(proposition)ɵ.PropositionһӻһӾ.PredicateıеProposition,ÿPropositionΪضPredicate.ͬһı,һЩ׼PredicateģʽʾıĽṹ,ֱ׼ģʽΪSchema.SchemaʾıṹһֲλĽṹ,SchemaԵݹǶף2.ıɽ׶,ѡʵSchema,Ȼ֪ʶеƥSchemaеPredicate,ΪPredicateĲֵ.ÿPredicateɲ,ĸģ3,4.PropositionǽPredicateеĲֵõʵ.SchemaڱPredicateͬʱ,PredicateѡʵPropositionƥ.ֶƥ䷽ʱ,ɽƻƾѡĸProposition.SchemaõProposition,׶ʹ.
ıΧĳЩ߶չ,ǳΪ.ƻı,ʹıܵ.ıд͵Ľ:ȫֽ(global focus,ΪGF);ֲ(immediate focus,ΪIF).GFııı,SchemaһһӦ.ΪʹıĽṹ,Ǽ漰ıGFֻһ.GFֻSchemaݹʱſܷ仯.ı֮ǰ,ṩSchemaGF.Schemaֵݹ,ڲSchema,ָSchemaGF,.GFĿSchemaݹ.SchemaݹʵֵĹؼξǶ׵µSchemaGF.IFָһĸ,PropositionһֵĲ.PropositionĸֵԷΪ,һǿܳΪĲ,һǲܳΪĲ.Ϊ˿IFƶ,ıɹ,Ҫٺά3Ϣ:
(1) ǰӵIF(Ϊǰ,ΪCF);
(2) ǰпܳΪһӵIFĳɷ(Ϊpotential focus list,ΪPFL);
(3) ǰв־ӵIFɵĽջ(focus stack)2.
ҪоSchemaı滮еĽƻ.
1ƶ
оIFص֮任ֽ߱.Sidner4ƶ2:µCF: ǰPFLеԪ; ǰCF; ӽջеԪ; ǰCFصĸ.Mckeownеǰ3Ӧڽ㷨У2.ֻʹǰ3,ôCFתһδΪ¸ʱֻͨ,PFLеԪضǰһἰ.,һûбἰʱ,ͲܳΪ,ͨԽϲ.:
Ϻ̨72421ӷϺԤ(Focus=Ԥ):ҹϺкͳԤ(Focus=):ʱ(Focus=),ֲе(Focus=),ת(Focus=),ƫϷ(Focus=),תϷ(Focus=),45(Focus=),¶33(Focus=¶),¶26(Focus=¶).
Ԥı,CFת硢¶ʱ,Ӧù.CFתƷΧ̫,һ.ڷıĻ,ǽ޸Ϊ漰һ뵱ǰSchemaGFصĸ(implicitly related focus,ΪIRF).µĹֻCFתIRF,Աʹıṹɢ.,¶ȶԤصĸ.IRF(Object)ΪObjectصĶļ.µIFƶ:
1.תΪǰǱڽ,CF(new sentence)PFL(last sentence).
2.㱣ǰĵǰ,CF(new sentence)CF(last sentence).
3.صǰ۵ĳһ,CF(new sentence)Focus-Stack.
4.תƵȫֽص½,CF(new sentence)IRF(GF).
Ҫ˵,4һSchemaӦһGFڲIFı仯,Schemaʹ.ΪЩ,ΪǸȼ.ıԵص,϶ıķ,ȼϵ:
Priority(1)>Priority(2)>Priority(3)>Priority(4)
ıʱڶPropositionɹѡ,Ҫýƶп.ɾκһProposition,ȻȼӸߵЩ,ѡȼProposition.
2Schemaʵַ
Schemaͨת(augmented transition network,ATN)ķʵֵ.ATNԭȻӣ5.SchemaATNһͼ,Ľʼ״̬ем״ֹ̬״̬.SchemaĵݹǶ׶ӦATNĵݹǶ.ATN.һSchema/Predicate,Schemaеһ,SchemaPredicateʵ,÷ŲչһµSchema,SchemaʵΪnull.һjump,״̬֮ת,תʱƥκSchemaPredicate.ÿһظ.Schema/Predicateͻ,ϢʾSchemaPredicateʵֿظĴ,1ʾ1,+ʾΣ1NΣ.jumpͻ,ظһΪ1.SchemaĹ,ƥʧܾҪ,˻صǰ״̬,ѡPredicateƥ.,Ϊÿһ,ԽС,ȼԽ.תƵĳһ״̬,ѡԸ״̬ΪβĻȼߵģһһƥ.䲻ɹݵ״̬,ѡһȼĻƥ,.Ԫʾ:(Predicateʵ,Schemaʵ,ظ,).jump͵Ļ:Predicateʵ=jump,Schemaʵ=null,ظ=1.1ΪConstituency Schema,ӦATNͼ1ʾ.

Fig.1ATN of constituency schema
ͼ1Constituency schemaӦATN
Table1Constituency schema
1Constituencyģʽ

ATNMckeownʾSchemaATNͬ.Ҫ:
(1) SchemaATNʾвͼMckeownATNеsubr.ͼȡSchemaʽпɹӱʽ,һATNʾ,ԼSchemaıʾ.Schema,תƵͼƥʱ,CFתƵATNƥõPropositionCF(3).תƵǶ׵SchemaӦATN,,ΪIFƶSchemaʹ.ߵĽǲͬ.,SchemaATNһһӦ.ATN֮תֻSchemaĵݹɵ,ԭǱڿ.
(2) ΪÿظԵϢ.MckeownATN,ͨʾSchema Predicateʵظ.,Ҫƥ,ÿֻƥѡȡһProposition.ڸĽATN,SchemaPredicate ظȿʵ,ҲһظΪ+ʵ.úһַʵ,ֻһƥProposition,ڶǰʱ䡢ռ˳.ַ,IFƶǲͬ.ûʵ,ôͬһPredicateӦĶProposition֮IFͨ13ת.á+ͻʵ,ôЩProposition֮IFǰľ˵һֲйϵ.Ӧøݾѡʵķ.,ԵAttributiveνʾúһַʵ.ΪAttributive+ضԼԽ,мIFӦת.ܳ,ʹıṹɢ(ıеĺֱʾᲿ).
ͺǱͧһս(Focus=ͺǱͧ).װеͷͶװòƵĸٷ(Focus=).̽Զ(Focus=).ķйԲ(Focus=).ͺǱͧײ46׷(Focus=ͺǱͧ).ͺǱͧһЯ1216ö˵ͷĵ(Focus=ͺǱͧ).ͺǱͧˮ»,û޳,Է(Focus=ͺǱͧ).
3㷨
Ϊ˼IFƶ4SchemaݹԼлݵĴ,ǸĽMckeownĽ㷨еջʽƽṹ,Ϳƽṹ֮Ϊ.ĿҪ: ԭջʽṹʺϴSchemaݹ,һеݹ鶨ݽṹ.һSchemaӦıתƹһ,ôSchemaĵݹԿǽеĽչһµ,Էʵֵݹ; ͿƽṹԱΪֹı佹Ϣ,ڽл.ջʽƽṹִ˳ջ,ڻݵʱָǰ״̬.ͿƽṹSchemaĹ̾ǽĹ,ڻݵʱֻصǰɵĳһ,ɾȥ.㷨еĻݷΪ׶.1׶ڹ1͹2ʱ,ͨѰҽջзϹ3Ԫ.ҵ,ƥӦProposition,ݵǰSchemaӦĸ,ù4ɸѡ.ҵʵProposition,ָ1׶λǰ״̬.ڵ2׶λʱ,ɾѾõĽ,ѡATNͼеѡPredicateƥ.1׶εĻݲSchema.2׶εĻSchema,ԽԭȲSchemaʵ䵫ûгɹķŸPredicateʵƥ,.
ѡöΪƽṹ.ÿʾýͬCFĽ,ʾɾиýCF½ĽǱǶ׵SchemaӦĸ.еÿܶӦıеһProposition,ҲΪ˹콹ҪĽ,ӦκʵʵProposition.ÿ㶼ʾSchemaем״̬,Ϣ: ǰSchema,ӦATNĸGF; SchemaӦATNе״̬; ƥõProposition,PropositionCF,PFL; ʱǰ,ǰǸ,-1ʾ; SchemaӦĸ,¼ǰеƥǰSchemaʵչ仹Predicateʵֽƥ.ʱ,Schemaչ佫Predicateʵּ,Predicateƥ,һǰ.,ATNеÿ״̬,ʵƥʱѡȨӸߵΪ:ȨSchemaʵ,ȨPredicateʵ,θȨSchemaʵ,θȨPredicateʵ,...,.
Schemaƥĵ1Proposition,ջΪ,ûǰPFLɹѡ,Թ1͹3ʹ.ʱ,CFǸSchemaGF2ƹ㣩IRFеԪأ4.㷨,ÿSchemaӦĸCF=GF,PropositionϢΪnull.,ƥSchemaĵ1Propositionʱֻʹù2͹4.4IFƶѡPropositionԽĴ.Cʾеĵǰ,N,N1,N2,...ʾӵĽ.ˮƽʾ,ֱʾ.Schema,Status,Proposition,PrecMatchֱʾ5Ϣ.
㷨1.ѡIFƶ1PropositionԽĴ.
 ձ2չ; ƥĻSchemaʵ,CN1;CN.
Table2Processing for controlling tree of focus in algorithm 1
2㷨1ԽĴ



㷨2.ѡIFƶ2PropositionԽĴ.
 㷨1Ĳ1ͬ,֮ͬ,ƥATNûSchemaʵظΪ1ʱ,ӵĽNǵǰC; ƥĻSchemaʵ,C=N1;C=N.
㷨3.ѡIFƶ3PropositionԽĴ.
ڵ1׶λݵʱӦù3.1׶λǰĵǰΪC,ڵ1׶λʱ,ӵǰ㿪ʼŶȷѰӦù3Ľ.ҵĽΪF.
 3չ,Ŀǽ2׶λݵPrec(ǰ),C=P; 㷨2Ĳ1ͬ,PrecΪC; ƥĻSchemaʵ,C=N1;C=N. 
Table3Processing for controling tree of focus in algorithm 3
3㷨3ԽĴ

㷨4.ѡIFƶ4PropositionԽĴ.
1׶λǰĵǰΪC.ڵ1׶λݽδҳʵPropositionʱӦù4,ʱѻݵǰSchemaӦĸ.
 Ӹø㿪ʼѰĽ,ΪF; ͬ㷨3.
SchemaʱĽƶ㷨.
㷨5.
 ʼ:øRoot,Root.Schema=ƥSchema,Root.Status=ƥSchemaӦATN,Root.Proposition=null,Root.Prec=-1,Root.Match=PredicateMatch,C=Root;
 ݴӵǰһȨĻPredicateʵ,ѡ֮ƥProposition;
 һƥĻΪjump,4չ.C=N.Ȼת;
Table4Processing 1for controling tree of focus in algorithm 5
4㷨5ԽĴ1

 ڷϹ1Proposition,㷨1,Ȼת;
 ڷϹ2Proposition,㷨2,Ȼת;
 е1׶λ:
while ϻݣݵһεSchema
{if ڷϹ3Proposition,㷨3,Ȼת
ǰ=ǰĸ}
 ڷϹ4Proposition,㷨4,Ȼת;
 е2׶λ:
ָ1׶λǰĵǰC,
while true
{ɾȥǰ
if ӵǰиȨĻ,ѡĻƥ,Ȼת
if ǰC=ǰCSchemaӦĸ
{if C.Match=SchemaMatch
{C.Match=PredicateMatch,temp=C.Prec,
C.Schema=temp.Schema,C.Status=temp.Status.
if ǰCǰC=ǰC
else ǰC=ǰCǰ,Ȼת}
else Schemaƥʧ,㷨}
ǰC=ǰCǰ}
 while ǰC.StatusATNֹ״̬
{ǰC=ǰCSchemaӦĸ
if ǰCöĸ㡡Schemaƥɹ,㷨
else if ǰǰC=ǰC
else ǰC=ǰCǰ}
ת.
ע:ΪǰCʱ,CѾǿ,ΪCһ,5ʾ,ȻC=P.
Table5Processing 2for controling tree of focus in algorithm 5
5㷨5ԽĴ2

⻹ע,ڵ2׶λPrecʱ,C.Prec=-1,ôCǰ丸.Cǰ(C.Prec).Prec,Ҫǰ.ƥõPropositionͬһƶ,ƥ仡ظΪ+,ЩPropositionָ˳кηõ.ƥ仡ظΪ1,ЩPropositionָ˳кѡǰPropositionõ.
4ʵϵͳ
ݸĽĽ㷨һʵϵͳ֤㷨Ч.ʵϵͳҪʵı滮׶εĽƼSchemaز.ϵͳ: :PredicateʹõĸֲϢ; Predicate:SchemaʹõPredicateơʽϢ; Schema:ƥSchemaĽṹ; ֪ʶⶨ:ƥSchema֪ʶ.Ϣıļʽ.Ϊ˱ʵ,Բֶ˼.ʵϵͳ,ý㷨,ƥProposition,㷨м.ʵϵͳṹͼ2ʾ.

Fig.2Architecture for experimental system
ͼ2ʵϵͳṹ
㷨һѾϸ,ɽóPropositionеĵݹ㷨.
GetText:ĸroot
(1) if root=-1,㷨.
(2) if rootĳһSchemaӦĸ
{if rootPropositionϢΪnull,rootProposition
GetText(root),
GetText(root)}
else {GetText(rootĸ),GetText(root)}
,ʵе.
(1) ɽšʵ
SchemaʾеĿɽţ4ݵʹǰصɳɷֵĴԽ,ıʱض.P1P2൱(P1P2)/(P2P1),ӦATNͼ3ʾ.ͼл1,2͡1,3ȼͬ.P1P2һSchemaݹǶʵ,״̬1бP1P2ȡᣨѡһ·,ʵȡP1P2Predicateʵ.Ϊ,֪ʶΪÿPropositionȼ.

Fig.3ATN of  P1P2
ͼ3P1P2ӦATN
ڶPredicateƥóPropositionͬһƶʱ,ѡȼϸߵһ.Ա6ʾԤSchemaΪ,ƥTitle֮,ֱƥWeatherAmplificationStormAmplificationPredicateʵTitleAttributive,Title:(1) ҹϺкͳԤ;Attributive:(2) 7̨λѾ̨ʡ㴺жϴԼ620.ļ,(2)ȼ>(1)ȼ,̨֮һStormAmplification,WeatherAmplification;,(1)ȼ>(2)ȼ,WeatherAmplification,̨StormAmplification,ͻڲͬڵҪ.
Table 6Schema of weather forecast
6ԤSchema

(2) ڲͬӦҪòͬĸȷIRFϵPropositionȼϢ.ЩϢṩԵ֪ʶ.
(3) IFƶ1ʹӦעֽѭ,:
Proposition 1:CF=A PFL={B};
Proposition 2:CF=B PFL={A};
Proposition 3:CF=A PFL={...}.
Proposition 3ǰĵĹϵֵӦǹ3,ǹ1.Ҳ˵,ʵʹù1ʱ,PFLҪɾȥѱѡеCF,ӦɾȥʱڽջеԪ.CFҪת뽹ջеԪ,ʹԪػPFL,Ҳʹù3.
(4) ʹIFƶ1߹4ĻظΪ+ҸûSchemaʵֲnull,ôÿѡPropositionչһSchemaӦ.ʱӦöЩPropositionִѹ,ԽͬPropositionֻһ,չSchemaͬGF.
5
㷨¼˸Ľ:
(1) ĽSchemaATNʾ.ʹSchemaʽд+͡*PredicateATNֱʾ,ԸݲͬıصѡӦıʾ;
(2) ջʽƽṹĽΪͿƽṹ,еõProposition佹Ϣ,ʵSchemaĵݹƥеĻ,ȷSchemaݹʱGFƶͿƷ.ΪʵֻݻATNĻȼ;
(3) IFƶ.4ͬʱ,ıתƵ,ʹ㷨ʺϸ㷺Ӧ;
(4) ˶Բйϵʽͬľӵ,ıԵһҪ.Ȼûи򷽷Ӧйأ,ʵϵͳѼ˶Ӧ;
(5) ˶ԿɽŵĴ,ΪPropositionȼ.
Ƕε,ƪνȻڲͬӳ,ϵ㡢䷨㡢ʻ㡢㡢Ųȣ6.ĵ㷨Ҫʹɵı֤,Ȼ޹ص.ıɹлھ䷨㣨ʽѡ񡢽ṹνӵȣʹʻ㣨ָơʻνӵȣȲоıԿƵķ..
ĿоõȻѧ(No.69673008)ϺпίƼչ
(No.96297002)͵¹ڻ(VW).
߼飺ҦP,1957,,ҪоΪ,Ȼ.
ѧ,1977,˶ʿ,ҪоΪȻ,.
ߵλҦP(Ϻͨѧѧ빤ϵϺ200030)
ѧ(Ϻͨѧѧ빤ϵϺ200030)
οף
1Cole R A et al.Survey of the state of the art in human language technology.http://www.coli.uni-sb.de/hansu.The Web Page for the Department of Computational Linguistics at the University of the Saarland.1996
2Mckeown K R.Text Generation:Using Discourse Strategies and Focus Constraints to Generate Natural Language Text.Cambridge:Cambridge University Press,1985.3035,5758,7173
3Yao Tian-shun.Natural Language Understanding:A Study of Making a Machine Understand Human Language.Beijing:Tsinghua University Press,1995.5455
(Ҧ˳.Ȼ⡪һûԵо.:廪ѧ,1995.5455)
4Wang Xian,Yao Tian-fang.Design and implementation of macroplanner for Chinese weather forecast automated generation system.In:Chen Li-wei,Yuan Qi eds.Language Engineering.Beijing:Tsinghua University Press,1997.176181
(,ҦP.Ԥıݹ滮ʵ.:Ϊ,Ԭ.Թ.:廪ѧ,1997.176181)
5Cai Zi-xing,Xu Guang-you.Artificial Intelligence:Principles and Applications.2nd ed.Beijing:Tsinghua University Press,1996.307309
(,v,˹ܼӦ.2.:廪ѧ,1996.307309)
6Hu Zhuang-lin.The Joining and Coherence of Discourse.Shanghai:Shanghai Foreign Language Education Press,1994.224226
(׳.ƪν.Ϻ:Ϻ,1994.224226)
ոڣ1998-11-23
޸ڣ1999-03-01
