C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

■99841 / 12階層)  正規表現で文字列の否定
□投稿者/ 匿名希望マン (10回)-(2022/06/12(Sun) 23:04:41)
自分で正規表現エンジン(という程たいそうなものではないですが)を作りつつ、
この問題を考えてみていました。

当初の興味は
 https://bynatures.hatenadiary.jp/entry/3317/ の方法でNGワードを長くしていくと、
 正規表現はどのくらい複雑になるのか?
でした。

しかし、http://www.formauri.es/personal/pgimeno/misc/non-match-regex/ を
教えてもらい、そのうち、ジェネレーターを作ることが目的になってしまいました!
楽しそうだったので。

さて、以下の二つのアプローチで正規表現を生成していました。
 @ジェネレーターのサイトの出力を解析して、正規表現を出力するメソッドを作る
 ANGワードを与えてDFAを作り、そのDFAを正規表現に変換する

@に関しては No99776 で報告しています。
Aに関してはソースコードは割愛しますが、No99777 の資料に沿って実装してみました。
No99776 と同様、正規表現を示すと以下のようになりました(先頭の5個のみ)。
 Regex01: ^[^0]*$
 Regex02: ^[^0]*0([^01][^0]*0|0)*([^01][^0]*)?|[^0]*$
 Regex03: ^[^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|([^0]*0([^01][^0]*0|0)*([^01][^0]*)?|[^0]*)$
 Regex04: ^[^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2)*(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|(([^03][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^03][^0]*)?))|([^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|([^0]*0([^01][^0]*0|0)*([^01][^0]*)?|[^0]*))$
 Regex05: ^[^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2)*3(([^04][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2)*3)*(([^04][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2)*(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|(([^03][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^03][^0]*)?))|(([^04][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|(([^04][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^04][^0]*)?)))|([^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*2)*(([^03][^0]*0|0)([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|(([^03][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^03][^0]*)?))|([^0]*0([^01][^0]*0|0)*1(([^02][^0]*0|0)([^01][^0]*0|0)*1)*(([^02][^0]*0|0)([^01][^0]*0|0)*([^01][^0]*)?|([^02][^0]*)?)|([^0]*0([^01][^0]*0|0)*([^01][^0]*)?|[^0]*)))$
この調子でRegex16を書くと、UTF-8で8MBを超えるテキストになります!
No99777 の資料のアルゴリズムを使うなら、できるだけ短い正規表現を作るように工夫しないとダメですね。
それか、改めて正規表現を短くするアルゴリズム(そんなのあるのか知らんけど)噛ますか。

【まとめ】
NGワードを長くすると、正規表現は長くなる!

最後に所感。
 ・同じDFAでも、それと等価な正規表現はたくさんあるのかー!へぇー!
 ・No99777 の資料のアルゴリズムで、できるだけ短い正規表現を得るにはどうしたらいいのかな?
 ・DFAに最簡DFAがあるように、正規表現にも最も簡潔な正規表現が定義できて、それを得るアルゴリズムあるのかな?
 ・文字列の否定は正規表現で書けたけど、正規表現の否定って正規表現で書けるのかな?

解決済み
編集キー/

前の記事(元になった記事) 次の記事(この記事の返信)
←Re[11]: 正規表現で文字列の否定 /匿名希望マン 返信無し
 
上記関連ツリー

正規表現で文字列の否定 / 匿名希望マン (22/04/14(Thu) 20:20) #99465
Re[1]: 正規表現で文字列の否定 / 774RR (22/04/15(Fri) 09:43) #99470
Re[1]: 正規表現で文字列の否定 / furu (22/04/15(Fri) 10:48) #99473
  └ Re[2]: 正規表現で文字列の否定 / 匿名希望マン (22/04/15(Fri) 14:01) #99475
    └ Re[3]: 正規表現で文字列の否定 / shu (22/04/15(Fri) 14:55) #99477
      └ Re[4]: 正規表現で文字列の否定 / 匿名希望マン (22/04/15(Fri) 20:27) #99479
        ├ Re[5]: 正規表現で文字列の否定 / 匿名希望マン (22/04/16(Sat) 18:01) #99488
        │└ Re[6]: 正規表現で文字列の否定 / 伝説のカレー (22/04/16(Sat) 18:12) #99489
        │  └ Re[7]: 正規表現で文字列の否定 / 匿名希望マン (22/04/16(Sat) 20:35) #99491
        └ Re[5]: 正規表現で文字列の否定 / 伝説のカレー (22/04/16(Sat) 17:10) #99487
          └ Re[6]: 正規表現で文字列の否定 / 匿名希望マン (22/04/17(Sun) 12:17) #99493 解決済み
            └ Re[7]: 正規表現で文字列の否定 / shu (22/04/18(Mon) 17:29) #99499
              └ Re[8]: 正規表現で文字列の否定 / 匿名希望マン (22/04/19(Tue) 22:08) #99502
                └ Re[9]: 正規表現で文字列の否定 / shu (22/04/22(Fri) 01:19) #99529
                  └ Re[10]: 正規表現で文字列の否定 / 匿名希望マン (22/05/29(Sun) 14:48) #99776 解決済み
                    └ Re[11]: 正規表現で文字列の否定 / 匿名希望マン (22/05/29(Sun) 14:56) #99777 解決済み
                      └ 正規表現で文字列の否定 / 匿名希望マン (22/06/12(Sun) 23:04) #99841 解決済み ←Now

上記ツリーを一括表示 / 上記ツリーをトピック表示
 
上記の記事へ返信