正規表現を"微分"する!? 爆速で自作できる正規表現エンジン

正規表現を する!? 微分 爆速で自作できる正規表現エンジン iOSDC2023

自己紹介

自己紹介 岐阜県在住 フリーランスエンジニア 本日0x2F歳になりました エンジニアと人生コミュニティに生息 趣味で鉄を作っています @ta̲ka̲tsu

自己紹介

自己紹介

自己紹介

本トークでは ・形式言語理論における「純粋な」正規表現を取り扱います ・完全一致のみを取り扱います

昨年のトーク

用語

用語 アルファベット 「1文字」のこと アルファベット集合 Σ アルファベットの有限集合 Σ a b c …

用語 文字列(系列) アルファベットを0個以上 並べたもの 文字列集合 Σ * 文字列全てからなる集合 Σ* ε a b c … aa ab ac ba bb bc … aaa aab aac aba ⋯ aaaa aaab aaac ⋯ ⋯

用語 文字列(系列) アルファベットを0個以上 並べたもの 文字列集合 Σ * 文字列全てからなる集合 ※ ε は空文字列を表す Σ* ε a b c … aa ab ac ba bb bc … aaa aab aac aba ⋯ aaaa aaab aaac ⋯ ⋯

用語 言語 L 文字列集合の一部 (部分集合) ⋯ Σ* L ⋯ ※空集合も言語

用語 Σ* 正規表現 言語を決定する表現の１つ 正規表現 r で定まる言語を L(r) と書くことにする r = a(a | b) * L(r) a aa ab aaa aab aba abb ⋯

用語 Σ* 注意 正規表現で表せない 言語もある!! ? L ε ab aabb aaabbb aaaabbbb aaaaabbbbb aaaaaabbbbbb ⋯

用語 文字列 w が正規表現 r に Σ* マッチする L(r) ⟺ 文字列 w が言語 L(r) に 含まれる (w ∈ L(r)) ⋯ w ⋯

正規表現の 構成要素

正規表現の構成要素 アルファベット１文字は正規表現 Σ* L(a) L(a) = {a} a ⋯

正規表現の構成要素 ε は正規表現 Σ* L(ε) L(ε) = {ε} ε ⋯

正規表現の構成要素 ∅ は正規表現 Σ* L(∅) L(∅) = {} ⋯

正規表現の構成要素 選択 r1, r2 が正規表現ならば r1 | r2 も正規表現 L(r1 | r2) = L(r1) ∪ L(r2) Σ* L(r1) L(r2) L(r1 | r2) ⋯

正規表現の構成要素 連接 r1, r2 が正規表現ならば r1 ⋅ r2 も正規表現 L(r1 ⋅ r2) = {w1 ⋅ w2 | w1 ∈ L(r1), w2 ∈ L(r2)} 例：L(r1) = {aa, bb}, L(r2) = {ab, ba}のとき L(r1 ⋅ r2) = {aaab, aaba, bbab, bbba}

正規表現の構成要素 繰り返し(クリーネ閉包) r が正規表現ならば r * も正規表現 r * = ε|r|r ⋅ r|r ⋅ r ⋅ r|⋯ 例：L(r) = {ab, ba} のとき L(r*) = {ε, ab, ba, abab, abba, baab, baba, ababab, ⋯}

正規表現の構成要素 ※演算子の優先順位は * 、⋅ 、| の順に高いものとする また、連接の記号 ⋅ は省略されることが多い 例： a | bc * は a | (b ⋅ (c*)) を意味する

正規表現の構成要素 重要な性質 r|r = r ε⋅r=r⋅ε=r ∅⋅r=r⋅∅=∅ ∅|r = r|∅ = r r1(r2 | r3) = r1r2 | r1r3

本日の アルゴリズム

本日のアルゴリズム 正規表現 r に cat がマッチするか？

本日のアルゴリズム 正規表現 言語 r L(r) bear cat catch dog ⋯ に cat がマッチするか？

本日のアルゴリズム 正規表現 言語 r L(r) bear cat catch dog ⋯ が cat にマッチするか？ 対応する言語から探せば良いのでは？

本日のアルゴリズム 正規表現 言語 r L(r) bear cat catch dog ⋯ が cat にマッチするか？ 対応する言語から探せば良いのでは？ →問題点 ・言語の要素を列挙するのが難しい ・言語が無限集合の可能性がある

