2009/05/09

正規表現の最適化2

答えから書いてしまうと、「α{a,b}{c,d}」という正規表現はc(b-a)>=a-1もしくはc=dが成立する場合に限り「α{a*c,b*d}」に変換することができる。

証明といえるような内容になっているかどうか判らないが、俺なりに考えた結果を書いてみる。

まず、そもそも論として、「α{a,b}{c,d}」を「α{a*c,b*d}」に変換できるとはどういう意味なのだろうか?

「α{a,b}{c,d}」というのは、昨日も書いたが「とある正規表現αがa回以上b回以下繰り返す」というものがc回以上d回以下繰り返す、という指定である。また「α{a*c,b*d}」とは、とある正規表現αがa*c回以上b*d回以下繰り返すという意味である。

でもって、「α{a,b}{c,d}」を「α{a*c,b*d}」に変換できるというのは、「α{a,b}{c,d}」が実質的に「α{a*c,b*d}」と同じ、すなわち、「α{a,b}{c,d}」という指定により繰り返されるαの個数が、a*c~b*dの範囲内に収まり、かつ、a*c~b*dの全ての値を取るということを意味している。

例えば、「α{2,3}{4,5}」という正規表現を考えてみる。

αの数が最も少ないパターンでは、内側の繰り返しが全部2回で、かつ、外側の繰り返しが4回の場合、合計で8回繰り返す場合である。つまり下記のようになる場合である。

 αα αα αα αα (半角空白は判りやすくするために入れた)

次に少ないのは、内側の繰り返しが2回の奴が3つと3回の奴が1つ、でもって、外側の繰り返しが4回の場合である。つまり、下記のようなパターンである。

 ααα αα αα αα
    あるいは
 αα ααα αα αα
    あるいは
 αα αα ααα αα
    あるいは
 αα αα αα ααα

同様に、最も多くなるのは内側の繰り返しが全部3回で、かつ、外側の繰り返しが5回になる場合である。すなわち、下記のようなパターンである。

 ααα ααα ααα ααα ααα

こうやって考えていくと、「α{a,b}{c,d}」と指定された場合、全体の繰り返し数の最小は必ずa*c回、最大の繰り返し数はb*d回になると言うことができる。

ということは、「α{a,b}{c,d}」による繰り返し回数が、a*c回~b*d回の全てのパターンを取りうるのであれば、「α{a*c,b*d}」に変換できると言うことになる。

ちなみに、「α{2,3}{4,5}」の取りうる繰り返し回数を列挙すると下記のようになる。

外側の繰り返し回数内側の繰り返し回数合計
42,2,2,28
42,2,2,39
42,2,3,29
42,2,3,310
42,3,2,29
42,3,2,310
42,3,3,210
42,3,3,311
43,2,2,29
43,2,2,310
43,2,3,210
43,2,3,311
43,3,2,210
43,3,2,311
43,3,3,211
43,3,3,312
52,2,2,2,210
52,2,2,2,311
52,2,2,3,211
52,2,2,3,312
52,2,3,2,211
52,2,3,2,312
52,2,3,3,212
52,2,3,3,313
52,3,2,2,211
52,3,2,2,312
52,3,2,3,212
52,3,2,3,313
52,3,3,2,212
52,3,3,2,313
52,3,3,3,213
52,3,3,3,314
53,2,2,2,211
53,2,2,2,312
53,2,2,3,212
53,2,2,3,313
53,2,3,2,212
53,2,3,2,313
53,2,3,3,213
53,2,3,3,314
53,3,2,2,212
53,3,2,2,313
53,3,2,3,213
53,3,2,3,314
53,3,3,2,213
53,3,3,2,314
53,3,3,3,214
53,3,3,3,315


重複はあるが、最小の8回(=2*4)から最大の15回(=3*5)の全ての値を取るため、「α{2,3}{4,5}」は「α{8,15}」と同じであると言うことができる。

