Dec 25, 2015

特定の文字列を含まないという正規表現

正規表現で、特定の文字列を含まないパターンを記述するのは難しい。

その文字列の文字数が少なければ、例えば"ABC"を含まないとするなら

([^A]|A[^B]|AB[^C])*
という方法がありそうで、筆者は時々やってしまうのだが、これは正しくない。"AABC"があると"AA"がA[^B]にマッチ、"ABABC"があると"ABA"がAB[^C]にマッチしてスルーしてしまうし、"A"や"AB"で終わるとマッチしないからである。
この方向で進めると、一例としては、
([^A]|A(B?A)*([^AB]|B[^AC]))*(A(B?A)*B?)?
という式になるそうだが(大崎 博基さんの「Perl正規表現雑技」より)、これは少なくとも筆者には読めない。

特定の文字を含まない、という式は、例えば"A"を含まないなら[^A]*と簡単に書けるのに、特定の文字列を含まない、となると途端に難しくなるのは不思議である。

特定の文字列を含まない行にマッチする、よく知られたパターンとして、

(?!.*ABC).*
というやつがある。(?!...)はnegative lookahead assertion(否定先読み)というやつで、その先に...が続かない、という条件を表す。(?=...)はその先に...が続くというpositive lookahead assertionであり、ABC(?=DEF)は"ABCDEF"の"ABC"にマッチし、ABC(?!DEF)は"ABCDEF"の一部でない"ABC"にマッチする。
(?=...)(?!...)は、POSIX仕様などの正規表現の古い仕様には含まれず、grepなど一部使えない処理系があるが(Emacsもサポートしていない。外部コマンドを活用しろということらしい)、PerlやJavaScriptでもサポートされており、現在はほとんどの処理系で使えると言える。

(?!.*ABC).*の弱点は、文字列全体のマッチにしか使えないことである。例えば、文字列中の"STA"〜"END"の部分を検索したいが、途中に"ABC"を含む場合は除外したいと思って、STA(?!.*ABC).*ENDと書くと、"STAxxENDxABC"のように、"END"の後に"ABC"がある場合もマッチしなくなってしまう。

今回、そういうのが必要になって、悩みながら、何かいい方法は無いかと思ってWeb上を探してみたら、

((?!ABC).)*
というのを見つけた。この文字から先が"ABC"でない任意の文字が0個以上、である。すごい発想だと思った。

Web上には(.(?!ABC))*と書いている例もあり、同じだと勘違いして、早速(.(?!ABC))*を使い始めたのだが、よく考えると(.(?!ABC))*には問題があることに気付いた。これだと、"ABC"を2文字目から検索することになり、先頭がABCの場合に除外されず、マッチしてしまうのである。さらに、例えば、途中に"EN"を含まない"STA"〜"END"の部分を検索するつもりでSTA(.(?!EN))*ENDと書くと、途中に"EN"が無くても、"END"の直前の1文字が必ず.(?!EN)に当てはまらない("END"の"EN"で引っ掛かる)ので、何にもマッチしなくなってしまう。
((?!ABC).)*にはこれらの問題は起こらない。
それと対称にして、(?<!)のnegative lookbehind assertionを使って(.(?<ABC))*としても上記の問題は起こらないが、より複雑だし、手元のPerlで試すと10%ほどの速度低下が見られたので、これを使うメリットは無いだろう。

結局、外側の()によって後で参照可能なグループが増えないように、(?:(?!ABC).)*という形にすることによって、筆者の問題は解決した。

See more ...

Posted at 20:55 in PC一般 | WriteBacks (0)
WriteBacks

Dec 06, 2015

スパコン「京」を目撃

昨日、神戸市他が主催する、一般向けセミナー「意外と知らない?暮らしを支えるスパコンの働き」に行ってきた。

その前の見学会で、スーパーコンピューター「京」を見てきた。

下の階でポスターの展示をゆっくり見てたら、「京」を見る時間が10分くらいしか無くなってしまった。
見学室に入ると、説明員の方が会場からの質問を受けていた。次々に質問がなされていて、
「京」は一般向けに時間貸ししていること(部分的に借りれる)、
「京」の100%を借りると一時間百数十万円であること、
「京」を100%使う用途も20以上あるが他の人が使えなくなるので月1〜2日に決めていること、
CPUはSPARCというやつ、
OSがLinuxであること、
「京」の候補地は最後に神戸と仙台に絞られ、インフラの利で神戸に決まったこと、
2020年運用開始予定のポスト「京」も今と同じ場所に作られること、
がわかった。

セミナーの開会の挨拶では、文部科学省の人がスパコン研究プロジェクトの必要性を熱く語っておられた。
「行政事業レビュー」で「数ある事業の中で最も説明されてこなかったのがスパコン事業だ」と厳しく追及された件は、実際には色々説明していたが、政治家に発せられたその一言だけをマスコミが取り上げてフォローしないから世間的にスパコン研究が無駄という印象になっているのが実態であること、なぜ「2位じゃダメなんでしょうか」の理由は、単純明快なので何度も言われてきたことだが、1位のものを製造する技術があって初めて国際的な競争力になるから、ときっちり説明された。

講演は4つなされた。セミナーは撮影禁止だったので、細かい内容は伏せるが、無難な概要と、筆者がした質問と講演者からの回答を記しておく。

1. 「シミュレーション事始め」
 シミュレーションするには、物理モデルを作って、四則演算のみのアルゴリズムにして、プログラムを作る、精度を上げるには解像度を上げる(シミュレーションする三次元的な位置を細かく取る)必要があり、3乗や4乗(三次元+時間)のオーダーで計算量が増えるのでスパコンが必要になる、スパコンの根幹の技術は複数台のコンピューターを接続する技術、という一般的な話。
Q:インターネット上の複数台のコンピューターを接続して並列計算を行う場合の接続技術とスパコン内のプロセッサーの接続技術との特徴的な違いは?
A:距離と遅延。隣のノードの計算結果が頻繁に必要になる場合はスパコンが有利。

2. 「『京』が拓く天気予報の未来」
 スパコンによるシミュレーションと、全方位レーダーによる高速で詳細な雨雲の観測などの最新の観測技術を組み合わせることによって、雨雲が無い状態から30分後に発生するゲリラ豪雨も10分や15分前に予測できるようになるなど、新たなことができるようになる可能性が色々あるという話。

3. 「世界最先端スパコンが変えるタイヤづくり」
 タイヤの分子構造を兵庫県にあるSPring-8で計測して「京」てシミュレーションすることによって、低転がり抵抗、高グリップ性能のタイヤの耐摩耗性能を倍にする方法を発見したという話。
Q:動的な物理モデルの正確さはどのようにして確認したのか、正確でなかった時はどうやって改良したのか?
A:やはり高性能な計測機器を用いて実物の動きを計測しながらモデルを作成している。

4. 「電気自動車高性能化への挑戦:スパコンと放射光が解き明かす電池の姿」
 SPring-8と「京」を用いることによって原子構造、電子構造のシミュレーションを実現し、充電式電池の性能を向上する構造を見つることができたという話。

See more ...

Posted at 12:43 in 雑記 | WriteBacks (0)
WriteBacks