句法分析是自然语言处理领域非常基础而重要的问题,提高句法分析的准确度和分析效率一直都是人们研究的重点。在各种句法分析算法中,CKY是最著名、最常用的一种。本文对CKY算法的分析效率进行了实验性的研究,力图探索影响CKY算法效率的各种因素,进而提高CKY算法在实践应用中的分析速度。具体地,本文关注于两方面问题的研究:1.CKY算法的各种具体实现。尽管CKY算法具有理论的O(n~3)复杂度,然而实践中还是可以有多种不同效率的实现方式。本文系统地总结了各种实现方式,分析了时间复杂度,并提出了两种优化策略。实验表明了不同的实现的分析效率相差的确比较大,并且不同的文法上,最优的实现也并不一致。针对后一问题,我们提出了一种新的综合了其他实现的方式,称做联合实现。实验证明,联合实现可以在任何文法上都获得接近最优的分析效率。这对CKY算法的实践应用有着比较大的指导意义。2.不同的文法二元化方式。文法二元化对CKY算法获得O(n~3)的复杂度是至关重要的。然而,不同的二元化文法也会导致CKY分析效率上的差异。在做出简化假设的基础上,水文细致地分析了二元化对CKY分析效率的影响,认为好的二元化依赖于输入语言的某种内在性质,并提出了一种基于训练语料库信息的二元化方法。实验表明本文的二元化文法,相比现有的各种二元化方法,可以获得更高的分析效率。尽管在句法分析领域早面已经有许多研究CKY算法的工作,但据我们所知,还没有已知的工作总结研究过CKY的各种具体实现和文法二元化对CKY分析效率的影响。本文的工作对这两个基本问题做了有益的探索和研究。