ようこそ!浜村拓夫の世界へ

    ブログ内検索

    最近の記事

    ブックマーク数の多い記事

    Blog Translation

    Powered By FC2ブログ

    Powered By FC2ブログ
    ブログやるならFC2ブログ


    FC2ブログ LOGIN

    with Ajax Amazon

    スポンサーサイト

    このエントリーを含むはてなブックマーク はてなブックマーク - スポンサーサイト あとで読む
    上記の広告は1ヶ月以上更新のないブログに表示されています。
    新しい記事を書く事で広告が消せます。

    正規表現は大事!

    このエントリーを含むはてなブックマーク はてなブックマーク - 正規表現は大事! あとで読む
    コンピューターを使った作業で、同じことの繰り返しは、自動化したいです。
    テキスト処理(文字列の取り扱い)で、同じパターンが出てくるなら、正規表現を使えばOKですね?

    正規表現

    サルにもわかる正規表現入門

    1.正規表現とはなにか?
     端的に言えば、「いくつかの文字列を一つの形式で表現するための表現方法」です。
     では、なぜこの表現方法が有名なのかといえば、この表現方法を利用すれば、たくさんの文章の中から容易に見つけたい文字列を検索することができるためです。



    正規表現 - Wikipedia

    正規表現(せいきひょうげん、英: regular expression)とは、文字列の集合を一つの文字列で表現する方法の一つである。
    正規表現はテキストエディタ、ワードプロセッサをはじめとするアプリケーションソフトでパターンマッチ文字列を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。




    ●正規表現の参考書
    プログラマーの人は、みんなどうやって正規表現を勉強しているんだろう?
    枯れた技術(安定した仕様)を学ぶ → やっぱ本が便利ですよね?

    新しい事柄を学ぶとき、
    (1) 薄い本
    (2) 厚い本
    という順番で読むと、挫折せずにうまくいきます。

    仕事頭がよくなるアウトプット勉強法 - 浜村拓夫の世界

    *スキルアップのための本は「薄い本&厚い本」
     薄い本はやさしくまとめてあるので、まず概略や基礎用語を頭に入れることに役立ちます。
     厚い本は難しいことや専門的なことも網羅されているため、辞書代わりに使います。



    「薄い本」に該当する、概略や基礎用語は、ネットで仕入れられるので、次のステップに相当する「厚い本」を読んでみたいと思います。
    …というわけで、オライリー本をまず押さえておけばいいかな?

    正規表現クックブック
    Jan Goyvaerts / Steven Levithan
    オライリージャパン
    2010-04-15
    ¥ 4,536


    詳説 正規表現 第3版
    Jeffrey E.F. Friedl
    オライリージャパン
    2008-04-26
    ¥ 5,184


    反復学習ソフト付き 正規表現書き方ドリル (WEB+DB PRESS plus)
    杉山 貴章
    技術評論社
    2010-12-22
    ¥ 3,002


    正規表現ポケットリファレンス (POCKET REFERENCE)
    宮前 竜也
    技術評論社
    2006-02
    ¥ 2,030


    正規表現辞典 (Desktop reference)
    佐藤 竜一
    翔泳社
    2005-07-12
    ¥ 3,218



    ●正規表現は有限オートマトン

    コンピュータの基礎 その9 Poketora日記

    入力とその時の状態によって出力が決定される機械をモデル化したものを、オートマトンと言います。
    つまり、オートマトンとは、出力が入力だけでなく過去の入力によって決まる機械です。
    コンピュータの世界では、処理を表現するためにオートマトンの概念を使うことがあります。
    オートマトンの内、最も単純なモデルを有限オートマトンと言います。

    有限オートマトンの別の表現として、正規表現があります。
    正規表現とは、パターンを表現するための規則の集まりを示したものです。



    状態遷移図

    「詳説 正規表現」を読む - ありえるえりあ

    用語の定義
    検索対象文字列 → テキスト(text)
    (正規表現)検索パターン → パターン(pattern)
    テキスト内にパターンが見つかること → マッチする



    正規表現のメカニズム
    ・NFA(Nondeterministic Finite Automaton) 非決定性有限オートマトン
    ・DFA(Deterministic Finite Automaton) 決定性有限オートマトン

    有限オートマトン → 状態数が有限。入力と状態に応じて状態遷移する
    オートマトンによって定義される言語 → オートマトンが受理する入力記号列の集合
    NFAもDFAもどちらも正規表現を認識可能。

    NFA(非決定性有限オートマトン) → ある状態から、ある入力で複数の状態へ遷移可能
    DFA(決定性有限オートマトン) → ある状態から、ある入力で遷移可能な状態はひとつまたは存在しない

    正規表現のNFAの作成 → まず正規表現からNFAの遷移グラフを作成します。 後で、NFAからDFAに変換します。



    NFA vs. DFA

    NFAとDFAの現実
    ・本だけ読んでいると、DFAの方が恰好良い
    ・DFAはNFAより速い (*)
    ・NFAは最悪のケースで指数オーダーの計算量になる

    (*) egrep(DFA)がgrep(NFA)より速いという伝説の根拠
    egrepの方が遅くなる例は作れます。
    DFAは事前に計算することで、テキストのサイズに対してNFAよりスケールする。

    ほとんどのツールはNFA。
    NFA → perl, python, ruby, tcl, emacs, sed, vi

    DFA → awk, lex, egrep
    ハイブリッド(前方参照が不要ならDFA、必要ならNFA) → GNU grep




    ●構文解析
    正規表現(オートマトン)でうまく処理できないパターンには、構文解析や他のアルゴリズム(計算法)を適用してみればよいでしょうか?

    PHPの正規表現 - 浜村拓夫の世界

    正規表現の能力を超えるデータはどう扱えばいいのか?
    一番のお勧めは、ANTLRを使って字句解析(lexer)、構文解析(parser)するプログラムを生成する方法です。
    一昔前なら、lex/yacc、flex/bison, JavaCCなどしか選択肢がなかったのですが、今は断然ANTLRが便利です。




    ●類似データの取り扱い手法
    完全一致の検索は簡単だけど、微妙に違う類似検索は難しいのかな?

    レーベンシュタイン距離 - 浜村拓夫の世界

    レーベンシュタイン距離は、二つの文字列がどの程度異なっているかを示す距離である編集距離の一種類である。
    具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。
    スペルチェッカー等において、二つの文字列がどの程度に類似しているかを具体的な値として示す一つの方法である。
    Bitapアルゴリズムが、レーベンシュタイン距離がある値以下のパターンを検出するアルゴリズムとして知られている。agrepという実装がある。



    重要なのは’類似’ではなく’違い’だ–まったく新しい着想に基づく高精度の画像検索アルゴリズム

    ・米カーネギーメロン大学で開発された「Cross-domain Image Matching」という方法
    ・ターゲットの画像(A)を大量のランダムな画像と比較して、それらと当の画像との、もっとも著しい違いを記録する(Ra)。
    ・もう一つのターゲット画像(B)に対しても同じ記録を作成する(Rb)。
    ・RaとRbがほぼ同じなら、画像AとBは類似性が高い。





    どれだけ似ているか?という発想ではなく、似ていないもの同士が、逆によく似ているはず、という発想。


    ●構造の表現方法
    正規表現(オートマトン)や木構造で表現できないデータは、傾向=ベクトルとして扱えばOK。

    潜在意味解析 - Wikipedia

    潜在意味解析(英: Latent Semantic Analysis, LSA)は、ベクトル空間モデルを利用した自然言語処理の技法の1つで、文書群とそこに含まれる用語群について、それらに関連した概念の集合を生成することで、その関係を分析する技術である。
    潜在的意味解析とも。

    1988年、アメリカ合衆国でLSAの特許が取得されている。
    情報検索の分野では、潜在的意味索引または潜在意味インデックス(英: Latent Semantic Indexing, LSI)とも呼ばれている。



    潜在的意味インデキシング(LSI)徹底入門 - あらびき日記

    Latent Semantic Indexing - naoyaのはてなダイアリー

    「人とコンピュータの間で『あうんの呼吸』を実現したい」 | 東京工科大学
    ベクトル空間法

    自己組織化写像 - Wikipedia

    自己組織化写像(Self-organizing maps (SOM), Self-organizing feature maps (SOFM))は人工ニューラルネットワーク(en:Artificial neural network)の一種であり、大脳皮質の視覚野をモデル化したものである。

    ネットワークにおける実際の学習はベクトル量子化を参考にしている。

    SOMのアルゴリズムにはどんな次元の特徴ベクトルでも入力できるが、多くの応用では、入力の次元は高い。出力されるマップは1次元や2次元など、入力と異なる次元でも構わない(「近傍」が定義できればよい(→位相幾何学))。しかしポピュラーなのは2次元もしくは3次元のマップである。なぜなら、SOMは次元の拡大でなく、主に次元の削減に用いられるからである。

    可視化手法としてのSOM
    高次元のデータや、ベクトル空間上にないデータを、2次元の平面上などのより低次元で容易に観察できる空間に写像する(次元削減する)ことで可視化できる。次元削減によって可視化を行う手法としては他に主成分解析などがある。曲面上に分布している場合は主成分解析ではうまく削減できないが、SOMなら高次元空間上でのニューロンの配置が曲面にフィットするよう変形するので表示用の空間を有効に利用できる。



    自己組織化マップ(SOM:Self-Organizing Map) - 九州工業大学

    自己組織化マップ(SOM)とは

    SOMはニューラルネットワークの一種で
    与えられた入力情報の類似度をマップ上での距離で表現するモデルです.
    技術が発達した現代では複雑な情報が数多く存在します.
    しかしそのような高次元データを人間が瞬時に理解することは困難です.
    SOMは高次元データの中に存在する傾向や相関関係の発見などに応用することができ
    人間が高次元データを視覚的に理解する手助けを行ってくれます.

    SOMの特徴を一言であげるとすれば
    様々な高次元データを予備知識なし(教師なし)にクラスタリングできる点にあります.
    またこれが自己組織化といわれる所以です.


    ベクトル空間からマップ空間への写像

    とりあえず、正規表現で頑張ろう!

    関連記事

    コメント

    コメントの投稿


    管理者にだけ表示を許可する

    トラックバック

    トラックバックURL:
    http://hamamuratakuo.blog61.fc2.com/tb.php/1100-65d23231

    FC2Ad

    上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。