第 10 回文字列検索

本日の内容

10-1. 決定性オートマトンとプログラム
10-2. 決定性オートマトンと非決定性オートマトンとの等価性
10-3. 正規表現の入力
10-4. オートマトンの出力
10-5. 参考: P=NP問題

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

10-1. 決定性オートマトンとプログラム

次の状態への遷移が曖昧でないオートマトンは決定性オートマトンと言いましたが、これをプログラムにするのは簡単です。一番素朴なのは状態をラベルに対応させ、各遷移を goto 文で表現する方法です。但し、 goto は現在余り使われなくなりました。さらに、 Java では予約語になっていますが使えません。

例10-1

前回紹介したオートマトンの例は決定性です。これは goto 文を使うと、以下のようなプログラムになります。


#include <stdio.h>
int get(void){
  int c;
  while((c=getchar())=='\n');
  return c;
}
int main(void){
 int c;
 label1:
  c=get();
  if(c=='A'){ goto label2;}
  if(c=='C'){ goto label3;}
  goto err;
 label2:
  c=get();
  if(c=='A'){ goto label2;}
  if(c=='B'){ goto label3;}
  goto err;
 label3:
  c=get();
  if(c==EOF){ goto accept;}
  if(c=='B'){ goto label1; }
  goto err;
 err:
  printf("reject\n");
  return 2;
 accept:
  printf("accept\n");
  return 0;
}

注

通常キー入力は Enter キーを押して初めて有効になりますが、Enter キーを押すと入力文字列に \n が含まれてしまいます。そのため、 \n を読み飛ばすように get 関数を作っています。

そこで利用するのはループ中で switch 文により状態と case を対応させる方法です。これにより作ったプログラムは以下のとおりです。ここで列挙型 enum は複数の値をとる変数に対して、その値に意味のある名前を付ける機能です。このように状態を表す時などに、状態に名前を付けて管理できるようになります。


#include <stdio.h>
typedef enum status {
  STATE1, STATE2, STATE3, ERROR, ACCEPT}
STATE;
int get(void){
  int c;
  while((c=getchar())=='\n');
  return c;
}
int main(void){
  char c;
  STATE s;
  s=STATE1;
  while((c=get())!=EOF){
    switch(s){
    case STATE1:
      if(c=='A'){ s=STATE2; }
      else if(c=='C'){ s=STATE3; }
      else{ s=ERROR; }
      break;
    case STATE2:
      if(c=='A'){ s=STATE2; }
      else if(c=='B'){ s=STATE3; }
      else{ s=ERROR; }
      break;
    case STATE3:
      if(c=='B'){ s=STATE1; }
      else{ s=ERROR; }
      break;
    case ERROR:
      printf("reject\n");
      return 2;
    }
  }
  if(s==STATE3){
    printf("accept\n");
    return 0;
  }else{
    printf("reject\n");
    return 2;
  }
}

演習10-1

自然数を受理する決定性オートマトンを作り、それをプログラムに直しなさい。

10-2. 決定性オートマトンと非決定性オートマトンとの等価性

本章では非決定性オートマトンが決定性オートマトンに変換できることを示します。非決定性オートマトンでは一つの状態から複数の状態へ遷移します。そして、次々と遷移した後、一つでも受理状態へ遷移する遷移の仕方があれば入力を受理します。そこで遷移可能な状態のリストを考えます。そのリストの各要素に対して、入力を適応して、次に遷移可能な状態のリストを作ります。非決定性オートマトンではあらかじめ状態数が決まってますので、遷移可能な状態のリストも全状態の中から選ぶことで作れます。したがって、遷移可能な状態のリストの数も有限個になります。例えば、非決定性オートマトンの状態として 1, 2 ,3 の三つの状態があったとします。その時、遷移可能な状態のリストは、{1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} の七通りになります。そして、これらのリスト同士の間で、入力が与えられた時、どのリストへ遷移可能かを考えます。このように、遷移可能な状態リスト間で、入力による相互の移り変わりを決めることができます。これは、入力により一意に次のリストが決まるので、決定性オートマトンになります。開始状態一個だけのリストを新たな開始状態とし、もとの受理状態を含むすべてのリストを新たな受理状態とします。

ではここで例を示します。例えば、正規表現 .*aab を受理する非決定性オートマトンは次のようになります(簡単のため、入力アルファベットを a と b に限ってます)。

このように先頭に任意の文字列の存在を許す正規表現は、長い文字列において aab とマッチする任意の箇所で受理状態になりますので、受理した回数を数えることでマッチする個数を知ることができます。