では、いかなる条件が成立した場合に、「α{a,b}{c,d}」による繰り返し回数がa*c回~b*d回の全ての値を取るのだろうか?

それを明らかにするために、まずは外側の数量子の値が同じだった場合、すなわち「α{a,b}{x,x}」という指定だった場合について考えてみる。つまり、

 命題:{a,b}{x,x}が指定されたとき、任意のax~bxの繰り返し回数を取りうる

の、証明を試みる。

何か泥臭いが、帰納的に証明する。

まず、x=1の場合、すなわち{a,b}{1,1}の場合にa~bの任意の値を取りうるか否かについて考える。{a,b}の指定は、a~b回の任意回の繰り返しであることを示すのだから、{a,b}{1,1}がa~bの任意回の値を取れるのは明らかである。

次に、x=2の場合、すなわち{a,b}{2,2}の場合について考えてみる。

x=2つまり外側の繰り返し回数が2回なので、内側の(a~b回)を2回繰り返す、すなわち、

 (a~b回)+(a~b回)=(2a~2b回)

が成立することを考える。

ここでまた泥臭いが、1回目の内側の繰り返し回数が、a回からb回に変化するのを順番に追っていってみる。

 (a+0回)+(a~b回)=((a+0)+a~(a+0)+b回)=(2a~a+b回)
 (a+1回)+(a~b回)=((a+1)+a~(a+1)+b回)=(2a+1~a+b+1回)
 (a+2回)+(a~b回)=((a+2)+a~(a+2)+b回)=(2a+2~a+b+2回)
  ・・・
 (b-2回)+(a~b回)=((b-2)+a~(b-2)+b回)=(a+b-2~2b-2回)
 (b-1回)+(a~b回)=((b-1)+a~(b-1)+b回)=(a+b-1~2b-1回)
 (b-0回)+(a~b回)=((b-0)+a~(b-0)+b回)=(a+b~2b回)

1つめの式により、2a回からa+b回の任意の繰り返し回数が生成できることが判る。また、それ以降の式の最大繰り返し回数が、a+bから2bまで1つずつ順番に増加して行くことから、結果として、2a回~2b回の任意の繰り返し回数を取ることができることが判る。すなわち、(a~b回)+(a~b回)=(2a~2b回)は成立する。

次に、x=3の場合、すなわち{a,b}{3,3}の場合について考えてみる。

x=3つまり外側の繰り返し回数が3回なので、内側の(a~b回)を3回繰り返す、すなわち、

 (a~b回)+(a~b回)+(a~b回)=(3a~3b回)

が成立することを考える。

ここで、(a~b回)+(a~b回)=(2a~2b回)が成立することを利用して、上記の式を下記のように変形する。

 (a~b回)+(2a~2b回)=(3a~3b回)

ここでx=2の場合と同じように、1回目の内側の繰り返し回数が、a回からb回に変化するのを順番に追っていってみる。

 (a+0回)+(2a~2b回)=((a+0)+2a~(a+0)+2b回)=(3a~a+2b回)
 (a+1回)+(2a~2b回)=((a+1)+2a~(a+1)+2b回)=(3a+1~a+2b+1回)
 (a+2回)+(2a~2b回)=((a+2)+2a~(a+2)+2b回)=(3a+2~a+2b+2回)
  ・・・
 (b-2回)+(2a~2b回)=((b-2)+2a~(b-2)+2b回)=(2a+b-2~3b-2回)
 (b-1回)+(2a~2b回)=((b-1)+2a~(b-1)+2b回)=(2a+b-1~3b-1回)
 (b-0回)+(2a~2b回)=((b-0)+2a~(b-0)+2b回)=(2a+b~3b回)

x=2の場合と同様である。1つめの式により、3a回からa+2b回の任意の繰り返し回数が生成でき、また、それ以降の式の最大繰り返し回数が、a+2bから3bまで1つずつ順番に増加して行くことから、結果として、3a回~3b回の任意の繰り返し回数を取ることができることが判る。すなわち、(a~b回)+(a~b回)+(a~b回)=(3a~3b回)は成立する。

