快速上下文无关文法分析要求快速布尔矩阵乘法

                               莉莲李

                      康奈尔大学计算机科学系

                                   摘要

    在1975，Valiant表明布尔矩阵乘法可以用于分析上下文无关语法（CFGs），得到已知的渐近速度最快（虽然不实用）CFG解析算法。我们证明了一个双重结果：任何时间复杂度为O(gn³)的CFG分析器， 其中g是语法的尺寸而n是输入字符串长度，可以有效地转换成一个时间为O(m^3c/3) 的去乘m×m布尔矩阵算法。鉴于相当难找到实用根本的次立方布尔矩阵乘法算法，因此，我们解释为什么在开发实用根本的CFG分析器上没有一点进展。在证明这一结果时，我们也发展了一种形式化句法分析的概念。

1.引言

  Chomsky介绍的（1956）上下文无关文法（CFG）的形式理论，已在各种领域得到广泛的应用。CFGS模型已被用于对编程语言的结构建模，人类语言，甚至是生物数据，如组成DNA和RNA的核甘酸序列和（Aho，Sethi，和Ullman，1986；Jurafsky和Matin，2000；Durbin等人，1998）。

CFG生成系统的字符串是通过改写连续应用规则的。然而，在实践中，目标通常是不从一个语法产生有效的字符串。相反，一个典型的有趣的的字符串，比如一个程序或一个英文或一句话，在一个方面，目标是相对于语法分析-解析-字符串。

一般CFG解析的典型方法是CKY算法（Kasami，1965； Younger，1967）和Earley算法（Earley，1970）。它们都有一个最坏情况，其运行时间为O(gn³)，CFG大小为G，字符串的长度为n（Graham， Harrison, and Ruzzo，1980），虽然有要求输入语法为乔姆斯基的正常形式，以便实现这个时候的约束。不幸的是，作为语音识别，对字符串长度的依赖关系是这样昂贵的应用，响应必须及时，或在输入的情况下进行序列是非常长的，如在计算生物学。

渐近更快的解析算法确实存在。Graham, Harrison, and Ruzzo (（1980）给了一个Earley算法的变种，是基于所谓的“四人”（arlazarov等算法，1970），布尔矩阵乘法（BMM）；它的运行时间为O(gn³ /logn)。 Rytter（1985）进一步修改这个分析器的压缩技术，提高对字符串的依赖长度为 O(n ³ /log ² n)。但 Valiant’s (1975)的分析方法重组了CKY的计算，是已知的渐近最快方法。它还使用BMM；其最坏情况下的运行时间为在乔姆斯基正规形式的语法是比例为 M(n)，其中 M(m)是它乘2个m×m布尔矩阵需要的时间。

图1：已知的矩阵乘法的复杂度指数ω的最低上界. 例如，在1969之前，已知的矩阵乘法的最快的算法与M ³步成正比 (ω= 3)

由于这些次立方解析算法都依赖于布尔矩阵的乘法，自然要问，实践中BMM可以执行得多快。已知的执行BMM的渐近最快的方法是依靠乘以任意矩阵的算法。存在时间复杂度为O(m^3−δ)的矩阵乘法算法，从而可以提高标准算法的O(m³)的运行时间；例如，Strassen的算法（1969）有一个最坏情况下的运行时间O(m^2.81)，目前已知最快的归功于 Coppersmith和Winograd（1987；1990），有时间复杂度O(m^2.367)。（看Strassen（1990）的一个历史记录，以图形化地绘制在图1）不幸的是，牵涉提高 Strassen的结果的次立方算法的常数是如此之大，以至于这些快速算法不能在实践中使用。至于Strassen方法本身，它的实用性是模糊的：实证研究表明， “cross-over”点——在这个矩阵尺寸使用 Strassen的方法变得更好——是100以上(Bailey, 1988; Thottethodi,Chatterjee, and Lebeck, 1998)。总之，尽管几十年的研究工作，却很少成功找到一个清晰实用、简单、快速的矩阵乘法算法。