さて、この非決定性オートマトンを決定性オートマトンに変換します。但し、開始状態から到達可能な状態だけしか必要ないので、開始状態から処理を始めて、必要な状態のみを書き出します。

状態リスト	入力	遷移先の状態リスト
1	a	1,2
1	b	1
1,2	a	1,2,3
1,2	b	1
1,2,3	a	1,2,3
1,2,3	b	1,4
1,4	a	1,2
1,4	b	1

また、もともとの受理状態 4 を含むリストを新たな受理状態とします。

この決定性オートマトンを元に、入力文字列から.*aab と一致する回数を求めるプログラムを示します。なお、ここでは有限個の状態を変数に収めるため、C 言語の列挙型という型宣言を使いました。これは num 列挙型名 { 名前リスト }; で定義します。また、これは typedef の使用もできます。


#include <stdio.h>
typedef enum st { s1, s12, s123, s14 } STATUS;
int get(void){
  int c;
  while((c=getchar())=='\n');
  return c;
}
int main(void){
  int c;
  int count=0;
  STATUS s=s1;
  while((c=get())!=EOF){
    switch(s){
    case s1:
      if(c=='a'){ s=s12; }
      else if(c=='b'){ s=s1; }
      break;
    case s12:
      if(c=='a'){ s=s123; }
      else if(c=='b'){ s=s1; }
      break;
    case s123:
      if(c=='a'){ s=s123; }
      else if(c=='b'){ s=s14; count++;}
      break;
    case s14:
      if(c=='a'){ s=s12; }
      else if(c=='b'){ s=s1; }
      break;
    }
  }
  printf("%d\n",count);
  return 0;
}

演習10-2

次の文字列が含まれる回数を数えるプログラムを作りなさい。

abb
abab
abba

10-3. 正規表現の入力

前回の手法では、非決定性オートマトンから決定性オートマトンを構成してました。そのため、遷移可能な状態なリスト間の関係を求めてました。しかし、これを行うと、非決定性オートマトンの状態数を m とした時、 $O (2^{m})$ 個のリスト間の関係を調べなければなりません。これは、例えば正規表現を入力させるようなプログラムでは入力に対する効率が非常に悪くなります。

ここでは、正規表現を文字列として与え、入力に何箇所マッチするかを効率良く計算する方法を考えましょう。文字列の長さを m とし、入力の長さを n とします。

駄目な方法は、正規表現に対応した非決定性オートマトンを作り、決定性オートマトンに変換してから入力を一文字ずつ見ていく方法です。こうすると決定性オートマトンへ変換する手間を考慮しなければならないので、必要な計算量は $O (2^{m} + n)$ となります。

そこで、決定性オートマトンを完全に作らずに入力を読むことを考えます。そのためには正規表現や、非決定性オートマトンだけを使って入力を判断する必要があります。そこで、非決定性オートマトンに対して、非決定的な状態遷移をそのまま計算することを考えます。ある瞬間に遷移可能な状態は複数存在しますが、それは高々正規表現の長さ m 程度です。そして、その遷移可能な状態のそれぞれについて、入力文字を与えると、次に遷移可能な状態を計算することができます。次に遷移可能な状態も高々 m 個なので、そのための手間は結局 $O (m)$ で計算できます。入力一文字に対して $O (m)$ の手間がかかるので、全体では $O (m n)$ の手間がかかります。

演習10-3

正規表現を解釈するには、カッコの解釈などが必要なため、それ自体文法によって解析しなければなりません。そこで、ここでは簡単のために、正規表現の一部である文字列を入力と仮定し、その文字列を何回含むかを計算するプログラムを作りなさい。

演習10-4

指定した文字列を含む行を表示するプログラムを作りなさい。

参考

UNIX 系の OS では正規表現とマッチする行を表示するプログラム grep が用意されています。また、Windows には findstr コマンドが用意されてます。

10-4. オートマトンの出力

文字列に対して正規表現やオートマトンにより部分列を抽出することを考えます。正規表現において、通常抽出する部分を () (丸カッコ)で括って表現します。例えば、自然数を取り出したいときは、.*([1-9][0-9]*)のように表現します。

なお、受理する文字列は終了状態にたどり着けば一応得られることになります。但し、上記の例のような自然数の表現の中に自然数が含まれるような状況の場合、さらにルールが必要になります。つまり、 12345 のような文字列の場合、「1」「2」「3」「4」「5」と全て分割するのか、「1」「12」「123」「1234」「12345」「2」... と全ての場合を出力するのか、それとも「12345」とするのか。これはケースバイケースになりますが、通常は最長一致となる「12345」を選択することが多いと思います。