本日のアルゴリズム 正規表現 r c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯

本日のアルゴリズム 正規表現 r a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t tch ⋯

本日のアルゴリズム 正規表現 r a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r は cat にマッチするといえる！！ a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r c を削る 言語 a を削る t を削る L(r) bear cat実際に行うことは困難！ at t catch atch tch dog ⋯ ⋯ ⋯ ε ch ⋯

本日のアルゴリズム 正規表現 r c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯

本日のアルゴリズム 正規表現 r r′ c を削る  言語 L(r) bear cat catch dog ⋯ at atch ⋯ 正規言語から アルファベットを 削った集合に 対応する正規表現は 必ず存在することが 知られている

本日のアルゴリズム 正規表現 r c で”微分” r′ c を削る  言語 L(r) bear cat catch dog ⋯ at atch ⋯ これを 「正規表現を アルファベットで “微分”する」 と呼ぶことにする

本日のアルゴリズム 正規表現 r c で”微分” Dc(r) c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ 正規表現 r を アルファベット a で 微分した正規表現を Da(r)と表す

本日のアルゴリズム 正規表現 r c で”微分” a で”微分” t で”微分” Dc(r) Da(Dc(r)) Dt(Da(Dc(r))) a を削る c を削る 言語 L(r) bear cat catch dog ⋯ at atch ⋯ t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム 最後の正規表現に空文字がマッチするか？ 正規表現 r Dc(r) a を削る c を削る 言語 L(r) bear cat catch dog ⋯ Da(Dc(r)) at atch ⋯ Dt(Da(Dc(r))) t を削る t tch ⋯ ε ch ⋯

本日のアルゴリズム マッチの判定 文字列 a1a2⋯an が正規表現 r にマッチする ⟺ 空文字が正規表現 Dan(⋯Da2(Da1(r))⋯) にマッチする つまり ・正規表現をアルファベットで”微分”する ・空文字が正規表現にマッチするかを判定する が実装できれば良い

“微分”の方法

“微分”の方法 アルファベットの”微分” 正規表現 a L(a) 言語 a

“微分”の方法 アルファベットの”微分” 正規表現 a L(a) 言語 a a を削る ε

“微分”の方法 アルファベットの”微分” 正規表現 a L(a) 言語 a a で”微分” ε a を削る ε

“微分”の方法 アルファベットの”微分” 正規表現 b L(b) 言語 b

“微分”の方法 アルファベットの”微分” 正規表現 b L(b) 言語 b a を削る

“微分”の方法 アルファベットの”微分” 正規表現 b L(b) 言語 b a で”微分” a を削る ∅

“微分”の方法 ε の”微分” 正規表現 ε L(ε) 言語 ε

“微分”の方法 ε の”微分” 正規表現 ε L(ε) 言語 ε a を削る

“微分”の方法 ε の”微分” 正規表現 ε L(ε) 言語 ε a で”微分” a を削る ∅

“微分”の方法 ∅の”微分” 正規表現 ∅ L(∅) 言語

“微分”の方法 ∅の”微分” 正規表現 ∅ L(∅) 言語 a を削る

“微分”の方法 ∅の”微分” 正規表現 ∅ L(∅) 言語 a で”微分” a を削る ∅

“微分”の方法 選択の”微分” 正規表現 r1 | r2 L(r1) L(r2) 言語 L(r1 | r2)

“微分”の方法 選択の”微分” 正規表現 r1 | r2 L(r1) L(r2) 言語 ⋯ ⋯ ⋯ a を削る ⋯ L(r1) から a を削った言語

“微分”の方法 選択の”微分” 正規表現 r1 | r2 L(r1) L(r2) 言語 ⋯ ⋯ ⋯ a を削る ⋯ ⋯ ⋯ L(r2) から a を削った言語

“微分”の方法 選択の”微分” 正規表現 r1 | r2 L(r1) L(r2) 言語 L(r1 | r2) a を削る

“微分”の方法 選択の”微分” 正規表現 r1 | r2 L(r1) L(r2) 言語 L(r1 | r2) a で”微分” a を削る Da(r1) | Da(r2)

“微分”の方法 連接の”微分” 正規表現 r1r2

“微分”の方法 連接の”微分” 正規表現 r1r2 a で”微分” ? Da(r1)r2 先頭からアルファベットを削る操作なので これでよいのでは？

