[ruby-list:10658] Re: base64.rb

前田@リコーです。

前田> 強いて言えば「くり返し優先」「スキップ優先」ですかね。

これだけだといじわるみたいなので、例で説明しましょう。

abc.+def、abc.+?defという表現に対してabc12de34def56defという文字
列を与えた場合を考えます。たくさんあるマッチの可能性全部を一度に
調べることはできないので、未探索の可能性をスタックにためながら、
バックトラックによって調べていきます。最初に一致が見つかったとこ
ろで、答として返します。このときスタックに入ってるものは捨てられ
ます。

---

★abc.+defの場合

一致済				試行	失敗したら		結果
				a ? a	開始位置を進める	ok
a	 a			b ? b	開始位置を進める	ok
ab	 ab			c ? c	開始位置を進める	ok
abc	 abc			. ? 1	開始位置を進める	ok
abc.	 abc1			. ? 2	1: dから試す		ok
abc.+	 abc12			. ? d	2: dから試す		ok
abc.+	 abc12d			. ? e	3: dから試す		ok
	   中略	    
abc.+	 abc12de34def56		. ? d	11: dから試す		ok
	   中略
abc.+	 abc12de34def56de	. ? f	13: dから試す		ok
abc.+	 abc12de34def56def	. ? 終	14: dから試す		ng -> 14へBT
abc.+	 abc12de34def56def	d ? 終	バックトラック		ng -> 13へBT
abc.+	 abc12de34def56de	d ? f	バックトラック		ng -> 12へBT
abc.+	 abc12de34def56d	d ? e	バックトラック		ng -> 11へBT
abc.+	 abc12de34def56		d ? d	バックトラック		ok
abc.+d	 abc12de34def56d	e ? e	バックトラック		ok
abc.+de	 abc12de34def56de	f ? f	バックトラック		ok
abc.+def abc12de34def56def	終 ? 終	バックトラック		ok -> 終了

★abc.+?defの場合

一致済			試行	失敗したら		結果
			a ? a	開始位置を進める	ok
a	 a		b ? b	開始位置を進める	ok
ab	 ab		c ? c	開始位置を進める	ok
abc	 abc		. ? 1	開始位置を進める	ok
abc.	 abc1		d ? 2	1: .のくり返しを試す	ng -> 1へBT
abc.+	 abc1		. ? 2	開始位置を進める	ok
abc.+	 abc12		d ? d	1: .のくり返しを試す	ok
abc.+d	 abc12d		e ? e	バックトラック		ok
abc.+de	 abc12de	f ? 3	バックトラック		ng -> 1へBT
abc.+	 abc12		. ? d	開始位置を進める	ok
abc.+	 abc12d		d ? e	1: .のくり返しを試す	ng -> 1へBT
abc.+	 abc12d		. ? e	開始位置を進める	ok
	 中略
abc.+	 abc12de34	d ? d	開始位置を進める	ok
abc.+d	 abc12de34d	e ? e	開始位置を進める	ok
abc.+de	 abc12de34de	f ? f	開始位置を進める	ok
abc.+def abc12de34def	終 ? 終	開始位置を進める	ok -> 終了

結果として、
	abc.+def	abc12de34def56def
	abc.+?def	abc12de34def
が得られますが、長さに関する計算は一度も行っていないことがわかり
ます。

ここで、頭のいい人は「そうか、長さが最長、ではなくてくり返し回数
が最大なんだな」とか思うかもしれませんが、実はそれも正確ではあり
ません。「ある順番で試し、最初に見つかったもの」という大原則があっ
て、+に対する?ではその「順番」をコントロールしているにすぎません。

-------------------------------  Vulture       LRM20   .□||□.   LRM20
 前田 薫 [e-mail]   75t 175km/h     Md+  o'□||□`o  Md+
 (株)リコー ソフトウェア研究所   HeatSink 18  LG Sm+   .=X~~X=.   Sm+ LG
-------------------------------  Armor 2195           _|_    _|_