最長一致した部分を取り出すには、まずその部分を示すオートマトンを作ります。基本的にはプログラムは初期状態から、そのパターンに入る先頭文字を読んだらバッファへの記憶を開始します。そして、受理状態に入ったらバッファの内容を書き出す準備をします。そのまま拒否状態に入らなければ解釈をどんどん続けていきます。そして、最終的に拒否状態になるまで入力を読み、その時点で直前の受理状態に準備したバッファの内容を出力します。

繰り返し同一パターンで最長一致部分を出力しつづけるプログラムを作るには、上記の拒否状態になった時点で初期状態に戻っている必要があります。これを実現するために安易な方法として、一端拒否状態になったら、読み込んだ文字を一文字入力に返してから初期状態に戻す手があります。一方、拒否状態になる入力に対して ε 動作で初期状態に戻るような動きを考えます(入力に応じて遷移しているので実際は ε 動作ではありません)。これを便宜上 λ 動作として、非決定性のオートマトンとみなし、上記と同様の分析で決定性のオートマトンを導く手もあります。

例10-2

ここではテキストファイルから自然数を最長一致で取り出すオートマトンの分析と、プログラム例を示します。

なお、受理状態で入力 0-9 を受け取ると、そのまま受理状態に遷移します。これは初期状態で認識を開始する 1-9 を含んでます。したがって、認識中に受理状態から拒否状態に移る入力を受け取ると、その入力では初期状態から認識が始まらないので、非決定的な λ 動作をするのではなく、単にその他の文字として初期状態に戻せば良いことになります。

C言語


#include <stdio.h>
#define MAX 80
typedef enum {s1, s2} STATUS;
int main(void){
  int c,i;
  char buffer[MAX+1];
  STATUS status=s1;
  while((c=getchar())!=EOF){
    switch(status){
    case s1:
      if(c>='1' && c<='9'){
	i=0;
	buffer[i++]=c;
	status=s2;
      }
      break;
    case s2:
      if(c>='0' && c<='9'){
	if(i>=MAX){
	  fprintf(stderr,"Overflow\n");
	  return 1;
	}
	buffer[i++]=c;
      }else{
	buffer[i]='\0';
	printf("%s\n",buffer);
	status=s1;
      }
      break;
    }
  }
  if(status==s2){
    buffer[i]='\0';
    printf("%s\n",buffer);
  }
  return 0;
}

C++言語


#include <iostream>
#include <string>
typedef enum {s1, s2} STATUS;
int main(){
  char c;
  std::string  buffer;
  STATUS status=s1;
  while(std::cin.get(c)){
    switch(status){
    case s1:
      if(c>='1' && c<='9'){
	buffer=c;
	status=s2;
      }
      break;
    case s2:
      if(c>='0' && c<='9'){
	buffer+=c;
      }else{
	std::cout << buffer << std::endl;
	status=s1;
      }
      break;
    }
  }
  if(status==s2){
    std::cout << buffer << std::endl;
  }
}

Java 言語


import java.util.*;
import java.util.regex.*;
import java.io.*;
class Rei2 {
    public static void main(String arg[]) throws IOException {
	InputStreamReader isr = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(isr);
	String buf;
	Pattern p = Pattern.compile("[1-9][0-9]*");
	Matcher m;
	while((buf=br.readLine())!=null){
	    m= p.matcher(buf);
	    while(m.find()){
		System.out.println(m.group());
	    }	
	}
    }
}

10-5. 参考: P=NP問題

オートマトンに対して記憶装置としてテープを接続したものをチューリング機械と言います。決定性のチューリング機械で計算できるものと、現在のコンピュータで計算できるものは本質的に等価であることが知られています。

入力の長さに対して計算量が多項式の問題について、決定性のチューリング機械で計算できる問題のクラスを P と言い、非決定性のチューリング機械で計算できる問題のクラスを NPと言います。これらが等しいかどうかは計算機科学上で重要な未解決問題で P=NP 問題と言います。

NP 問題に含まれるものに素因数分解、地図の三色彩色可能性問題(平面の地図は四色で塗れる)、巡回セールスマン問題(都市間の交通費がわかっている時全都市を予算内で回れるかどうかを決める問題)などがあります。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 10 回 文字列検索