關(guān)于CKY句法分析效率的實(shí)驗(yàn)性研究.pdf

1、句法分析是自然語言處理領(lǐng)域非常基礎(chǔ)而重要的問題，提高句法分析的準(zhǔn)確度和分析效率一直都是人們研究的重點(diǎn)。在各種句法分析算法中，CKY是最著名、最常用的一種。本文對CKY算法的分析效率進(jìn)行了實(shí)驗(yàn)性的研究，力圖探索影響CKY算法效率的各種因素，進(jìn)而提高CKY算法在實(shí)踐應(yīng)用中的分析速度。
　　具體地，本文關(guān)注于兩方面問題的研究：
　　1．CKY算法的各種具體實(shí)現(xiàn)。盡管CKY算法具有理論的O(n3)復(fù)雜度，然而實(shí)踐中還是可以有多種不同

2、效率的實(shí)現(xiàn)方式。本文系統(tǒng)地總結(jié)了各種實(shí)現(xiàn)方式，分析了時(shí)間復(fù)雜度，并提出了兩種優(yōu)化策略。實(shí)驗(yàn)表明了不同的實(shí)現(xiàn)的分析效率相差的確比較大，并且不同的文法上，最優(yōu)的實(shí)現(xiàn)也并不一致。針對后一問題，我們提出了一種新的綜合了其他實(shí)現(xiàn)的方式，稱做聯(lián)合實(shí)現(xiàn)。實(shí)驗(yàn)證明，聯(lián)合實(shí)現(xiàn)可以在任何文法上都獲得接近最優(yōu)的分析效率。這對CKY算法的實(shí)踐應(yīng)用有著比較大的指導(dǎo)意義。
　　2．不同的文法二元化方式。文法二元化對CKY算法獲得O(n3)的復(fù)雜度是至關(guān)重要的

3、。然而，不同的二元化文法也會導(dǎo)致CKY分析效率上的差異。在做出簡化假設(shè)的基礎(chǔ)上，本文細(xì)致地分析了二元化對CKY分析效率的影響，認(rèn)為好的二元化依賴于輸入語言的某種內(nèi)在性質(zhì)，并提出了一種基于訓(xùn)練語料庫信息的二元化方法。實(shí)驗(yàn)表明本文的二元化文法，相比現(xiàn)有的各種二元化方法，可以獲得更高的分析效率。
　　盡管在句法分析領(lǐng)域里面已經(jīng)有許多研究CKY算法的工作，但據(jù)我們所知，還沒有已知的工作總結(jié)研究過CKY的各種具體實(shí)現(xiàn)和文法二元化對CKY分析