文献

J-GLOBAL ID：201102246633432065   整理番号：11A0992017

近似正規表現マッチングのためのシストリックアルゴリズムとそのFPGA実装

著者 (3件)： 宇丹裕一朗 (広島市大 大学院情報科学研究科) ,  若林真一 (広島市大 大学院情報科学研究科) ,  永山忍 (広島市大 大学院情報科学研究科)
資料名： 電子情報通信学会論文誌 D  (IEICE Transactions on Information and Systems (Japanese Edition))
巻： J94-D  号： 6  ページ： 935-944  発行年： 2011年06月01日 
JST資料番号： S0757C  ISSN： 1880-4535  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近似文字列照合とは,与えられた文字列(パターン)に類似する文字列をテキストから探し出すという問題である。主な応用としてはバイオインフォマティクスにおけるDNA配列の解析などがある。本論文では,パターンの記述に正規表現の部分クラスを用い,パターンに類似するすべての部分文字列をテキストから探し出す問題を近似正規表現マッチングと呼ぶ。そして,この問題を一次元シストリックアレーを用いて高速に解くハードウェアアルゴリズムを提案し,そのFPGA実装により提案アルゴリズムの有効性を示す。(著者抄録)

シソーラス用語： *正規表現 ,  オートマトン理論 ,  *パターンマッチング ,  *シストリックアレイ ,  計算理論 ,  *FPGA ,  *文字列 ,  計算機ファイル ,  計算機アルゴリズム ,  遺伝学実験技術
準シソーラス用語： DNA配列解析 ,  *テキストファイル ,  *ハードウェアアルゴリズム

分類 (2件)： 人工知能  (JE08000Z) ,  半導体集積回路  (NC03162T)

引用文献 (17件)：

• J. Aoe (eds), Computer Algorithms: String Matching Strategies, IEEE Computer Society Press, 1994.
• J. Bispo, I. Sourdis, J. M. P. Cardoso, and S. Vassailiadis,“Regular expression matching for recon figurable packet inspection,” Proc.2006 IEEE International Conference on Field Programmable Tecnology, pp. 119-126, 2006.
• B. C. Brodie, R. K. Cytron, and D. E. Taylor,“A scalable architecture for high throughput regularexpression pattern matching,” Proc.33rd International Symposium on Computer Architecture, pp. 191-202, 2006.
• P. A. V. Hall and G. R. Dowling,“Approximate string matching,” ACM Comput. Surv., vol.12, no.4, pp. 381-402, 1980.
• M. C. Herbordt, J. Model, Y. Gu, B. Sukhwani, and T. VanCourt,“Single pass, BLAST-like, approxi mate string matching on FPGAs,” Proc.14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 217-216, 2006.

タイトルに関連する用語 (4件)： 近似 ,  正規表現 ,  マッチング ,  FPGA実装