正規表現– tag –
-
コンピュータ科学 深掘り
文字列探索とKMP — grepは1文字ずつ見ていない
indexOf があるのに、なぜ探索アルゴリズムを知るのか。素朴な探索・KMP・Boyer-Moore・Rabin-Karp を全部自分で書いて、比較回数と時間を実測します。最悪ケースを自分で作って素朴な探索を19,990,100回まで膨らませ、KMPで33分の1にします。Boyer-Moore がパターンを長くするほど速くなることを、比較回数が半分ずつ減るところまで数えます。ハフマン符号は英文4MBの出現頻度から符号表を作り、gzip の実測圧縮率と並べます。最後に接尾辞配列で「何回引いたら作る価値があるか」の交差点を出します。 -
プログラム
正規表現が固まる理由 — エンジンを100行で自作する
正規表現は呪文ではありません。連結・選択・繰り返しの3つだけなら、パーサとオートマトンで100行そこそこで作れます。先に /(a+)+$/ が30文字の入力で14秒固まるところを実測して見せ、そのあと自作して「なぜ固まるのか」を内側から説明します。同じ入力を自作エンジンに食わせると0ミリ秒で返る理由と、それでも実務でバックトラック方式が使われる理由まで。
1