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

宇丹 裕一朗  若林 真一  永山 忍  
(FIT2010推薦論文)

誌名
電子情報通信学会論文誌 D   Vol.J94-D   No.6   pp.935-944
発行日: 2011/06/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 計算機システム
キーワード: 
ストリングマッチング,  FPGA,  正規表現,  近似文字列照合,  シストリックアレー,  

本文: PDF(399KB)>>
論文を購入




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