“微分”の方法 連接の”微分” 正規表現 r1r2 a で”微分” Da(r1)r2 先頭からアルファベットを削る操作なので これでよいのでは？ →見落としがある

“微分”の方法 連接の”微分” L(r1) ab ac L(r2) ac bc

“微分”の方法 連接の”微分” L(r1) ab ac L(r2) ac bc L(r1r2) abac abbc acac acbc

“微分”の方法 連接の”微分” L(r1) ab ac L(r2) ac bc L(r1r2) abac abbc acac acbc a を削る b c

“微分”の方法 連接の”微分” L(r1) ab ac L(r2) ac bc L(r1r2) abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接

“微分”の方法 連接の”微分” L(r1) ab ac a を削る L(r2) ac bc L(r1r2) abac abbc acac acbc a を削る b c bac bbc cac bac bbc cac cbc cbc L(r2) と連接

“微分”の方法 連接の”微分” L(r1) ab ac a を削る L(r2) ac bc L(r1r2) abac abbc acac acbc a を削る b c bac bbc cac bac bbc cac cbc cbc L(r2) と連接 同じ！

“微分”の方法 連接の”微分” L(r1) ε ab ac L(r2) ac bc

“微分”の方法 連接の”微分” L(r1) ε ab ac L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc

“微分”の方法 連接の”微分” L(r1) ε ab ac L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c

“微分”の方法 連接の”微分” L(r1) ε ab ac L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc 異なる！

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る b c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る a を削る b c c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc

“微分”の方法 連接の”微分” L(r1) ε ab ac a を削る L(r2) ac bc L(r1r2) ac bc abac abbc acac acbc a を削る a を削る b c c bac bbc cac cbc L(r2) と連接 c bac bbc cac cbc 合わせれば 同じ！

“微分”の方法 連接の”微分” r1r2 a で”微分” Da(r1)r2 Da(r1)r2 | Da(r2) ( r1に空文字がマッチしない時) ( r1に空文字がマッチする時)

