講演名 | 2010-01-27 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般) 若葉 陽一, 若林 真一, 永山 忍, 稲木 雅人, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 正規表現マッチングとは,正規表現をパターンとし,与えられたパターンに一致する文字列を入力系列から検索する操作である.我々は,これまでに1文字の繰返しを指定する量指定子をパターンとして利用できる正規表現マッチングハードウェアを提案した.しかし,文字列のユニオンや文字の否定などの正規表現のサブクラスに対する量指定子のパターンに対するマッチングが必要になる場合もある.そこで,本稿では,文字列のユニオンや文字の否定に対して量指定子が適用可能なハードウェアアルゴリズムを提案し,提案ハードウェアを用いることで,パターンの実現に必要な回路面積を大幅に削減できることを示す. |
抄録(英) | Regular expression pattern matching is a problem to find substrings in a given text, which match with a pattern represented by regular expression. We have proposed regular expression pattern matching hardware that can realize iteration of a single character using quantifiers. However, some applications require patterns that include iteration of a subclass of regular expression, such as union of strings and negation of a character, using quantifiers. In this paper, we propose a hardware algorithm that can realize iteration of such a subclass of regular expression using quantifiers. FPGA implementation results show that the proposed algorithm significantly reduces the number of LUTs needed to realize those patterns. |
キーワード(和) | ストリングマッチング / Snort / 正規表現 / 量指定子 |
キーワード(英) | String Matching / Snort / Regular expression / Quantifier |
資料番号 | VLD2009-91,CPSY2009-73,RECONF2009-76 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2010/1/19(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般) |
サブタイトル(和) | |
タイトル(英) | Regular Expression Pattern Matching Hardware for Realizing Iteration of Strings Using Quantifiers |
サブタイトル(和) | |
キーワード(1)(和/英) | ストリングマッチング / String Matching |
キーワード(2)(和/英) | Snort / Snort |
キーワード(3)(和/英) | 正規表現 / Regular expression |
キーワード(4)(和/英) | 量指定子 / Quantifier |
第 1 著者 氏名(和/英) | 若葉 陽一 / Yoichi WAKABA |
第 1 著者 所属(和/英) | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
第 2 著者 氏名(和/英) | 若林 真一 / Shin'ichi WAKABAYASHI |
第 2 著者 所属(和/英) | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
第 3 著者 氏名(和/英) | 永山 忍 / Shinobu NAGAYAMA |
第 3 著者 所属(和/英) | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
第 4 著者 氏名(和/英) | 稲木 雅人 / Masato INAGI |
第 4 著者 所属(和/英) | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
発表年月日 | 2010-01-27 |
資料番号 | VLD2009-91,CPSY2009-73,RECONF2009-76 |
巻番号(vol) | vol.109 |
号番号(no) | 393 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |