ももの知恵の樹

正規表現

正規表現 (Regular Expression)について

正規表現とは

正規表現とは、数学者であるスティーヴン・コール・クリーネ(Stephen Cole Kleene)によって考案された、文字列の集合を一つの文字列で表現する方法です。
コマンド（grep, sed awk, viなど）に正規表現を用いると、文字列の検索・置換・消去が容易となります。


正規表現における基本記法

  • 文字
    • 正規表現における「文字」とは、その文字自身を表す正規表現を意味します。
    • 例えば、「A」という文字が表記された場合、文字「A」が１つだけ出現することを表す正規表現であるとみなします。
  • 連結(concatenation)
    • 例えば「ABC」と表現は、文字「A」「B」「C」が順番に出現することを表す正規表現を意味します。
  • 選択(union)
    • 例えば「A|B|C」と表現は、文字「A」「B」「C」のいずれかが出現することを表す正規表現を意味します。
  • 閉包(closure：繰り返し)
    • 例えば「A*」と表現は、文字「A」が０回以上繰り返して出現することを表す正規表現を意味します。

メタ文字 (meta-character)

正規表現では、特別な意味を持つ文字を「メタ文字」と呼びます。

メタ文字を単なる文字として扱いたい場合は、それらメタ文字の前に「\（バックスラッシュ）」を付加します。

なお、メタ文字の意味はシステムや処理系によって若干異なるので、実行結果がおかしいときはコマンド仕様を確認する必要があります。

以下に挙げるのは利用頻度が高く、一般的に用いられるメタ文字です。 


*      直前の文字の0回以上に一致
+      直前の文字の1回以上に一致
.      1つの任意文字（A, B, Cなど、ただし\nを除く)
?      直前の文字の0回または1回に一致
{n}    直前の文字がちょうどn回に一致
{n,}   直前の文字がn回以上に一致
{n,m}  直前の文字がn回以上,m回以下に一致
[xyz]  x,y,zの何れか1文字に一致
[^A]   否定：A以外の文字
x|y    選択：xまたはyに一致
()     グループ化
\w     英数文字かアンダーバーを表す(a-z,A-Z,0?9,_)
\d     数値文字を表す(0-9)
^      行の最初
$      行の最後
\s     空白,タブ
\S     空白文字以外
\d     数値文字
\D     \d以外
\w     英数文字かアンダーバー
\W     \w以外の文字
\b     単語の境界

正規表現とオートマトン

正規表現におけるパターンマッチの基本的な動作原理は、有限オートマトンという仕組みを用いて実装されています。
現在のシステムで用いられる正規表現は、クリーネが考案した正規表現よりも遥かに複雑化していますが、動作原理の基本が有限オートマトンという点は変わりません。


有限オートマトン (Finite Automaton)とは

有限オートマトンとは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」です。
つまり、ある入力に対し、ある処理を自動的に実行し、ある出力を出すシステムのことです。


正規表現が特定の文字列にパターンマッチするかどうかは、有限オートマトンによって判定することができます。
正規表現を有限オートマトン、つまり状態遷移図（State Transition Diagram：オートマトンを図形的に表現したもの）に変換し、調べたい文字列を与えて内部の状態を遷移させていき、入力文字列が受理されるかを確認します。
遷移結果が受理状態に達すれば、その正規表現は入力として受け取った文字列にマッチしたと判断することができます。


有限オートマトンには以下の二種類があり、どちらで実装されているかによって正規表現の挙動が大きく異なってきます。
DFAは表を作るのに多少時間がかかるものの、NFAに比べてマッチしているかどうかを調べるスピードが非常に速いのが特徴です。

  • 非決定性オートマトン (NFA:Nondeterministic Finite Automaton)
    • 非決定性オートマトンとは、入力に対する状態遷移の行き先が一意的に決まらないような状態遷移の不定性を持ったオートマトンです。遷移先が複数あり得る状態遷移図で表されます。
  • 決定性有限オートマトン (DFA:Deterministic Finite Automaton)
    • 決定性有限オートマトンとは、ε遷移が無く、一つの状態から同じ記号で異なった複数の状態に遷移することがないオートマトンです。どの状態点（有向グラフのノード）においても、状態遷移が失敗するか、状態遷移先が1個だけに決まる状態遷移図で表されます。

正規表現サンプル


(sedコマンド)絶対パスからファイル名を排除。同一名ディレクトリを表示しない。


sed 's/\(.*\\\).*$/\1/' NV_header_list.txt | uniq > after.txt

(sedコマンド)行頭・行末の空白を削除する。

-eオプションを使うと複数条件指定できます。 


sed -e 's/^ *//' -e 's/ *$//'

(sedコマンド)改行コードCrLfをLfに変換する。


sed 's/\r\n/\n/g'

(viのsed機能) 空白のみの行に対して、行（改行）をのこしたまま空白のみ削除する


%s/^¥s¥+$//

(viのsed機能)行間の無駄な改行を消去


:%s/^\n//g
:g/^ *$/d

(viのsed機能)空行を追加する


:%s/\n/\n\n/g