概率CYK算法的分析研究.pdf

1、本文將簡要介紹單詞的分類與詞類標注的相關內容，在此基礎上介紹句法處理的一個計算機模型：上下文無關語法。上下文無關語法又稱為短語結構語法，是模擬自然語言成分結構的最常用的數(shù)學系統(tǒng)。此時就可以對句子進行句法剖析了，也就是根據(jù)上下文無關語法識別一個句子并給句子指派結構。很多句子有一個以上的結構，即這些句子是有歧義的，上下文無關語法可以有效地表示這種歧義，但是它沒有提供手段來消解歧義。
　　 概率上下文無關語法可以提供對這個問題的解決方

2、法：從歧義中選擇概率最大的解釋。由于歧義非常普遍，因此概率剖析器在大多數(shù)剖析或自然語言處理工作中起著重要的作用。
　　 在現(xiàn)存的剖析算法中，概率CYK算法是用于概率上下文無關語法剖析的一個標準算法，它具有以下特點：
　　 1. 概率CYK算法要求Chomsky 范式的概率上下文無關語法。Chomsky范式的規(guī)則只有兩種形式：A →BC或A →x(這里A、B、C是非終結符，x可以是非終結符或終結符)。由于每個上下文無關語法

3、都可以轉化成弱等價的Chomsky 范式的語法，因此概率CYK算法可以應用于任何一個概率上下文無關語法。
　　 2. 概率CYK算法本質上是一種自底向上分析法，采用廣度優(yōu)先的搜索策略。
　　 3. 概率CYK算法是一種動態(tài)規(guī)劃算法，并行進行不需要回溯，沒有冗余的操作，時間復雜度為3O(n)，n 為單詞個數(shù)。
　　 基于概率CYK算法自底向上分析的特點，傳統(tǒng)的語法規(guī)則排列順序實際上制約了剖析的速度，可以重新排列語法