圖 - 如何使用Tree Isomorphic來解決語言模式匹配？

在Algorithm Design Manual，它說圖 - 如何使用Tree Isomorphic來解決語言模式匹配？

你測試兩棵樹是否同構？ - 對於圖同構的某些特殊情況，例如樹和平面圖，存在更快的算法。 也許最重要的情況是檢測樹之間的同構，這是語言模式匹配和解析應用程序中出現的問題。分析樹通常用於描述文本的結構;如果底層的文本對具有相同的結構，則兩個解析樹將是同構的。

我只是希望有人請給我一個例子，說明如何使用Tree Isomorphism來解決語言模式匹配問題。即如何將語言模式匹配映射到樹同構問題？

通常情況下，我該如何構造一個字符串或文本作爲樹並比較它們的身份？

感謝

來源

2012-05-07 Jackson Tale

只是一個快速提示，如果你沒有得到很好的答案這裏這個問題可能是一個很好的適合http://cstheory.stackexchange.com/，... – ChristopheD

@ChristopheD謝謝！ –

使用英語爲例，這個想法是，一些英語句子可以通過下面的分析樹表示：

 SENTENCE    SENTENCE 
    /  \   /  \ 
    PROPER NOUN VERB  COMMON NOUN VERB 
    /    / \ 
    NAME    ARTICLE NOUN

的英文詞組「的狗吠聲。「然後可以如下解析：

ARTICLE NOUN  VERB 
/  /  /
The  dog  barks 

    COMMON NOUN 
    / \ 
ARTICLE NOUN  VERB 
/  /  /
The  dog  barks 


      SENTENCE 
      / \ 
    COMMON NOUN  \ 
    / \  \ 
ARTICLE NOUN  VERB 
/  /  /
The  dog  barks

另一個結構相同的句子是「一片落葉」。它的解析樹會看起來具有相同的形狀，這意味着兩個解析樹將是同構的。也就是說，即使意義不同，它們也與句子具有相同的邏輯結構。

  SENTENCE 
      / \ 
    COMMON NOUN  \ 
    / \  \ 
ARTICLE NOUN  VERB 
/  /  /
A   leaf  falls

如果您忽略實際的物理單詞，那麼兩個解析樹也都與一般模式同構，也表示爲樹。

來源

2012-05-08 05:09:35

非常清楚，謝謝！ –

正如文中所指出，解析樹是這裏的關鍵概念。一個分析樹表示（某種方式）文本的結構，它在技術上是一棵樹，所以你可以使用任何你喜歡的樹算法來處理分析樹。

解析樹是一種有序的根樹，它根據某種形式的語法表示字符串的語法結構。

（上Parse trees維基百科文章）

來源

2012-05-07 21:48:02

圖 - 如何使用Tree Isomorphic來解決語言模式匹配？

回答

相關問題