“なんとなく使ってる……”から一歩踏み込む!『正規表現』社内勉強会レポート

こんにちは、広報部の笠川です。

この記事作成時点でSekappyは2018年の年末。ちょうど『アルティメットマスターズ』が発売された直後で、社内ではBOX開封の戦果報告で盛り上がりました。お仕事の方も佳境を迎えているチームもあり、年末のラストスパートといった雰囲気でした。

さて、本日はそんな中で行われた2018年最後の社内勉強会のレポートをお送りします。今回の発表者は開発部チーフの押味さん。前職では自社のITを全部担っていたなんでも屋系のエンジニアで、Sekappyでもチームを束ねるチーフとして信頼を集めています。MTGではSekappy随一の電波デッキビルダーで、新セット発売後は先陣を切って名作や迷作を発表してくれています。

今回は普段から使う場面はあるけれど突っ込んだ部分まではなかなか触れる機会がない『正規表現』がテーマ。社内Slackに「全然わからない、俺たちは雰囲気で正規表現を使っている…」というコメントが上がってきたところを見るに、なかなかかゆい部分の題材のようです。

正規表現を完全に理解したいメンバーが集まり、勉強会がスタート。まずは正規表現の普段の用途からおさらいします。電話番号やパスワードのバリデーションチェックや文字情報の検索などの文字列処理はもちろん、コーディングやドキュメントの編集にも便利です。

一般的なエディタであれば機能として備えており、例えばvimなら検索や置換をしたいときはこの通り。

/¥(Creature¥|Plainswalker¥)
%s/¥(Interrupt¥|Mana source¥)/Instant/g

続きまして、「そもそも正規表現ってどんなもの?」という説明に入っていきます。スライドには『正規表現、完全に理解する』とタイトルがついており、これは頼もしい。笑 押味さん曰く、C++を完全に理解しようとしたらリファレンスだけで1605ページありますが、正規表現はたった3行だけで定義できるとのこと。

アルファベット Σ = {𝑎1, … , 𝑎𝑘 } 上の正規表現とは、次の(1), (2)で定義されるものである。
(1) 𝑎1, … , 𝑎𝑘 , 𝜀, ∅ はいずれも正規表現である。
(2) 𝑟と𝑠が正規表現のとき、𝑟+𝑠, 𝑟∙𝑠, (𝑟∗)はいずれも正規表現である。

実際に使うだけならググれば大体の用は足りるとのことですが、こちらが理解できると内部でどのように動いているかがわかり、「正規表現って何だ?どうやって動いてんだ?」とモヤモヤしている人はスッキリに繋がるとのこと。また、自然言語処理/パーサー/コンパイラなど、任意の文字列処理や計算理論への入り口にもなります。

前述の定義を理解していくために、ここからはオートマトン言語理論という数学的なバックグラウンドに触れていきます。まずは日常使う言葉とは意味の違う用語の定義から。

【アルファベット】
・有限個の記号の集合 Σ
・例: {0,1}, {a,b,c,…,z}, 文字コード

【文(系列)】
・アルファベット Σ 上の文 𝑤(アルファベットから選ばれた記号を有限個並べたもの)
・個数が 0 のとき、空文 ε
・連接 𝑤1∙𝑤2
・例: Σ = {𝑎,𝑏,𝑐,…,𝑧,𝐴,𝐵,𝐶,…,𝑍} 
      𝑤 = 𝐽𝑎𝑐𝑒

【(形式)言語】
・アルファベット Σ 上の文の集合 L
・空集合の場合、空言語 ∅
・例: Σ = {𝑎,𝑏,𝑐,…,𝑧,𝐴,𝐵,𝐶,…,𝑍}
      𝐿 = {𝐴𝑟𝑡𝑖𝑓𝑎𝑐𝑡, 𝐶𝑟𝑒𝑎𝑡𝑢𝑟𝑒, 𝐿𝑎𝑛𝑑}

こちらを元に先ほどの正規表現の定義を見てみると、(1)一つ一つの記号や空の要素が正規表現で、(2)その掛け合わせで表現される言語も正規表現ですよ、というのがわかってきました。正規表現と言語との対応については下記のような対応になるとのことです。

・𝑎1 = {𝑎1}, 𝜀 = {𝜀}, ∅ = ∅ 
・𝑟+𝑠 = 𝑟∪𝑠 
・𝑟∙𝑠 = {𝑤∙𝑤′ | 𝑤∈𝑟, 𝑤’∈𝑠}
  ただし 𝑟 = ∅ または 𝑠 = ∅ のとき、𝑟∙𝑠 = ∅
・𝑟∗ = {𝜀} ∪ 𝑟 ∪ (𝑟∙𝑟) ∪ (𝑟∙𝑟∙𝑟) ∪ …

ここからは言語が定義される様子を確認するため、状態の様子を表す状態遷移図を見ていきます。

状態遷移図の読み取り方を教わったあとは、実際に手を動かして特定の文を受理する状態遷移図を描いてみます。

「この時はこうなって欲しいから…」「この場合はこうなるから…」と試行錯誤しながら状態遷移図を描いていきます。答えと照らし合わせながら、言語が定義される様子をイメージすることができました。

引き続き遷移の仕方が一意に決まらない非決定性有限オートマトンについても確認。こちらはたくさんのすごろくのコマを用意して動かすようにイメージすると理解しやすいとのことでした。

そして最後にこのパートのまとめ。これらの有限オートマトンが認識できる言語は正規言語と呼ばれ、正規表現の振る舞いと対応して文字を取り扱えるのだそうです。単に処理として使うにしても、どのような仕組みで動いているかがわかっているとスッキリ度合いも違ってきますね!

パートが変わって、ここからは正規表現の実用について見ていきます。実際に使う際は「チートシートを参照しながら使っているうちに覚えてしまいましょう!」とのことだったので、ここでは選言や量化、メタ文字などについてささっと確認。【参考】https://qiita.com/tossh/items/635aea9a529b9deb3038

そして最後には演習として、正規表現のテストサイトでMTGに役立つ(?)処理を実際に行っていきます。まずは、カード名に”《》”を付ける方法から!

【MO形式のデッキリストのカード名に《》をつけよ】
 Before : 60 Island
 After  : 60 《Island》

そして応用編では、《血染めの月》を置いたときに特殊地形を山にする方法まで!

【基本でない土地の土地タイプを山にせよ】
 基本土地 - 島
	→ そのまま
 基本氷雪土地 – 沼
	→ そのまま
 伝説の氷雪土地
	→ 伝説の氷雪土地 - 山
 土地 - 神座 
	→ 土地 - 山

正規表現を使うのは初めてという方から、普段からよく正規表現を使っている方まで、皆さん頭をひねりながら、トロンにカーンやウギンを出されないよう頑張ります!

最後に答え合わせをして、今回の勉強会は終了。「正規表現を便利に使って日頃の業務やマジックに活かしましょう!実は計算理論の入り口としても最適なので、そちらに興味がある方もぜひ!」と、押味さんから締めの言葉をいただきました。押味さん、参加者の皆さん、お疲れ様でした!

こちらで2018年の勉強会は締めになりました。日頃から新しい技術を身に付けたり、積極的にメンバーと知識をシェアしている開発部メンバーには、純粋に尊敬の念が止みません…。2019年も一緒に”MTG×IT”を盛り上げていきましょう!

それでは本日はこちらにて!