“微分”の方法 連接の”微分” r1r2 a で”微分” Da(r1)r2 Da(r1)r2 | Da(r2) ∅ if ε ∉ L(r) δ(r) = {ε if ε ∈ L(r) ( r1が空文字にマッチしない時) ( r1が空文字にマッチする時) という補助関数を定義すると Da(r1r2) = Da(r1)r2 | δ(r1)Da(r2) と書ける

“微分”の方法 繰り返しの”微分” Da(r*)

“微分”の方法 繰り返しの”微分” Da(r*) = Da(ε | r | rr | rrr | ⋯)

“微分”の方法 繰り返しの”微分” Da(r*) = Da(ε | r | rr | rrr | ⋯) = Da(ε) | Da(rr) | Da(rrr) | ⋯

“微分”の方法 繰り返しの”微分” Da(r*) = Da(ε | r | rr | rrr | ⋯) = Da(ε) | Da(rr) | Da(rrr) | ⋯ = ∅ | Da(r) | (Da(r)r | δ(r)Da(r)) | (Da(r)rr | δ(r)Da(rr)) | ⋯

“微分”の方法 繰り返しの”微分” Da(r*) = Da(ε | r | rr | rrr | ⋯) = Da(ε) | Da(rr) | Da(rrr) | ⋯ = ∅ | Da(r) | (Da(r)r | δ(r)Da(r)) | (Da(r)rr | δ(r)Da(rr)) | ⋯ = Da(r) | Da(r)r | Da(r)rr | ⋯ = Da(r)(ε | r | rr | ⋯) = Da(r)r *

“微分”の方法 正規表現の”微分”のまとめ Da(a) = ε Da(b) = ∅ Da(ε) = ∅ Da(∅) = ∅ Da(r1 | r2) = Da(r1) | Da(r2) Da(r1r2) = Da(r1)r2 | δ(r1)Da(r2) Da(r*) = Da(r)r *

実装

実装 public enum MyRegex { case char(Character) // アルファベット case epsilon // ε case empty // ∅ indirect case concat(MyRegex,MyRegex) // 連接 indirect case or(MyRegex,MyRegex) // 選択 indirect case star(MyRegex) // 繰り返し }

実装
extension MyRegex {
func matchToEmptyString() -> Bool {
switch self {
case .char(_):
return false
case .epsilon:
return true
case .empty:
return false
case .concat(let r1, let r2):
return r1.matchToEmptyString() && r2.matchToEmptyString()
case .or(let r1, let r2):
return r1.matchToEmptyString() || r2.matchToEmptyString()
case .star(_):
return true
}
}
}

実装 func delta(_ r:MyRegex) -> MyRegex { return r.matchToEmptyString() ? .epsilon : .empty }

実装
extension MyRegex {
func derivative(with char:Character) -> MyRegex {
switch self {
case .char(let c):
return (char == c) ? .epsilon : .empty
case .epsilon:
return .empty
case .empty:
return .empty
case .concat(let r1, let r2):
return .or(.concat(r1.derivative(with: char), r2),
.concat(delta(r1), r2.derivative(with: char)))
case .or(let r1, let r2):
return .or( r1.derivative(with: char), r2.derivative(with: char))
case .star(let r):
return .concat(r.derivative(with: char), .star(r))
}
}
}

実装 extension MyRegex { public func wholeMatch(to str: String) -> Bool { return str.reduce( self ) { $0.derivative(with: $1) }.matchToEmptyString() } }

実装 extension MyRegex { public func wholeMatch(to str: String) -> Bool { return str.reduce( self ) { $0.derivative(with: $1) }.matchToEmptyString() } } 完成

実装 extension MyRegex { public func wholeMatch(to str: String) -> Bool { return str.reduce( self ) { $0.derivative(with: $1) }.matchToEmptyString() } } 完成？

実装 let jojo : MyRegex = .star(.concat(.char("オ"), .char("ラ"))) // (オラ)* if jojo.wholeMatch(to: "オラオラオラオラオラオラオラオラ") { print("jojo") } else { print("not jojo") }

実装

実装 初期状態 repeat concat char("オ") char("ラ")

実装 “オ”で微分 concat or concat ε char("ラ") concat ∅ ∅ repeat concat char("オ") char("ラ")

実装 さらに“ラ”で微分 or concat or or concat ∅ char("ラ") concat ε ε or concat ∅ ∅ concat ∅ ∅ repeat concat char("オ") char("ラ") concat ∅ concat or concat ∅ char("ラ") concat ∅ ε repeat concat char("オ") char("ラ")

実装 さらに“オ”で微分 or or concat or or or concat ∅ char("ラ") concat ∅ ∅ or concat ∅ ε concat ε ∅ or or concat ∅ ∅ concat ∅ ∅ or concat ∅ ∅ concat ∅ ∅ repeat concat char("オ") char("ラ") concat ε

実装
extension MyRegex {
func derivative(with char:Character) -> MyRegex {
switch self {
case .char(let c):
return (char == c) ? .epsilon : .empty
case .epsilon:
return .empty
case .empty:
return .empty
case .concat(let r1, let r2):
return .or(.concat(r1.derivative(with: char), r2),
.concat(delta(r1), r2.derivative(with: char)))
case .or(let r1, let r2):
return .or( r1.derivative(with: char), r2.derivative(with: char))
case .star(let r):
return .concat(r.derivative(with: char), .star(r))
}
}
}

実装 “オ”で微分した結果 concat or concat ε char("ラ") concat ∅ ∅ repeat concat char("オ") char("ラ") こうなっている Dオ((オラ) * ) = (εラ | ∅∅)(オラ) *

実装 “オ”で微分 こうしたい concat char("ラ") repeat concat char("オ") char("ラ") Dオ((オラ) * ) = (εラ | ∅∅)(オラ) * = ラ(オラ) *

実装
// concatinate
func s_concat(_ lhs:MyRegex, _ rhs:MyRegex) -> MyRegex {
if case .epsilon = lhs {
return rhs // εr = r
}
if case .empty = lhs {
return .empty // ∅r = ∅
}
if case .epsilon = rhs {
return lhs // rε = r
}
if case .empty = rhs {
return .empty // r∅ = ∅
}
return .concat(lhs, rhs)
}

実装
// or
extension MyRegex : Equatable {
}
func s_or(_ lhs:MyRegex, _ rhs:MyRegex) -> MyRegex {
if lhs == rhs {
return lhs // r|r = r
}
if case .empty = lhs {
return rhs // ∅|r = r
}
if case .empty = rhs {
return lhs // r|∅ = r
}
return .or(lhs, rhs)
}

実装
extension MyRegex {
func derivative(with char:Character) -> MyRegex {
switch self {
case .char(let c):
return (char == c) ? .epsilon : .empty
case .epsilon:
return .empty
case .empty:
return .empty
case .concat(let r1, let r2):
return s_or(s_concat(r1.derivative(with: char), r2),
s_concat(delta(r1), r2.derivative(with: char)))
case .or(let r1, let r2):
return s_or(r1.derivative(with: char), r2.derivative(with: char))
case .star(let r):
return s_concat(r.derivative(with: char), .star(r))
}
}
}

実装 正規表現が作りづらい… let let let let let let ios : MyRegex = .concat(.char("i"), .concat(.char("O"), .char("S"))) // "iOS" ww : MyRegex = .concat(.char("W"), .char("W")) // "WW" dc : MyRegex = .concat(.char("D"), .char("C")) // "DC" two_or_three : MyRegex = .or(.char("2"), .char("3")) // "2|3" twice_two_or_three : MyRegex = .concat(two_or_three, two_or_three) // “(2|3){2}” option_twice_two_or_three : MyRegex = .or(.epsilon, twice_two_or_three)// “((2|3){2})?” // "(iOS|WW)DC((2|3){2}*)?" let testRegex1 : MyRegex = .concat(.or(ios, ww), .concat(dc, option_twice_two_or_three)) let result1 = testRegex1.wholeMatch(to: "iOSDC") print(result1) // true let result2 = testRegex1.wholeMatch(to: "WWDC22") print(result2) // true let result3 = testRegex1.wholeMatch(to: "iOSDC23") print(result3) // true

実装 MyRegexBuilderも作った let testRegex = MyRegex { ChoiceOf { "iOS" "WW" } "DC" Optionally { Repeat(count: 2) { ChoiceOf { "2" "3" } } } } let result1 = testRegex1.wholeMatch(to: "iOSDC") print(result1) // true let result2 = testRegex1.wholeMatch(to: "WWDC22") print(result2) // true let result3 = testRegex1.wholeMatch(to: "iOSDC23") print(result3) // true

MyRegex https://github.com/ta-ka-tsu/MyRegex

• https://github.com/ta-ka-tsu/MyRegex

DFAやVMによる 実装の概要との比較

DFAやVMによる実装の概要との比較 DFA型 正規表現 DFA a 変換 (a | b) * bb(ab) * q1 b b a q2 b a q3 ※アルファベット集合が {a, b}の場合

DFAやVMによる実装の概要との比較 VM型 正規表現 命令列(バイトコード) 変換 (a | b) * bb(ab) * 0: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: split 1 6 split 2 4 char a jump 5 char b jump 0 char b char b split 9 12 char a char b jump 8 match

DFAやVMによる実装の概要との比較 比較 正規表現エンジン 変換 実行時速度 DFA型 DFAに変換が必要 高速 VM型 VMに変換が必要 高速 “微分”型 不要 低速

なぜ“微分”と呼ぶ?

関数 function f(x)

f(x) 関数 function ff  微分する di erentiate f(x + h) − f(x) f′(x) = lim h→0 h

f(x) 関数 function 微分する di erentiate ff  導関数 derivative f(x + h) − f(x) f′(x) = lim h→0 h

f(x) 関数 function 微分する di erentiate ff  導関数 derivative f(x + h) − f(x) f′(x) = lim h→0 h

https://dl.acm.org/doi/pdf/10.1145/321239.321249

• https://dl.acm.org/doi/pdf/10.1145/321239.321249

https://dl.acm.org/doi/pdf/10.1145/321239.321249

• https://dl.acm.org/doi/pdf/10.1145/321239.321249

本トークでは 「正規表現のDerivativeを求めること」 を 「正規表現を”微分”する」 と表現しました ※注：適切な訳ではない可能性があります

参考文献 ・JANUSZ A. BRZOZOWSKI Derivatives of Regular Expressions https://dl.acm.org/doi/pdf/10.1145/321239.321249 ・新屋良磨、鈴木勇介、高田謙 正規表現技術入門 (2015) 最新エンジン実装と理論的背景 技術評論社 ・Mark C. Chu-Carroll(訳:cocoatomo) グッド・マス オーム社 (2016) ギークのための数・論理・計算機科学

• https://dl.acm.org/doi/pdf/10.1145/321239.321249