正規表現勉強内容まとめ1

正規表現

友達に正規表現について語られたので,今後正規表現が必要になった時のためのメモ。

参考資料

ネットサーフィンしながらみつけた良さそうな記事をメモ

正規表現の使い方解説
正規表現記号一覧
サンプル集
文字クラスについて

勉強法

正規表現については,応用情報技術者の試験勉強でごくごく基本的なことは覚えたので,どういうものかはわかっているつもりです。 ただしプログラミングをするときに正規表現を使ったことが無く,あまり使いこなせていない状態です。

この機能を実装するには正規表現が便利そうだなという状況はプログラミングをしていれば,すぐに出会うと思うのでその時はに上に示した参考資料を見ながら書いて覚えることにします。友達の話では正規表現は何よりも書いて覚えたほうが早いとのことです。

そのため今は正規表現について詳しくはやらず,友達が語ってくれた内容を↓にメモ。

友達が語ってくれた話

クラスの友達が語ってくれた内容を,忘れないようにメモ。思い出しながら書いているので少し表現がおかしいところがあるかもしれません。

1. 最適化

正規表現は自由度が高く,同じパターンを定義しようとしても人によって変わってきたりします。ですが,最適化というものが大事らしいのです。

例えば「gray」という単語と「grey」という単語を同じ正規表現で定義しようとすると

  1. gr[ae]y
  2. gr(a|e)y
  3. gray|grey

というように幾つかの定義方法があります。これらはどれも"gray"または"grey"の2つの単語にマッチングしますが,内部での比較回数が違います。友達には具体的にどのような順番で比較されていくかということも説明を受けたのですが,詳しいところは忘れました。 結論から言うと,上に示した3つの正規表現は番号順に処理時間が早いです。

それはなぜかというと正規表現のマッチングでは有限オートマトンという考え方が利用されているからとのこと。 こういったことは知らなくても正規表現を利用することが出来るのですが,大量のデータから正規表現にマッチングする単語を取り出そうとすると,正規表現の定義方法によって処理時間が大きく変わってくるとのことです。

2. 有限オートマトンについて

先程正規表現には有限オートマトンの考え方が利用されていると言いましたが,有限オートマトンには2種類有るそうです。

簡単にいうと,DFAは「状態と入力によって次に遷移すべき状態が一意に定まる」,NFAは「ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるもの」です。 また,なぜそうなるかの説明は僕にはよく分かりませんでしたが,DFAとNFAを比較すると↓のような特徴があります。

DFA NFA
安定性 ◯ ☓
高速性 ◯ ☓
柔軟さ ☓ ◯

DFAとNFAは一長一短でどちらが優れているとかいうものではありません。 向き不向きがありますが,多くのプログラミング言語では柔軟性に長けているNFAが利用されているとのことです。