4.2.7 CYK的简短回顾

到现在我们已经在这条路上走了很远。首先我们通过原始语法构建了识别表。接下来,我们找到了单元规则和ε规则,虽然比较复杂但用它们也能达到我们的目的。接着我们改进了一下,将语法转换为CNF。而CNF并不包含单元规则和ε规则。由此我们发现构建识别表的算法会变得更简单。发现右侧的最大长度限制为2,也让我们的效率提高很多,同时也让事情简单了一点。然而Sheil [20]已经证明,效率只取决于语法右侧出现的非终结符的最大个数,而不是每一个sé的右侧的长度。这个很容易理解,只要意识到效率取决于(相对于其他事)子句中“很难”找到的小切片(当检查一个右侧是否能生成这个子句时)。而这些“很难”找的小切片的数量取决于右侧的非终结符的数量。因此为了提升效率,Chomsky Normal Form就比较严格一些了。

转换为CNF的一个缺点是生成的识别表丢失了一些信息,以至于我们需要从原始语法中构建一些派生。在转换过程中,有些非终结符被丢弃了,因为它们变成了非生成性的。好在这些失去的信息倒是很容易恢复。最终,这个过程将带给我们一个与我们首次尝试使用原始语法时得到的,几乎一模一样的识别表。它只多了一些在我们将语法转换为CNF时添加在非终结符上的额外的信息。更重要的是,它是以一个更简单高效的方式得到的。

作为CYK算法的一个更详细版本,详见15.4.2节Tree Adjoining Grammars。

results matching ""

    No results matching ""