大会名称 |
---|
2010年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2010 |
発行日 |
2010/8/20 |
セッション番号 |
4Q |
セッション名 |
設計技術と再構成可能システム |
講演日 |
2010/09/08 |
講演場所(会議室等) |
Q会場(ウエスト2号館3F 第5講義室) |
講演番号 |
RC-003 |
タイトル |
高速なテキスト検索のための近似正規表現マッチングアルゴリズムとそのFPGA実装 |
著者名 |
宇丹 裕一朗, 若林 真一, 永山 忍, |
キーワード |
近似文字列照合, 正規表現マッチング, FPGA, シストリックアレイ |
抄録 |
テキスト検索とは,与えられた文字列(パターン)に類似する文字列をテキストから探し出すという問題である. 主な応用としてはバイオインフォマティクスにおけるDNA配列の解析などがある. 本論文では,パターンの記述に正規表現の部分クラスを用い,パターンに類似するすべての部分文字列をテキストから探し出す問題を近似正規表現マッチングと呼ぶ. そして,この問題を1次元シストリックアレイを用いて高速に解くことができるハードウェアアルゴリズムを提案し,そのFPGA実装により提案アルゴリズムの有効性を示す. |
本文pdf |
PDF download (190.3KB) |