正規表現を書く際、どのようなパターンにマッチさせるか、どこをキャプチャするかという視点で記述することはあっても、パフォーマンスを考えて記述するというのはある程度知っている人でなければ忘れがちな視点です。 このエントリでは、バックトラックをメインに正規表現がパフォーマンスに及ぼす挙動について見ていきます。 対象の正規表現エンジン ここでは、従来型 NFA を対象としています。具体的には、PHP の preg_ 関数で利用している PCRE や mb_ereg 関数が利用している鬼車です。Perl や Ruby、Python、Java、.NET でも従来型 NFA を採用しているので、似た挙動となるでしょう。 「従来型 NFA」や「バックトラック」などの用語については、「詳説 正規表現 第3版」のものを用いています。 バックトラックによるマッチ探査 正規表現エンジンでは、指定された文字列が、パ

こんにちは、Webアプリケーションエンジニアのid:nanto_viです。 Webアプリケーションを作っていると、「全角文字と半角文字を統一したい」「ユーザーの入力から漢字を抜き出したい」といったテキスト処理を行う場面にたびたび遭遇します。はてなではWebアプリケーションのサーバー側プログラミング言語としてPerlを多く使っていますが、PerlならこのようなときにUnicodeプロパティを用いた正規表現パターンで柔軟な処理が可能です。 Unicodeプロパティ 現在、ほとんどのプラットフォームで採用されている文字集合がUnicodeです。Unicodeでは文字だけでなくその文字の様々な特性(プロパティ)も定められており、テキスト処理の基礎情報として活用できます。 Perl正規表現でのUnicodeプロパティの利用 Perlの正規表現では、\p{Property_Name=Value}のよう

こんにちは、Webアプリケーションエンジニアのid:nanto_viです。みなさんHTMLのフォーム検証機能は使っていますか? 近年は各Webブラウザの対応も進み、お手軽にフォームの利便性を高められるようになっています。 そんなフォーム検証機能のひとつがinput要素のpattern属性です。pattern属性の値にJavaScriptの正規表現パターンを指定することで、ユーザーの入力が意図しないものであった場合、フォーム送信ができなくなります。下図は5桁の数字の入力が求められるところに3桁しか入力せずフォーム送信しようとしたところです。ブラウザに組み込みのエラー表示が出現し、またそのメッセージにtitle属性の値が使われていることを確認できるでしょう。(pattern属性を指定する際には、title属性に書式の説明を記述することが推奨されています。) <input type="text"

Atom は、今注目の最新テキストエディタです。私は、このエディタをソフトウェア開発に使用しているのですが、オープンソースになっているので、少しでも貢献できればとAtomが抱えるIssuesについて検証してみることにしました。私は、 ある奇妙なバグ を見つけました。それは、Atomのユーザ speter がテキストを1行書き、行末で Enter を押した時に起こりました。新たな行が書けるようになるまで、Atomは30分も計算していたのです。私は、そんな単純かつよくあるオペレーションもろくにできないことに大きな衝撃を受け、早速その原因を探ることにしました。 検索 これが、問題のテキストです。 vVar.Type().Name() == "" && vVar.Kind() == reflect.Ptr && vVar.Type().Elem().Name() == "" && vVar.Typ

わずかな文字がいかにしてパフォーマンスに大きな違いを生めるかというお話 正規表現は、私たち開発者がことあるごとに駆使する呪文のようなものですが、私たちはそれをどんな時も巧みに使いこなしていると言えるでしょうか。正規表現は繊細で精密な言語です。入念な慎重さで記述してやれば、ボウリングで一瞬にして完璧なストライクを取るような強力なテキストとなり得ます。 しかし、正規表現が精密さに欠ける状態で投げ出されると、さながら酔っ払いがよろよろとつまずきながらテキストの上を歩くがごとく、そのボールはぎこちなくボウリングのレーンを転がり、ピンを1つか2つ倒すだけで終わってしまうのです。 これら2つの正規表現の違いは何なのか。何がいい表現と悪い表現を分けるのか。正規表現に素晴らしい力を与えるメカニズムを、この投稿で明かしてみようと思います。効果的な表現とそうでない表現との大きな違いをきっと分かってもらえるはず

