關于CKY句法分析效率的實驗性研究.pdf

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

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

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