---------- SED 教室 第十一回 「正規表現、再論」 ---------- SED のもっとも強力な機能である「タグ付き」正規表現は、SED 教室第七回で 紹介しました。そのとき、「\1」は「\(」「\)」で記憶した文字列を呼び出すた めの*正規表現*と紹介した事を覚えてますでしょうか。 今までの SED 教室では「\1」は置換文字列中でしか使いませんでした。しか し「\1」は正規表現ですから、当然正規表現文字列中で使うことが出来るのです。 たとえば次のような正規表現を考えます。 ^\(.*\)\1$ 「.*」にマッチした文字列が「\1」で呼び出されます。つまり、「.*」にマッ チした文字列と同じものが「\1」の位置に現れる時、この正規表現はパターンス ペースにマッチするのです。たとえばパターンスペースが次の場合マッチします。 「abcabc」 「.*」に前半の「abc」がマッチする時、「\1」は「abc」と同じ意味になりま す。従って「\1」は後半の「abc」にマッチするわけです。結局、正規表現 「^\(.*\)\1$」は同じ二つの文字列からなる行にマッチしますね。たとえば次に 示すような行にです。 --------------------------------------- わんわん にゃんにゃん --------------------------------------- 「\1」が正規表現中で使えると説明しましたが、もちろん「\2」,「\3」など も同様です。 では次のスクリプトは、どんな動きをするでしょうか。 <<< PALIND.SED >>> --------------------------------------- 1 h 2 :loop 3 s/^\(.\)\(.*\)\1$/\2/ 4 t loop 5 /^$/b disp 6 /^.$/b disp 7 d 8 :disp 9 g --------------------------------------- 三行目の置換命令で、正規表現中に「\1」が使われています。「^\(.\)」ですか らパターンスペースの最初の一文字が記憶されます。従って「\1」はその文字と 同じ意味になります。たとえばパターンスペースが「トマト」だったとすると、 「\1」は「ト」になります。「.*」は任意の文字列にマッチしますから、この場 合「マ」にマッチしますね。結局この置換によりパターンスペースの内容は「マ」 になります。つまり先頭の文字と末尾の文字が等しいときのみ置換が行われ、先 頭と末尾の文字を削除した文字列に置換されます。 置換が行われたときは、四行目の命令「t」で二行目にジャンプして再び置換 が行われます。これを繰り返して置換が出来なくなったとき (つまり先頭の文字 と末尾の文字が異なるとき) 五~六行目でパターンスペースの文字列の長さが 0 または 1 の時のみ八行目にジャンプし、ホールドスペースに保存しておいた文 字列を標準出力に吐き出します。 どんな文字列が吐き出されるかって? ほとんど自明だと思いますが、例をあ げておきましょう。 --------------------------------------- たけやぶやけた しんぶんし AKASAKA --------------------------------------- ほかにどんな文字列があったかな? :-) さて、UNIX には「uniq」というコマンドがあります (多分 ASCII Tools にも あります)。このコマンドは同一の行が連続する場合、それらを一つにまとめる フィルタです。たとえば <<< INPUT.TXT >>> --------------------------------------- Apple Apple Apple 時計 --------------------------------------- を入力すると --------------------------------------- Apple 時計 --------------------------------------- を出力します。この uniq コマンドの動作を SED で真似してみましょう。 <<< UNIQ.SED >>> --------------------------------------- 1 $!N 2 /^\(.*\)\n\1$/!P 3 D --------------------------------------- 一行目の「N」と三行目の「D」により、パターンスペースには常に標準入力の 連続する 2 行が保持されます。二行目の正規表現は、この 2 行が等しいときマッ チします (「\n」はセグメントの区切りでしたね。)。条件に「!」があるのでマッ チしなかったときのみ条件が成立し、最初のセグメントが標準出力に吐き出され ます。つまり次の行と同じでない行のみを吐き出すのです。 uniq コマンドには -c オプションを指定できます。指定すると連続する同一 行の行数を付加します。たとえば <<< INPUT.TXT >>> を入力した場合は次のよ うな出力が得られます。 --------------------------------------- 3 Apple 2 1 時計 --------------------------------------- uniq -c は SED 教室第九回で紹介した、数字を 1 増やすテクニックを使えば 簡単に実現できます。 <<< UNIQC.SED >>> --------------------------------------- 1 x 2 1s/.*/ / 3 H 4 y/ 0123456789/11234567890/ 5 G 6 s/.*\([^0]0*\)\n.*\n\(.*\)[^9]9*$/\2\1/ 7 x 8 s/\n.*// 9 $!N 10 /^\(.*\)\n\1$/!{ 11 x 12 G 13 s/\n/ / 14 P 15 s/.*/ / 16 x 17 } 18 D --------------------------------------- ほとんど SED 教室第九回で紹介した <<< NUMBER.SED >>> と同じですから簡 単ですね。 <<< UNIQC.SED >>> はいろいろな応用が出来ます。ここでは一例として英文の 単語毎の出現回数を数える方法を考えます。 まず最初に英文から単語を切り出して、一行に一単語づつ並べます。スクリプ トは次のようになるでしょう。 <<< VOC.SED >>> --------------------------------------- 1 y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxyz/ 2 s/[^a-z][^a-z]*/\ 3 /g 4 s/\n$// 5 s/^\n// 6 /^$/d --------------------------------------- たとえば次のような英文に対し、 <<< INPUT.TXT >>> --------------------------------------- A nondeterministic finite automaton is the essential concept of the theory of formal language. It is also closely related to the coding theory, and plays an important role in various applications. It is, therefore, very important to investigate and understand the properties of nondeterministic finite automata. In this thesis, the minimum nondeterministic finite automata equivalent to the given automaton are discussed, and the minimization algorithm is presented. < 以下略 > --------------------------------------- sed -f voc.sed INPUT.TXT を実行すると、次のような出力が得られます。 --------------------------------------- a nondeterministic finite automaton is the essential concept of the theory of formal language it is also closely < 以下略 > --------------------------------------- さらにこの出力をアルファベット順に並べ換えます。並べ換えには sort コマ ンドを使います。sort は元は UNIX のコマンドですが、MS-DOS 上で動く sort コマンドも各種配布されているようです。 sed -f voc.sed INPUT.TXT | sort を実行すると次のように出力されます。 --------------------------------------- a a a algorithm algorithm algorithm algorithm algorithm all all all all also also always always an < 以下略 > --------------------------------------- これを UNIQC.SED に入力すれば単語毎の出現頻度を数える事が出来ます。さ らに :-) その出力を sort すると出現頻度の高いものから順に並べる事が出来 ます。私の修士論文全文 (thesis.tex) を入力してみました。 --------------------------------------- A>sed -f voc.sed thesis.tex | sort | sed -f uniqc.sed | sort -r 563 s 535 the 297 automaton 291 of 278 a 224 is 222 n 203 in 147 to 121 and 118 m 114 states 113 r 106 delta 103 i < 以下略 > --------------------------------------- 「the」より出現頻度が高い単語が現れてしまった。三位に「automaton」が出 てくるのは論文のテーマだから当然かな? なお sort の -r は逆順にソートす るためのオプションです。ついでに言いますと、この出力の行数を数えると使用 単語数を知ることが出来ます。 --- GCD03723 (Greatest Common Divisor:最大公約数)