論理積（AND）の場合 ANDは、例えば'apple'と'orange'の両方が含まれているかどうか調べる場合は以下のようにすればいいらしいです。 なんで！？ (?=)は位置指定子というものの一つで、x(?=y)としたときは、'x'に'y'が続く場合のみ'x'にマッチします（肯定先読み）。 つまり、あくまでも位置を指定しているというわけです。 上の例の場合、まず先頭をスタート位置とし、^（先頭）→.*（何かしらの文字が0回以上）→appleと続いているかチェックします。さらにまた先頭から、^（先頭）→.*（何かしらの文字が0回以上）→orangeと続いているかチェックします。 順を追って見ていくと、

正規表現は様々なプログラミング言語やツールで利用できる、文字列の検索や置換に不可欠の存在といっても過言ではないかもしれません。 「Regulex」はその正規表現を可視化して分かりやすくグラフとして表示してくれるサービスです。 文字列で正規表現を入力すると対応したグラフが表示されるので、複雑な正規表現も直感的に理解できます(?)。 例1 例えば「(a|b\d+)*c」をビジュアライズすると以下のようなグラフが作られます。 グループがあってその中でaまたはbと数字の繰り返しがきて、最後にcがくる…というような正規表現が、グラフ化されました。 例2 もう少し簡単な例「abc\d+」を考えると次のようになります。 abcがきて、最後に数字の繰り返しが1回以上くる…。ということが直感的に理解できます。 まとめ 作成した正規表現グラフはイメージとして出力したり、サイトに埋め込んだりもできます(Java

正規表現難しい! 謎の記号が並んでるし, いざ書いてもうまく判定できてるかよくわからない. もうプログラムの勉強なんかしたくないし, 生きているのがツライよぉ. そんな人にもってこいなのが, 今回紹介する『VerbalExpressions』です!! プロジェクトスタート時から watch していて, アプローチとして面白いなと思ったので紹介します. VerbalExpressions って？ これはタイトルの通り複雑な正規表現を分かりやすくしてくれるライブラリです. コードは, 普通に正規表現書くよりも長くなっちゃいますが, 英文法に近いカタチで書くことができます. var tester = VerEx().startOfLine().then( "a" ).maybe( "b" ); var message = "abc"; console.log(tester.test(messag

文字列のパースをする必要がある時、どんな文字列にでも何でもかんでも正規表現で処理しようとするエンジニアをたまに見かける。 正規表現は確かに文字列を扱うための強力な手段だが、万能ではない。正規表現の性質上、そもそもパースできない文法があるからだ。従ってそういうケースの時には正規表現ではなく別の方法を使ったほうが良い。正規表現を無理やり使っても、バグを埋め込んだり、メンテナンスが難しかったり、正しく文字列をパース出来なかったりで良いことはあまりない。 正規表現がパースできない文字列 正規表現が苦手とする文法で一番よく言われるのは、再帰的な構文を含む文法である。例えば、括弧つきの数式なんかがそうで、1+1 でも (1+1) でも ( (1+1) ) でも ( ( (1+1) ) ) でも ( ( ( ( 1+1) ) ) ) でも、という風にいくらでも入れ子にできる。正規表現では、こういった文字

Perlの正規表現で条件分岐する方法を紹介します。 １．Perlの正規表現で条件分岐する たとえば文字列の先頭に「"」が存在する場合、文字列の末尾に「"」が必須であるパターンと、「"」がないパターン、 "foo" と foo の両方にマッチさせたい場合の正規表現は次のようになります。 ^(")?(?(1)\w+"|\w+)$ サンプルコード #!/usr/bin/perl use strict; use warnings; my $str = '"aaa"'; if ( $str =~ /^(")?(?(1)\w+"|\w+)$/ ) { print "match"; } else { print "not match"; } 解説です。まず、 ^(")? で、先頭にダブルクォーテーション「"」が1文字（または0文字）存在することを判定します。 次に、 (?(1) で、グループ（ここでは1

たまにメールアドレスの形式を正規表現で表すのは不可能とかというのを目にするのですが、そんなことはありません。入れ子がなければたいていの文字列の形式は正規表現で表すことができます。 ということで、RFC5321, 5322 からメールアドレスの正規表現を書いてみました。 /\A([0-9a-z!\#$%&'*+\-\/=?^_`{|}~]+(\.[0-9a-z!\#$%&'*+\-\/=?^_`{|}~]+)*|\"([\x20\x21\x23-\x5b\x5d-\x7e]|\\[\x20-\x7e])*\")@[0-9a-z]([0-9a-z-]*[0-9a-z])?(\.[0-9a-z]([0-9a-z-]*[0-9a-z])?)*\z/i ちょっと長いですけど、最近の Ruby だと (?<hoge>) と \g<hoge> を使うことで、同じ正規表現の繰り返しを簡単に書くことができる

JavaScript において、文字列を正規表現にマッチさせるためのメソッドは、以下の4つがあります。 1. RegExp.test() 2. RegExp.exec() 3. String.match() 4. String.search() RegExpオブジェクトのメソッド(引数がStringオブジェクト)と、Stringオブジェクトのメソッド(引数がRegExpオブジェクト)があり、しかもすべてのメソッドで微妙に動作が違うので、非常に紛らわしい… ということで、これらがどう違うのか、どう使い分ければいいかをまとめてみました。 ## RegExp.test() とString.search() まずはパターンにマッチするかどうかだけをチェックしたい時。 あるパターンが文字列に存在するかどうかだけを知りたいときは、RegExp.test() または String.search() を使

こういうの無いかなあと思って調べたらそのままあったのでメモ。 もし、パターンにマッチするものについて、マッチしたテキスト以上の情報を得たいと考えたとき、文字列ではなく MatchObject のインスタンスを返す finditer() が便利です。以下に例を示すように、なにかの文章の全ての副詞と、 その位置を 調べたいと考えたとき、下記のように finditer() を使います。 : >>> text = "He was carefully disguised but captured quickly by police." >>> for m in re.finditer(r"\w+ly", text): ... print '%02d-%02d: %s' % (m.start(), m.end(), m.group(0)) 07-16: carefully 40-47: quickly

正規表現の文字クラスの略記法 \d と \s と \w がいつのまにかアレレなことになっていたのでメモ。(1 Perl 5.8 以降で正規表現を使うには use utf8 が必須。 use utf8 では \d と \s と \w の文字クラスの内容が Unicode のカテゴリーに基づいている。 InDesign（Boost）も同様。 PCRE や Ruby は変わりなし。 (2 参考資料：perldoc の perlrecharclass 参考資料：Programming Perl の 5.4. Character Classes ちょっと詳しく見ていきます。 ＊以降、Perl ＝ use utf8 の Perl ほとんど全ての人が [0-9] の10文字として使っていますが、Perl では \p{Nd} です。ただし、Perlのバージョンによって（対応しているUnicodeバージョン

この記事は abicky.net の 正規表現の先読み・後読みを極める！ に移行しました

柔軟性の高い正規表現を書こうとすると，避けて通れないのが先読み・後読みです． 先読み・後読みに関して，いままではとりあえず的な理解をしていたのですが，それだと説明できない正規表現に遭遇したので，説明できるまで理解を深めてみました． とりあえず的な理解 正規表現を使って間もない人が先読み・後読みを理解するための説明です． 肯定的先読み(?=pattern) 次の正規表現では直後にbarがあるfoo(barは含まない)に一致します． foo(?=bar) 否定的先読み(?!pattern) 次の正規表現では直後にbarがないfoo(barは含まない)に一致します． foo(?!bar) 肯定的後読み(?<=pattern) 次の正規表現では直前に barがあるfoo(barは含まない)に一致します． (?<=bar)foo 否定的後読み(?<!pattern) 次の正規表現では直前にbarがな