Regular expression 与 GNU grep 的中文化

《专题报导》

  Regular expression 与 GNU grep 的中文化

              (作者　邱展毅)

      一、前言

      打开电视、收音机、报章杂志，细心的你也许已发觉到资讯量正
    快速的成长中。若你连上网际网路(Internet)，相信News、BBS、
    Gopher、WWW(Word Wide Web)的资讯量更会使你看的目不暇给。聪
    明的你会如何运用这些资讯呢？或者已被这庞大的资讯巨兽逼迫的
    不知所措？

      对生活在资讯高度膨胀环境下的现代人而言，拥有好的检索工具
    ，以过滤出真正有用的资讯，的确是一件不可或缺的事！本文将介
    绍在UNIX上常用的一个检索工具---grep，并说明以GNU grep为基础
    ，所完成可处理「中文regular expression」的工具---cgrep。

      二、Regular expression

      Regular expression可分为Standard regular expression 及
    Extended regular expression，前者之组成元素为：普通字元、^
    、、〔...〕、． 、＊、－、〔^...〕、掤、痎、、m,n；后者除了
    前者之组成元素外，增加了四个运算子：＋、？ 、（...）及｜。
    regular repression是一种很值得推崇的字串表达方式，可以简化
    许多复杂的字串处理工作，提升工作效率。然而本文的重点并不是
    介绍它的使用方法，故仅列举几个实例于【表一】以供参考。有兴
    趣的读者可参考本通讯第十一卷05、06两期之「Regular
    Expression简介」一文或UNIX指令Sed、egrep之man page。

      表一 regular expression使用实例
┌─────────────────────────────┐
│1、"[Tt]here"表示字串"There"或"there"。 │
│2、"tr.*al"表示以"tr"开始，"al"结束的所有字串。 │
│3、"[a-zA-Z]/{0,20/}"表示由0-20个英文字母(不分大小写)所组│
│ 成的字串。 │
│4、"[Tt]here｜tr.*al｜[a-zA-Z]/{0,20/}表示满足上述1、2或3 │
│ 之所有字串。 │
└─────────────────────────────┘

      UNIX上有许多已被广泛使用的工具，诸如grep、egrep、awk、
    sed、vi、emacs...等，这些工具皆可使用regular expression来指
    定欲找寻的字串，并可结合各工具的其他功能，对找到的资料做进
    一步的处理，使得它们成为功能强大且受欢迎的工具。

      不过令人感到遗憾的是这些好用的工具所支援的regular
    expression，到目前为止仅可处理ASCII字元(注一)所组成的
    regular expression，如【表一】所列出的例子。对于 Big5中文码
    的处理，常有预期之外的结果产生，使得使用者无法完全信任这些
    工具，而必须多做一些检验的动作，造成使用上的不便及时间的浪
    费！ 【表二】说明造成这种情况的原因。

      表二 regular expression与Big5中文字
