高速かつ省メモリなGoogleの正規表現ライブラリ re2 についてのメモ - naoya_t@hatenablog
高速かつ省メモリなGoogleの正規表現ライブラリ re2 についてのメモ。 RE2は、PCRE や Perl や Python で使われているようなバックトラッキング正規表現エンジンの代替となる、高速で、安全で、スレッド・フレンドリーなC++ライブラリです。 バックトラッキング・エンジンは一般に機能や便利なシンタックスシュガーが満載ですが、小さな入力に対してさえも指数関数的に時間がかかる羽目に陥ることがあります。RE2はオートマトン理論を用い、正規表現検索が入力のサイズに対し線形の時間内に走ることを保証しています。 検索を固定量のメモリに制約できるように、RE2はメモリ制限を実装しています。 どのような入力もしくは正規表現を処理しなくてはならないとしても、小さな固定のC++スタック量のみ使用するようRE2は設計されています。そのため、RE2はスレッドスタックを任意に拡げられないマルチスレ
regex比較 - 初学者の箸置
通りすがりの方から「鬼車はー？」というリクエストをもらったので*1・・・全体書き直してフレームワークみたいにしてみた。 http://github.com/tkuro11/RegProf _Profベースクラス 例のバックトラックパターンのみ（しかも1から28固定）というしょぼいプロファイルだけしかとらないんだけど、とりあえずクラスにくくりだしてみた。 _Profクラスをベースにして、これの仮想関数になっている RE()を各regexエンジン用に書き加えてサブクラス化する。その後、ベースクラスのインスタンスメソッド Prof()を呼び出すと自分の RE()を読んでその時間を返す、と言った感じの方式、例えば前回の RE2であれば、 #include <re2/re2.h> #include "_Prof.h" struct RE2Prof : public _Prof { bool RE(s
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
Unicodeで「漢字」の正規表現 – ものかの
改訂：2017/07/22 Unicode 10.0に合わせて書き直し。正規表現を簡易にしようとしてやりすぎていたのを修正。 改訂：2023/03/21 U+30000以降を追加。InDesignの正規表現を追記。 正規表現で漢字の範囲指定をする場合、Unicodeではどうするかが悩ましいところです。 Unicodeの漢字の範囲として [一-龠] にしている例を見かけます。しかしこれは旧規格JIS X 0208の漢字が含まれる範囲をUnicodeの中から切り出しているだけです。互換漢字ブロックをまるごと取りこぼしているので、WindowsのシフトJIS（CP932）の拡張漢字に当たるものが含まれていません。現規格JIS X 0213の第３・第４水準漢字も考慮されていません。簡易な範囲指定だとしても、新常用漢字の「𠮟」が含まれておらず、今から見るとあまりに時代遅れです。 Unicodeのす
m//の戻り値 - だるろぐ
久々に。 use strict; use warnings; use Data::Dumper;sub p {warn Dumper [@_];my @c = caller;print STDERR " at $c[1]:$c[2]\n\n"} my $s = "hoge"; my ($d,$r) = (0,0); ($d,$r) = (($s =~ /sss/),($s =~ /hoge/)); p $d, $r; # case 1 ($d,$r) = (($s =~ /hoge/),($s =~ /aaa/)); p $d, $r; # case 2 これを実行したときの結果が、予想と違って悩んだ。 俺の予想 case 1 ($d, $r) は (undef, 1) case 2 ($d, $r) は (1, undef) 現実 % perl h.pl $VAR1 = [ 1, und
へぼへぼCTO日記 - メールアドレス(addr-spec)の正規表現
能書き 前エントリを書いてからいろいろと調べていて驚いたんだけど、日本語のwebsiteで、それなりにまともにRFC822(RFC2822,RFC5322)に準拠した(もしくはきちんと意図的に準拠していない部分を選択している)正規表現はPerlだろうがPHPだろうがRubyだろうが軽くぐぐった程度では見当たらない。PerlのモジュールのEmail::AddressもEmail::Validも程度の差はあれ問題を抱えている。そこらへんの既存の出回ってる正規表現にどういった問題があるかなんてことは次回エントリにて。 というわけで、Perl、PHP、RubyでRFC5322準拠なメールアドレス(addr-spec)の正規表現を以下に示します。尚、addr-specの最終的な正規表現のみならずそれを作成するに至る部分も併記してあります。これは、最終的な正規表現だけでは難解すぎてとても理解できないか
Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.
redditから 正規表現： その理論、実装と歴史 - karasuyamatenguの日記
「recursive backtracking」による実装のPerlをはじめとする近代言語の正規表現と古典的Unixのfinite automataによる実装の比較をする記事。正規表現に興味がある方にはお勧め。 http://swtch.com/~rsc/regexp/regexp1.html? 以下、ザっと目を通したインプレッション。時間のあるときに一日かけてジックリ読んでみたい文献だ。 Perlをはじめとするスクリプト言語系とgrep,awkなど伝統的Unixのregexの実装には決定的な違いがある。前者はbacktrackingを使い、後者はUnix創始者のKen Thompson氏が1960年代に発明したNFAベースのもの。実は「a?」や単独のキャラクタ「a」が繰り返されるような「特殊」な正規表現だと、Thompson NFA実装の方が桁違いに速い。 Ahoの本などで正規表現とかF
JavaScript正規表現メモ。 (JavaScriptでよく使う書き方。) - こせきの技術日記
タイトル変えました。旧タイトル「JavaScriptでよく使う書き方」。よく使うけど毎回忘れる。 正規表現にマッチするかどうか。 RegExp#testを使う。 /abc/.test("abcdefg") // => true String#searchはマッチした位置を返す。マッチしない場合は-1。先頭にマッチすると0でfalseなので注意。真偽値が欲しい場合はString#searchを使わない。 "abcdefg".search(/xxx/) // => -1 "abcdefg".search(/def/) // => 3 "abcdefg".search(/abc/) == false // => true 正規表現の部分マッチを得る。 部分マッチを得るには、RegExp#execかString#matchを使う。execとmatchの速度は大して変わらない。 正規表現のベンチマー
正規表現まとめサイト | エンタープライズ | マイコミジャーナル
Smashing Magazine - WE SMASH YOU WITH THE INFORMATION THAT WILL MAKE YOUR LIFE EASIER, REALLY. 文字列を処理するにあたって正規表現は欠かせない機能といえる。任意の文字列やテキストファイル、HTML/XMLから特定のキーワードを検索したり取り出し、置換をおこなうにあたって、正規表現が使えると使えないのとでは、プログラミングの手間やツールの活用度合いが変わってくる。 正規表現は便利で強力な機能だが、その独特の表記方法はプログラマ初心者には敷居の高いものでもある。Glen Stansberry氏による正規表現に関するチュートリアルや資料、ツールなどのまとめがSmashing MagazineにEssential Guide To Regular Expressions: Tools and Tutori
Extractorを使った正規表現ライブラリの簡易ラッパー - kmizuの日記
Scalaの正規表現ライブラリは、Javaの正規表現ライブラリのラッパーになっていて、Javaのものよりもだいぶ使いやすくはなっているが、パターンマッチに使う時は、以下のように必ずvalなどでいったん変数に代入しなければならないという欠点がある。 scala> val numPat = """[0-9]+""".r numPat: scala.util.matching.Regex = [0-9]+ scala> "123" match { case numPat() => println("matched") } matchedそこで、簡単な場合には、パターンにいちいち名前を付けずに済むようなライブラリをExtractorを使って書いてみた。これを使うと、たとえば上のコードは次のように書ける： scala> ("123", """[0-9]+""") match { case Succe
tokuhirom blog
Blog Search when-present<#else>when-missing. (These only cover the last step of the expression; to cover the whole expression, use parenthesis: (myOptionalVar.foo)!myDefault, (myOptionalVar.foo)?? ---- ---- FTL stack trace ("~" means nesting-related): - Failed at: ${entry.path} [in template "__entry.ftlh" at line 3, column 25] - Reached through: #include "__entry.ftlh" [in template "entry.ftlh" at
Perlの正規表現のバグ? (前編) - moriyoshiの日記
「鬼車の[[:print:]]はPOSIX流じゃないらしい」でid:ockeghemさんやid:nihenさんと先週いろいろやりとりしてた中で、一つだけ解決していない問題があった。 utf8フラグが立っているかどうかでPOSIX文字クラスのマッチの挙動が変わるという件。 大変詳しい調査をありがとうございます。トラックバックのブログに書いたように、[:print:]の挙動は、Perlでもutf8フラグの有無でも変わってくるようです。[:print:]は実用できないなと思いました え?まじ?と思うも、一応Perlのコード例も出していたので検証しないわけにはいかない。以下のようなコードで試してみたが、utf8フラグが立っていない場合と同じ結果となり、再現しないのだ。 use encoding 'utf8'; for (split //, "\t\r\n a") { printf("%d:%d:%
perlの正規表現でUnicodeブロックを使う - (ﾟ∀ﾟ)o彡 sasata299's blog
2009年03月13日07:07 Perl perlの正規表現でUnicodeブロックを使う 今日、Unicodeブロックというものを初めて知りました。正規表現で利用できます。 例えば、半角英数字もしくは半角記号かどうかをチェックするときには、このように書けるんです。 #!/usr/bin/perl use strict; use warnings; use utf8; use Encode qw(encode_utf8); my $str = "aあ-い0bc〜d９e"; for ($str =~ /./g) { if (/\p{InBasicLatin}/) { print encode_utf8("$_ is latin\n"); } else { print encode_utf8("$_ is not latin\n"); } } \p{InBasicLatin} の部分が半角英
テスト駆動で 0 から 255 の数字にマッチする正規表現へ変形してみる - Tociyuki::Diary
ぶくま経由で、RFC 3986 URI の日本語訳にたどり着き、読んでいました。スムーズな日本語ですんなりと読めて、良い訳だと思いました。私は誤訳を見つけられませんでした。 それはともかく、読んでいる最中に、RFC3986 だけではないのですが、IPv4 アドレスの数字にマッチする構文が、正規表現向けでないのに改めて気になりました。RFC の記述をそのまま正規表現にすると、バックトラックをおこす書き方になっています。 バックトラックがおきないようにするには、先頭から1文字ずつ見ていくだけで残りの選択肢のどれに進めばいいか決定できるようにすればよろしい。ということで、これをテスト駆動で正規表現に向いた記述に変更してみました。 ⇒ http://www.studyinghttp.net/cgi-bin/rfc.cgi?3986#Sec3.2.2 IPv4address = dec-octet
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
正規表現の確認
re-try
jsregex
fam.cx
http://qootas.org/blog/archives/2006/06/perl_regex_perf.html