第 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:
  fprintf(stderr,"reject\n");
  return 2;
 accept:
  fprintf(stderr,"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:
      fprintf(stderr,"reject\n");
      return 2;
    }
  }
  if(s==STATE3){
    fprintf(stderr,"accept\n");
    return 0;
  }else{
    fprintf(stderr,"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 とマッチする任意の箇所で受理状態になりますので、受理した回数を数え ることでマッチする個数を知ることができます。

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

また、もともとの受理状態 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

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

1. abb
2. abab
3. abba

10-3. 正規表現の入力

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

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

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

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

演習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){
	  buffer[i++]=c;
	}else{
	  fprintf(stderr,"Overflow\n");
	  return 1;
	}
      }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(void){
  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;
  }    
  return 0;
}

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