┌─────────────────────────────────────┐
│1.Big5中文码(2bytes code)之组成形式如下图所示： │
│ ┌───────┬───────┐ │
│ │ High Byte │ Low Byte │ │
│ ├───────┼───────┤ │
│ │ 0xA1-0xFE │ 0x40-0x7E │ │
│ │ │ or │ │
│ │ │ 0xA1-0xFE │ │
│ └───────┴───────┘ │
│2.由上图可看出Big5中文字之high byte及low byte有重复部分（0xA1-0xFE）。若 │
│ 中文字之high byte及low byte皆落在0xA1-0xFE 这个范围内，则可能产生第一个│
│ 中文字的low byte与第二个中文字的high byte所组成的字仍是一个合法中文字的│
│ 情形，这就是造成混淆的原因之一。例如：资、料、网、不、中、之、互、仍、今│
│　、内、分、及、天、太、少、手、全、文、方、日、月、它、必、用、民...，这│
│　些常用到的字都是会产生混淆的字。 │
│ │
│3.会产生混淆的字共有8050个(Big5 A4A1-F9DC)，若包括全形符号及造字区，则不只│
│ 这些。 │
│ │
│4.Regular expression所构成的样式(pattern)若含有运算子'． '、'＊'、/{m,n/}、│
│ 〔...〕，当与中文字做比对时，可能会将中文字截一半。例如：pattern="资．" │
│ 并不会找到"资讯"，只找到"资"及"讯"的high byte。 │
│ │
│5.Regular expression之character class运算子〔...〕内部只能辨识1byte字元(a │
│ 、z、3...)，无法辨识2bytes字元(Big5中文码)。例如：pattern="资〔讯料〕"无│
│ 法正确比对"资讯"或"资料"等字串。 │
└─────────────────────────────────────┘

      假若我们能解决【表二】所列出的问题，对Big5 中文环境的使
    用者而言，相信会是一个很好的消息！基于这个理念，我们首先完
    成了GNU grep的中文化，解决了上述问题，为各位呈献一个支援全
    中文regular expression的好工具。

      三、GNU grep的中文化

      传统UNIX指令中， grep家族---grep、egrep、fgrep(注二)是一
    组非常好用而且使用频率相当高的检索工具。藉由它们，可以从一
    群资料档中过滤出我们想要的资料，进而提供我们有用的资讯。不
    过若将其应用于检索中文资料，可能常有受骗的感觉！底下说明中
    文化的动机与过程：

      1.中文化动机---从资料档(test.doc)中检索资料
       ┌─────────────────────────┐
       │ 搜集相关资料。 │
       │ 以正确的资讯做判断。 │
       │ 全文检索满足您的需要。 │
       │ 之乎者也成功的中文化。 │
       │ 在浏灠画面中即无法显示出来。 │
       │ 拥有全文检索系统使您的工作更加有效率。 │
       │ This is the hour Madam Entreated me to call her. │
       └─────────────────────────┘

      例一、执行egrep "的｜之" test.doc，结果如下：
      ┌───────────────────┐
      │以正确的资讯做判断。 │
      │ -- │
      │全文检索满足您的需要。 │
      │ -- │
      │之乎者也成功的中文化。 │
      │在浏灠画面中即无法显示出来。 │
      │ ---- │
      │拥有全文检索系统使您的工作更加有效率。 │
      │ -- │
      └───────────────────┘

      检索结果的第四列并没有'的'或'之'两个字，为何该列会被选出
    来呢？原因是Big5码'中'(内码A4A4)的low byte与'即'(内码A759)
    的high byte 恰巧合成'之'(内码A4A7)这个字，因而产生误判的情
    形。

      例二、执行grep ``[站立]'' test.doc，结果如下：
      ┌───────────────────┐
      │搜集相关资料。 │
      │以正确的资讯做判断。 │
      │全文检索满足您的需要。 │
      │之乎者也成功的中文化。 │
      │在浏灠画面中即无法显示出来。 │
      │拥有全文检索系统使您的工作更加有效率。 │
      └───────────────────┘

      可以很清楚的看出test.doc内并不含'站'或'立'这两个字，但却
    选出了六列资料。若资料量很大，要想去除这种中文字误判的情形
    ，可真是一件恼人的工作！

      2.中文化的过程

      GNU grep有完整的原始程式码，并且在「GNU General Public
    License」的规范下，任何人皆可以自由的拥有、修改及传播它。这
    对于想要拥有一个好的中文化工具的我们，的确是一个好消息！

      GNU grep具备传统UNIX指令grep家族之功能，且几乎完全相容。
    其与grep家族之对应如【表三】所示：

      表三 GNU grep 与 UNIX grep家族
     ┌────┬───────┬───────────┐
     │GNU grep│UNIX grep家族│regular expression │
     ├────┼───────┼───────────┤
     │grep(-G)│grep　　　　　│standard regular exp. │
     ├────┼───────┼───────────┤
     │grep -E │egrep　　 │extended regular exp. │
     ├────┼───────┼───────────┤
     │grep -F │fgrep　　 　　│不支援regular exp. │
     └────┴───────┴───────────┘

      GNU grep 使用三种字串搜寻方法(matcher)，分别为KWS matcher
    、DFA matcher及regex matcher。对于完整字串(注三)所构成的样
    式(pattern)，使用KWS matcher 即可完成检索的工作。而 Regular
    expression 所构成的样式，若不含Back-reference 运算子(，-)，
    使用KWS matcher及DFA matcher即可完成检索工作；若含有
    Back-reference运算子，则须再使用regex matcher方可完成检索的
    工作。 【表四】列出GNU grep使用各matcher的情形。

      表四 GNU grep使用的检索方法
      ┌─────┬────────────┐
      │GNU grep │ 检索方法 │
      ├─────┼────────────┤
      │grep(-G) │ KWS、DFA、Regex matcher│
      ├─────┼────────────┤
      │grep -E │ KWS、DFA、Regex matcher│
      ├─────┼────────────┤
      │grep -F │KWS matcher │
      └─────┴────────────┘

      由于regex matcher的检索速度很慢，且DFA matcher已含盖KWS
    matcher的检索功能，故我们只针对DFA matcher进行中文化(不考
    虑Back-reference运算子)。 DFA matcher的理论架构即是
    Compilers 书上所提的「确定性有限自动机」(Deterministic
    Finite Automata)，该方法效率佳，但须耗用较多的记忆空间。

      GNU grep的原始程式使用bit map 的方式来建立状态移转表
    (transition table)，这对处理1byte字元(0-255)是一个效率很好
    的方法。不过若用这个方法为数量庞大的中文字(Big5 2bytes
    code)建立状态移转表，大量的记忆空间需求，并不是一般电脑所能
    负荷的。因此我们以集合的观念(交集、余集、差集、...)改写bit
    map的方法，使得记忆空间维持在可接受的状况。当然效率与空间是
    一个很难取舍的问题，新的方法执行速度虽然比不上原来的方法，
    但仍不致于太差。

      要能做到彻底的中文化，中文字与其它字元(例如：ascii或
    0-255)都必须以一个完整字元的观念来处理，而不是将Big5中文码
    拆成二个ascii code分别处理。这一点在对 GNU grep 进行中文化
    的过程皆已考虑到，也因此regular expression中的'． '可以代表
    一个英文字或一个Big5中文字；'资〔讯料源〕'可以找到「资讯」
    、「资料」或「资源」等词，不再有受骗的恐惧了。


      四、效能测试

      要知道一个工具的性能好坏，一份完整的测试报告是最具说服力
    的。以下就是我们对中文化的GNU grep所做的效能测试(测试环境
    为SUN SPARCCenter 2000上执行SunOS 5.4)，并与未中文化的GNU
    grep及 UNIX 上的 egrep 作一比较。 (中文化后的GNU grep我们以
    cgrep来命名)。

      表五 测试时所使用的样式(pattern)
