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

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

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

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