搜索
Table_bottom

标签云
Table_bottom

分类
Table_bottom

声明
文章若未特別註明,皆採用 知识共享许可协议 請自覺遵守
Table_bottom

存档
Table_bottom

匆匆过客
31945
Table_bottom

功能
Table_bottom

直覺上的Hobbs算法

註:文中“(即……)”形式的內容爲輔助理解本質的內容,並非算法內容。

算法分成幾個按順序的部分,每部分如果匹配上,則直接返回,否則往下走。“匹配”的標準爲:agreement等正確,同時滿足當前部分的要求。

整體邏輯/基本想法

算法可大體分爲三個部分:

  1. 在當前句子中尋找(過程較爲複雜,後面詳細說明)
    1. 在目標節點左側進行尋找
    2. 找完還沒找到則在右側進行尋找,但不進入NP和S節點
  2. (如果找不到或沒有合適的)在前面的句子中尋找(如果找不到則繼續向前直到找到爲止)
    • 過程十分簡單:以從左向右、寬度優先爲原則遍歷子樹,尋找匹配的NP

算法過程

算法初始化:從目標代詞(記爲T)所在的NP節點(記爲“當前節點”和/或“X”)開始(即NP->Pron規則中的NP)。

算法唯一循環:

  1. 尋找X之上最近的NP或S節點作爲當前節點,替換原先的X。
  2. 以從左向右、寬度優先爲原則,尋找當前節點X的子樹中(同時在T到X路徑左側)第一個匹配的NP
  3. 若X是S,則看前一個句子的語法樹(見上面)。(只有兩種情況會滿足該要求:
    1. T是句子中(從左往右數)第一個NP(即該句子爲以目標代詞爲主語的句子,或是以目標代詞爲賓語的祈使句等),則首次進入則會遇到該規則
    2. 循環回來遇到S(即尋找完當前句子而沒有找到相匹配的NP)
  4. 尋找X之上最近的NP或S節點作爲當前節點,替換原先的X。
  5. 如果X是NP,而且從T到X的路徑中沒有經過Nominal節點(即T並非X這個NP的定語),則試圖匹配X
  6. 以從左向右、寬度優先爲原則,尋找當前節點X的子樹中(同時在T到X路徑左側)第一個匹配的NP
  7. 如果X是S(即左側已找完),則尋找T到S路徑右側的所有子樹中尋找相匹配的NP。此時如果遇到NP和S,不進入其子樹。
  8. (若如果仍未匹配上)回到3

 

(最近在爲NLP的(高速入門)課準備考試,於是也在看J&M的Speech and Language Processing。其中關於Hobbs的描述看得很頭痛,於是dump一下自己的理解。)