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

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

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

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