一般化してn回の場合も同様に、

 (a~b回)1+・・・+(a~b回)(n-1)=((n-1)a~(n-1)b回)

が成立することから、

 (a~b回)1+・・・+(a~b回)n=(na~nb回)

は、

 (a~b回)+((n-1)a~(n-1)b回)=(na~nb回)

となり、今までと同じように、

 (a+0回)+((n-1)a~(n-1)b回)=((a+0)+(n-1)a~(a+0)+(n-1)b回)=(na~a+(n-1)b回)
 (a+1回)+((n-1)a~(n-1)b回)=((a+1)+(n-1)a~(a+1)+(n-1)b回)=(na+1~a+(n-1)b+1回)
 (a+2回)+((n-1)a~(n-1)b回)=((a+2)+(n-1)a~(a+2)+(n-1)b回)=(na+2~a+(n-1)b+2回)
  ・・・
 (b-2回)+((n-1)a~(n-1)b回)=((b-2)+(n-1)a~(b-2)+(n-1)b回)=((n-1)a+b-2~nb-2回)
 (b-1回)+((n-1)a~(n-1)b回)=((b-1)+(n-1)a~(b-1)+(n-1)b回)=((n-1)a+b-1~nb-1回)
 (b-0回)+((n-1)a~(n-1)b回)=((b-0)+(n-1)a~(b-0)+(n-1)b回)=((n-1)a+b~nb回)

となり、(a~b回)1+・・・+(a~b回)n=(na~nb回)が成立する。

以上のことから、「α{a,b}{x,x}」は、常に「α{a*x,b*x}」に変換できると言うことができる。

次に、外側の繰り返し回数に幅がある場合、すなわち「α{a,b}{c,d}」の場合に、ac~bd回の任意の繰り返し回数を生成できるか否かについて考えてみる。

ここで、以下のような複数の変換について考えてみる。

 「α{a,b}{c+0,c+0}」を「α{a(c+0),b(c+0)}」にする
 「α{a,b}{c+1,c+1}」を「α{a(c+1),b(c+1)}」にする
 「α{a,b}{c+2,c+2}」を「α{a(c+2),b(c+2)}」にする
  ・・・
 「α{a,b}{d-1,d-1}」を「α{a(d-1),b(d-1)}」にする
 「α{a,b}{d-0,d-1}」を「α{a(d-0),b(d-0)}」にする

つまり、外側の繰り返し回数を固定にして、一つずつ増やしていった場合について、それぞれの変換について考えてみる。上記の変換は、外側の繰り返し回数が同じであるため、今までの証明から全て成立するということができる。

ここで、変換後の「α{ac,bc}」「α{a(c+1),b(c+1)}」・・・「α{ad,bd}」の繰り返し回数の範囲が互いに重複しているのであれば、「α{a,b}{c,d}」の繰り返し回数が、ac~bd回の全ての繰り返し回数の値を取ることができると言うことができるはずである。

数直線で書くと、こんな感じになるだろうか。



式で書くと、b(c+0)+1>=a(c+1) かつ b(c+1)+1>=a(c+2) かつ ・・・ かつ b(d-1)+1>=a(d-0) という条件式になる。表現を変えれば、下記のようになる。



上記の式は、下記のように書き換えられる。



ここで、iは必ず正の値であり、かつ、単調増大であること、及び、aとbの値は変わらないことから、iがもっとも小さいとき、すなわちi=cの場合にi(b-a)>=a-1が成立すれば、iがcからdまで変化する場合の、全ての場合について成立すると言うことができる。

以上のことから、c(b-a)>=a-1が成立する、あるいは、c=dが成立するならば、「α{a,b}{c,d}」=「α{a*c,b*d}」が成立すると言うことができる。


と、こんなもんでどうだろうか? あっているだろうか?

0 件のコメント: