3.7 Awk 和Perl

为使这个演习比较圆满，我们也用两个应用广泛的脚本语言(Awk 和Perl)写了这个程序。这些语言都提供了本应用所需要的各种特征，包括关联数组和字符串处理等。

关联数组实际上是散列表的一种包装，使用起来非常方便。它看起来像数组，但可以用任意的字符串或数，或者字符串和数的由逗号分隔的表作为下标。关联数组也是一种从一个数据类型到另一类型的映射。在Awk 里，所有数组都是关联数组；Perl则不同，这里既有以整数作为下标的普通数组，也有关联数组—称为“散列”，这实际上也说明了它们的实现方法。

在程序的Awk 和Perl实现里，前缀长度都固定为2。

Awk 是一个模式—操作对的语言：输入总以一次一行的方式读入，每个读入行都拿来与程序里的模式做匹配，与此同时，对各个成功匹配执行有关动作。这里存在着两个特殊的模式，BEGIN和END，它们分别能在输入的第一行之前和最后一行之后匹配成功。

动作是由花括号括起的一个语句块。在上面的Awk 版本的马尔可夫程序里，BEGIN动作块对前缀和若干其他变量做初始化。

随后的一个语句块没有模式部分，这是一种默认方式，意味着这个块将对每个输入行执行一次。Awk 自动把每个读入的行分割成一些域(由空白分隔的词)，它们将分别成为$1到$NF。变量NF的值是域的个数。语句：

建立从前缀到后缀的映射。数组nsuffix记录后缀个数，其元素nsuffix[w1, w2]记录与前缀对应的后缀的个数。而后缀本身则被做为数组statetab的元素，如statetab[w1, w2, 1]，statetab[w1, w2, 2]，等等。

当END块执行时，所有内容都已经输入完毕。到这个时刻，对于每个前缀，nsuffix里都有一个元素记录着它对应的后缀个数，而在statetab里则存有相应个数的后缀。

用Perl语言写出的东西与此类似，但是需要另外用一个匿名数组(而不是用第三个下标变量) 来保存后缀的有关情况。这里还需要用一个多重赋值完成对前缀的更新。Perl采用特殊字符表示变量的类型，$表示标量，@表示有下标的数组。这里的[ ]用于下标数组，而{}表示散列。和前面程序一样，映射本身保存在变量statetab里。程序中最关键的行是：

它把一个新后缀加入到存储在statetab{$w1}{$w2}的匿名数组的最后。在随后的生成阶段里，$statetab{$w1}{$w2}是对后缀数组的一个引用，而$suf->[$r]指向其中的第r个后缀。

与前三个程序相比，用Awk 和Perl写的程序都短得多，但要把它们修改为能处理前缀词不是两个的情况却很困难。采用C++ 的STL实现，其核心部分(函数add和generate)看起来长一点，但是却更清晰。无论如何，脚本语言对有些情况是很好的选择，例如做试验性的程序设计，构造系统原型，以及做那些对运行时间要求不高的实际产品。

练习3-7 修改上面的Awk 和Perl程序，设法使它们能处理任意长度的前缀。通过试验确定这种修改对性能的影响。