直接成分分析法在计算机结构与树形图上的运用

直接成分分析法在计算机结构与树形图上的运用

0叉树形态的复杂性树型图在数学研究、计算机编程和语言学研究中发挥着重要作用。在语言学研究领域,分叉树形图经常用于视觉化体现某一语言(英语)结构:句子结构、音节结构和音位几何特征。目前常见的利用分叉树形图分析相关句子(词组)结构的理论主要有:Chomsky在转化生成语法中提出的X-、SP理论、表层深层结构转化规则1-177,Halliday在系统功能语法中提出的最小括号法486-521;人们根据Bloomfield提出的直接成分分析法168-169在分析实际问题时,所采用的二叉树分析图等。然而,即便是二叉树也有不同的形态,为研究方便,本文采用的是如图1所示的二叉树形态。语言学直接成分分析法(以下简称IC分析法)中的二叉树和程序设计中的数据存储结构二叉树(以下简称二叉树)有着某些相似的特征。例如:二者都由结点和分叉构成;一个结点都可以引申出两个子结点。因而,语言学二叉树可以看作一种特殊的信息数据存储结构二叉树。另外,笔者试作如此猜想:数据存储结构二叉树的内在关系以及与之相关的数学公式是否可以用于揭示直接成分分析法中二叉树的内在关系呢?如果可以,鉴于后者的特殊性,原先的数学关系又将作如何调整?其实这一假设可以分解为以下几个子问题:IC分析法二叉树可以分为哪几类?在语言学二叉树中,各个语言单位(可以看作二叉树的结点),语言层次(可以看作二叉树的层次或深度),以及整个树形图之间存在何种数学关系?这些关系成立的前提条件是什么以及如何应用到实例中?IC分析法有无多元化分的可能性?若可分,多元化分中的内在关系将是怎样的?在《语言论》一书中,Bloomfiled提出了两个著名的语言分析方法:语言学刺激反应公式23和直接成分分析法169。从研究角度上讲,国内已有学者从数理角度对前者进行了拓展性研究,但是鲜有学者从数理角度继续深入研究后者。通过类比数据结构二叉树的分类和性质,本文重点研究了理想化条件下IC二叉树的分类和内部数学关系,探讨了多元划分的可能性,以期为自然语言(英语)的计算机处理提供新思路,从而深入拓展IC分析法。1研究背景1.1相关文献记载Bloomfield于1933年在《语言论》一书中首次明确地提出了IC分析法168-169,大多数语言学家对IC分析的合理性并未提出太多的质疑,而且似乎是“顺理成章”地接受了其理论与方法55。但是他并没有直接定义这一概念,而是通过例子来阐释:……AnyEnglishspeakingpersonwhoconcernshimselfwiththismatterissuretotellusthattheimmediateconstituentsofPoorJohnranawayarethetwoformsPoorJohnandranaway;thateachoftheseis,inturn,acomplexform;thattheimmediateconstituentsofranawayareran,morpheme,andaway,acomplexform,whoseconstituentsarethemorphemesa-andway;andthattheconstituentsofPoorJohnarePoorandJohn.Onlyinthiswaywillaproperanalysisleadtotheultimatelyconstituentmorphemes……168-169由以上论述可知:IC分析法是一种语法分析体系,它把较大的语言单位(句子或词组)分成连续不断的层次或成分,这种分析直到最后一层,即每一成分仅含一个词或其有意义的部分。它的的核心特征可以归纳为:两分法(二元化分)适用于各个层次;两分法直至遇到不可再分的成分(通常到词)才停止。IC分析法是对语言形式上的划分,需要指出的是:虽然Bloomfield认为语言分析应该从形式出发,但并不否认意义因素在语言分析中的作用53。他认为IC分析中的最终不可分成分一般为词素,而词素就是语言中最小的有意义的单位,这点可以证明他对意义的重视。为了便于二叉树与实际所代表的语言(单位)对应,本文所提及的IC分析法只研究到词的层面。语言学家们曾用各种图形阐释IC分析法:包括集合交并法、括号法、凹凸表法以及二叉树等。鉴于二叉树形态的多样性,为阐释方便,本文只研究如图1所示的二叉树形态。1.2叉树的基本性质数据结构二叉树具有如下性质:①在二叉树的第k层,最多有2k-1(k≥1)个结点;②深度为m的二叉树最多有2m-1个结点;③在任意一棵二叉树中,深度为0的结点总是比度为2的结点多1个;④具有n个结点的二叉树,其深度(最大层次数)至少为[log2n]+1,其中[log2n]表示只取log2n的整数部分;⑤具有n个结点的完全二叉树的深度为[log2n]+1,其中表示只取整数34-36。当然,二叉树还有许多其它性质,鉴于篇幅限制,本文将根据以上几个结论来探究语言学IC二叉树中较为简单的基本性质。数据结构二叉树有两个特殊的类型:满二叉树和完全二叉树。在前者中:除最后一层外,每一层上的所有结点都有两个子结点;在后者中,除最后一层外,每一层上的结点数均达到最大值;两者在最后一层上只缺少右边的若干结点34-36。语言学二叉树自身的特性决定了它不是简单的二叉树,其性质和分类不能简单地与信息结构二叉树相类比。2ic分析中相交树的分类2.1深度的分析在IC分析法框架内,IC二叉树的树形结构可与自然语言的结构相对应。结点表示语言单位或成分。如图1中,A作为根结点代表着一个较大的语言单位(句子或词组);子结点B和C代表构成A的两个直接成分(词组或词);结点D和E表示构成上一结点B的两个直接成分;同理以此类推,最终得出两个不可再分的结点H和I(不可再分的语言成分)。另外,树形层次代表语言层次。比如,A所处的层次代表着将要进行IC分析的较高的语言层(句子层或词组层);B,C表示经过IC分析法处理后,所得出的较低的语言层;其他结点以此类推,属于更低的层次。而且,并不是所有出于同一层次的结点都可以进行IC划分。在第3层上,有的结点(如:D,F,G)已经是词,或者经过若干次IC划分已经处于词的层面,一般不能再进行划分;而有的结点(E),由于还未划分到词,因而可以再分,并且在第4层次得出H和I两个叶子结点(E的直接不可分成分,即词)。笔者称这种现象为“直接不可分成分”出现的不同步性。另外“直接不可分成分”用Bloomfield的术语来表示就是“最终成分”168-169。本文IC二叉树研究的重要前提“最终成分(二叉树中用叶子结点或终结点表示)”或“直接不可分成分”就是指词。在这个前提下,D,H,I,F,G(叶子结点)代表着构成我们通常所见的(将要进行直接成分划分的)句子(根结点A)的词。值得注意的是:IC分析法核心特性决定了IC二叉树的某一结点(在可分的情况下)必须同时分成两个子结点。这点与信息结构二叉树不同,后者的结点的分化不必同时,而是按照信息访问(查询,又称遍历)或存储的次序进行排列的。另外,直接成分分析法体现出的语言的设计特征“创造性”34-36,20-21及“递归性”,使语言单位具有无限次二元划分的可能性,这是本文IC二叉树研究的另一个重要前提。2.2满ic二叉树形态笔者认为IC二叉树可以分为3类:空IC二叉树、满IC二叉树、非满IC二叉树。从图形角度来讲,空树是只有一个结点(根结点)或没有结点的IC二叉树。从语言学角度来看,它表示的是这样1个语言单位:只含有1个词,或者含有非词成分,抑或非语言形式(无语、手势语等)。如图2所示,前者的树形图可记作“·”;后两者的树形图可记作“Φ”。空树可描述为:“在某些语境中,以某种句子类型出现词或非词成分。177”它们可以履行句子的职能,表达一个完整的意思。比如:(1)a:Whatdoyouknowaboutthecriminal?b:……(Silence)(2)c:Whatistheprefixintheword‘pretext’?d:Pre-.(3)e:Whendoyougohome?f:Tomorrow.满IC二叉树形态(如图3所示)类似于数据结构二叉树中的满二叉树形态。从图形角度来讲,所有叶子结点或终结点都分布在同一层次,即最底层。从语言角度来看,在IC分析作用下,语言单位(或其成分)的所有直接不可分成分均出现在同一语言层(最底层)。这一点可归结为:“直接不可分成分”出现的同步性。要想呈现出满树分布特征,从较高层次分化出来的直接成分应该具有类似的划分结构,即都可以同时划分出相同数量的语言成分(结构),或经过若干次IC分析后得出的语言成分同时在同一语言层上具有不可再分性(通常到词)。此外,这也反映了在IC分析法作用下,语言成分(单位)分布的对称性。例如,英文句子“Thegirlwalkedhome”的IC分析图具有上述特征。非满IC二叉树(如图4)与满树相对。从图形角度来讲,叶子结点或终结点不都分布在同一层次(最底层)。从语言角度来看,它体现了语言“直接不可分成分”出现的不同步性。对于呈现出非IC满树分布特征的语言单位,从较高层次分化出来的直接成分不具有类似的划分结构,即不能同时划分出相同数量的语言成分(结构)。这反映了在IC分析法作用下,语言成分(单位)分布的不对称性。如词组“thebeautifulgirl”的IC二叉树就是非满树。但是,在树形上,非满IC二叉树不同于作为数据结构的完全二叉树,原因在于:后者除最后一层外每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点;而前者,依据其定义,最后一层外每一层上的结点数可以不达到最大值,在最后一层上(依据语言环境)可以缺失任意位置的结点。据此,在二元划分前提下,从形态上看,非满IC二叉树不完全等同于作为数据结构的完全二叉树。此外,在IC分析法作用下,我们还可得出空IC二叉树的语言单位或成分(结点)总数恒为1或0,满IC二叉树和非满二叉树的语言单位或成分(结点)总数为奇数。3语言学与二叉树之间的内部数学关系3.1满语2号的节点数和语言学意义3.1.1确定严格控制参数的公式在满IC二叉树中,一个根结点分化成第2树层的两个次结点;在第3层,上一层两个次结点又依次分别分化成相应的两个结点,共计4个结点;以此类推:后一层上的结点数是前一层次结点数的两倍。以上特点说明了:满IC二叉树的各层的结点数形成了以1(根结点数)为首项,2为公比的等比数列。设某一树层为第m层,此层的结点数为am,根据等比数列公式,可得am=2(m-1)(m≥1,m∈N+),此公式表示的图形意义为:当IC满树的某一树层m确定时,第m层的结点数为2(m-1)。am和m的关系可以用一个更普遍的函数y=2(x-1)来表示。am=2(m-1)等价变形可得m=log2am+1,当am为已知时(设am=t),则原方程变形为m=log2t+1(t≥1,t∈N+)。此公式表示的图形意义为:某层次的结点数t确定时,则这一层次必是log2t+1层。另外,以上结论也可从满二叉树(数据结构)的性质④得出34-36。根据IC二叉树结点与自然语言(英语)语言单位和语言层次的对应关系,以上结论可归为:在IC分析法作用下,当所涉及的语言单位呈现出满二叉树分布状态时,位于某语言层m的(被划分出的)语言成分(单位)数为:2(m-1);特定语言层的语言成分数t确定时,则其必分布在第log2t+1层上。3.1.2满二叉树数据结构满二叉树的各层的结点数构成了等比数列。因而求满二叉树的总的结点就等于求等比数列的和。设此等比数列有m(m≥1)项,即二叉树有m个树层。当m趋近+∞时,则前m项和为:Sm=∑m=1∞am=∑m=1∞2(m−1)=a1+a2+a3+⋯+am.Sm=∑m=1∞am=∑m=1∞2(m-1)=a1+a2+a3+⋯+am.根据等比数列前n项和公式Sn=a1(1-qn)/(1-q),可得Sm=1(1-2m)/(1-2)=2m-1(m≥1,m∈N+)。此公式的图形意义为:当IC满树的前m层结点总数为2m-1。另外Sm和m的数学关系可用一个更普遍的函数y=2x-1来表示。当IC满树的结点总数确定时(设Sm=p),也可求出有多少树层m,其关系式为:m=log2(p+1)。这个结论的证明如下:由Sm=2m-1得:log2Sm=log2(2m-1),即m=log2(Sm+1),把p=Sm代入此式得:m=log2(p+1)。另外,以上结论也可从满二叉树(数据结构)的性质得出34-36。从语言学角度看,以上结论可归纳为:在IC分析法作用下,呈现出满树分布状态的较大语言单位及其划分出的成分总数为2m-1(m为语言单位在IC分析法作用下呈现出的语言层次)。3.2ic-2叉树的节点、树层的最佳值和学术意义3.2.1在满树各层深度结构设计时,求各层点对点及分值的有效性通过观察3类IC二叉树形态,可得出在同等条件下,即当树层数(m≥1)确定时,满IC二叉树的结点总数最多。其推理如下:当m=1时,空IC二叉树结点数为1,满IC二叉树结点数为1,非满IC二叉树结点数为1;当m>1时(空IC二叉树不符合条件),由于满树各层结点(除最后一层)都能分出两个子结点,而非满树的各层的结点(除最后一层)不能充分进行分化,因此树层数相同时,满树的结点数大于非满树的结点数。综上所述,当树层数m确定时,求此IC二叉树的结点数的最大值就等价于求满IC二叉树的结点总数:Sm=2m-1(m≥1,m∈N+)。另外,关于结点最大值的结论也可以从数据结构二叉树的性质①得出。另外,当树层数(m≥1)确定时,要想使结点分布的总数最少,则除最后一层外,每层只有一个结点可以分化出两个次结点。此时结点总数为Sm=2(m-1)+1=2m-1(m≥1,m∈N+)。从语言学角度看,以上结论可归为:在IC分析法作用下,当可被二元划分的较大语言单位呈现出的层次为m(m≥1)时,此语言单位及其划分出的成分最少为2m-1;此语言单位及其划分出来的成分最多为2m-1。3.2.2提出结论及结果通过观察3类IC二叉树形态,我们还可以发现:当结点数p=0时,此树为空数,树层不存在;结点数p=1时,这3类二叉树树层各为1;当结点数p>1时,要想使结点分布的层次最少,必须使各个层次都排满结点,即每个结点(除最后一层)都可IC划分(如图3所示)。而在3类IC二叉树中,最能充分实现结点IC划分的只有满IC二叉树。综上所述,当结点数p≥1时,求IC二叉树树层的最小值就等价于求满IC二叉树的数层数m,m=log2(p+1)。反之,在IC分析法作用下,结点总数确定时,要想使结点分布的层次最多,则除最后一层外。每层只有一个结点可以分化出两个次结点(如图5所示)。设结点数为p(p≥1),树层数为m,根据以上的推理和IC二叉树特点可得:p=2(m-1)+1,即m=(p+1)/2。综上所述,当结点数p≥1时,所形成IC二叉树树层数的最大值为(p+1)/2。事实上,当m≥3时,此类树前一层结点分划的可能性(c1221)会影响下一层结点划分,根据相应的排列组合公式,可得此树的形态共有2(m-2)种。从语言学角度看,以上结论可归纳为:在IC分析法作用下,当可被二元划分的较大语言单位(包括其被二元划分的所有成分)有p(p≥1)个时,它(们)所形成的语言层次最少为:log2(p+1);所形成的语言层次最多为:(p+1)/2。4建立数据库语料库以数据结构二叉树的性质和直接成分分析法为研究基础,本文所揭示的语言内部的数学关系有着一定的理论价值和应用价值。IC分析法的优点在于可以层次鲜明地揭示出语言内部的结构层次,有助于语言描写的客观精确;可以分析歧义句;发现新语法规律。国内已有学者提倡在外国文学教学中发挥学生数学逻辑智能的重要性。鉴于此,拓展后的IC分析法,特别是其中的数学关系和公式以及形态图,也可以应用在语言学和文学的教学中。它有助于教师和学生从数学角度(借助相关的计算软件和多媒体设备)来分析语言的层次结构,改变以往的纯语言分析,这也符合多元智能(MI)理论11-12中培养数学逻辑智能和空间智能的要求。目前,计算机处理句法(结构)歧义的方法主要是概率上下文无关语法、概率词汇下文无关语法和概率CYK算法。这些方法主要是依据概率计算和与之相关的语料库来判断某种句法结构出现的可能性。笔者尝试用拓展后的IC分析法来处理句法歧义。原因在于:不同的句法结构所表示的意义不同,