通信プロトコルコンパイラPreccsにおける正規表現パターンマッチングの高速化

• Item type: Trans(1)
• 公開日: 2007-03-15
• タイトル: 通信プロトコルコンパイラPreccsにおける正規表現パターンマッチングの高速化
• タイトル / 言語: en
• タイトル: Optimization Techniques for Regular Expression Pattern Matching in the Preccs Compiler
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 株式会社システム計画研究所／東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Research Institute of Systems Planning, Inc. / Graduate School of Information Science and Technology,The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology,The University of Tokyo
• 著者名: 服部, 健太; 平木, 敬
• 著者名(英): Kenta, Hattori; Kei, Hiraki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Preccsは通信プロトコルの記述に特化したプログラミング言語であり，拡張した正規表現によってメッセージ形式を定義し，並行プロセス計算に基づいてメッセージの送受信手順を記述する．本発表では，正規表現パターンマッチングを高速に行うためにPreccsコンパイラが用いている2つの手法について説明する．1つ目はDFAによるパターンマッチングである．Preccsでは正規表現を拡張し，マッチしたフィールドの参照や，参照した値による繰返しマッチをサポートしているため，DFAを用いたパターンマッチングの手法は自明ではない．2つ目はパターンマッチングのスキップである．ある正規表現とマッチしたメッセージに対して，さらに狭いパターンと再度マッチングを行う場合，すでにマッチ済みの事実を利用して，2度目のマッチング処理の一部を省略することが可能になる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Preccs is a programming language for communication protocols. Message formats are defined with extended regular expression and rules for message sequences are defined with notation based on a concurrent process calculus. In this presentation, we describe two optimization techniques for regular expression pattern matching. The first is use of a DFA engine. It is not trivial to develop DFA for pattern matching, because regular expression is extended such that a part of matching pattern can be referred as value and iterative matching by the referred value is supported. The second is to skip matching characters. When trying to match again with a narrower pattern to a message matching with a ceratain pettern, it is possible to skip to a part of the process using the informations about the previous matching.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 48, 号 SIG4(PRO32), p. 73-73, 発行日 2007-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会