┌───┬────────────────────────────────┐
│ │ pattern(s) #│
├───┼────────────────────────────────┤
│pat. 1│ window 1│
├───┼────────────────────────────────┤
│pat. 2│window|/<the/>|pat.*n|disk|easy 5│
├───┼────────────────────────────────┤
│pat. 3│window|/<the/>|pat.*n|disk|easy|grand|happy|mouth|noun|open 10│
├───┼────────────────────────────────┤
│pat. 4│window|/<the/>|pat.*n|disk|easy|grand|happy|mouth|noun|open| │
│ │quit|quiz|rich|string|teach|limit|vesa|wear|xray|year 20│
├───┼────────────────────────────────┤
│pat. 5│window|/<the/>|pat.*n|disk|easy|grand|happy|mouth|noun|open| │
│ │quit|quiz|rich|string|teach|limit|vesa|wear|xray|year|zone| │
│ │zoo|bolck|blank|people 25│
├───┼────────────────────────────────┤
│pat. 6│window|/<the/>|pat.*n|disk|easy|grand|happy|mouth|noun|open| │
│ │quit|quiz|rich|string|teach|limit|vesa|wear|xray|year|zone| │
│ │zoo|bolck|blank|people|monney|splin|shift|pause|scroll| │
│ │enter|custom|friend|share|close|match|philo|phy|compact| │
│ │stock|head|trail|hair|eye 60│
└───┴────────────────────────────────┘

      【表五】为测试时所使用的样式(pat.1-6)，其中第三栏(＃)内的
    数字表示该样式是由几个子样式(subpattern)所组成。 【表六】内
    之数字为程式执行时所花费的实际时间(real time；单位：秒)。若
    将测试结果以曲线图表示，可以更清楚的看出egrep、 grep -E 及
    cgrep -E之执行效率。如【图一】所示，可以很清楚的看出，egrep
    之时间曲线几乎为指数成长，而grep -E与cgrep -E 则为线性成长
    ，且曲线有渐趋平缓的倾向。

      表六 egrep、grep -E、cgrep -E 测试结果
    ┌────┬───┬───┬───┬───┬───┬───┐
    │＃---＞ │pat. 1│pat. 2│pat. 3│pat. 4│pat. 5│pat.6 │
    ├────┼───┼───┼───┼───┼───┼───┤
    │ │ 1 │ 5 │ 10 │ 20 │ 25 │ 60 │
    ├────┼───┼───┼───┼───┼───┼───┤
    │egrep │ 4.4 │ 4.6 │ 5.0 │ 22.2 │ 39.8 │ 467.7│
    ├────┼───┼───┼───┼───┼───┼───┤
    │grep -E│ 0.6 │ 3.0 │ 3.0 │ 3.3 │ 3.7 │ 7.9│
    ├────┼───┼───┼───┼───┼───┼───┤
    │cgrep -E│ 9.7 │10.0 │ 15.0 │ 17.0 │ 18.2 │ 20.9│
    └────┴───┴───┴───┴───┴───┴───┘

      图一 egrep、grep -E、cgrep -E之曲线图


      五、结语

      由计算中心开发完成的「中文全文检索资料库」目前已有文字版
    及WWW(Word Wide Web)版本，使用者已遍及世界各学术领域。为了
    让使用者能更灵活的使用这个资料库，我们已着手进行加入
    wildcard字元（＊、？）的检索功能到这个资料库内。

      检索时，要完成单一样式(pattern)结合wildcard字元的检索功
    能可以轻易的做到，不过结合多个样式(multipattern)与wildcard
    字元的检索功能，若要维持高效率的检索能力，仍得多下点功夫。

      欲达到多个样式(multipattern)与wildcard字元的检索功能，
    regular expression是直觉可以运用的好方法，它在UNIX 上已被
    广泛运用(例如：grep、egrep、awk、sed、vi、emacs，...)，并且
    可能已有完整的C Library可供使用(注四)。

      我们查阅许多演算法相关书籍，并希望能找到UNIX上结合
    multipattern与regular expression的检索工具---egrep所使用的
    演算法。在这个过程中测试了egrep、agrep(注五)及GNU grep的功
    能与执行效率，并阅读agrep 及GNU grep的部份程式码。评估后，
    由于GNU grep有完整的程式，并已支援extended regular
    expression(．、＊、｜、...)，故选定GNU grep有关regular
    expression之相关程式作深入了解，进而完成DFA module之中文化
    ，这就是cgrep中文化的由来。

      cgrep是在强化「中文全文检索资料库」功能的途中，所获得的附
    加成果，相信对许多人的工作会有所帮助，因此先提出来与各位分
    享！不过，截至目前为止，要完成wildcard 字元与multipattern
    的全文检索功能，仍有许多技术上的瓶颈等待突破，期待能早日提
    供各位一个更完整的「中文全文检索资料库」。

      注

      目前支援regular expression的工具，通常只处理ASCII字元
    (0-127)组成的regular expression，顶多也只扩充到处理字元
    0-255(即8bits字元，或称1byte字元)。至于中文字的处理，有些工
    具并不支援，或者只支援由EUC(Extended UNIX Code)构成的中文
    字。对于使用最广泛的Big5中文码--- 2bytes字元，现有工具上之
    regular expression并无法正确的表示。

      理想上应该只有一个grep指令，而非grep家族(grep、egrep、
    fgrep)，以减少使用者因记忆太多指令而造成混淆或误用的情况。
    然而权衡效率与记忆空间使用的情形，要找到一个既节省空间且有
    效率的演算法，实在不是一件容易办到的事。 grep家族即是使用不
    同的演算法(DFA、NFA、...)分别完成，以确保其能有较佳的执行表
    现。

      完整字串是由不含'＊'运算子的regular expression所构成。以
    实例来说明完整字串的含义：字串``happy''、``the｜之｜
    people''皆为完整字串所构成的样式(pattern)；而字串``hapy''、
    ``[Tt]he｜peoe｜〔之的〕''则不是由完整字串所构成的样式。

      UNIX C 上有几组处理regular expression的library function
    ，例如：【compile()，step()】、【recomp()，reexec()】。经研
    读其man page 及实际测试后，发现它们只支援standard regular
    expression而不支援extended regular expression，故无法运用于
    muliti-pattern之检索需求。

      agrep为中正大学吴升(Sun Wu)老师的作品。它除了拥有 grep 的
    功能外，并提供许多新的功能，例如：容错搜寻及样式间的逻辑运
    算(AND、OR)，不过仍有许多使用上的限制。另外，吴老师有一项新
    作品GAIS(Global Area Information Servers)，是一个多用途的资
    讯搜寻系统，有兴趣的读者可以使用WWW Browser连至
    http://gais.cs.ccu.edu.tw，以获得更详细的讯息。

      (在进行GNU grep 中文化的过程中，感谢工作站袁天竑、陈弘哲
    两位同仁热心协助，提供最新的程式(source code)及技术手册，同
    时，更感谢林晰先生细心的指导，使得本文得顺利完成)。