講演抄録/キーワード |
講演名 |
2010-03-12 11:15
FPGA上に実現した二つの近似文字列マッチングアルゴリズムの比較 ○清水敬介・中原啓貴・笹尾 勤・松浦宗寛(九工大) VLD2009-123 |
抄録 |
(和) |
テキスト中に現れるパターンの出現位置を求める問題を厳密文字列マッチングという. 一方で, パターンを編集したものをテキスト中に求める問題を近似文字列マッチングという. 本論文では, 3つの編集~(削除, 挿入, 置換)を考える. 編集の度合いを定量的に表したものを編集距離という. 近似文字列マッチングの多くのアルゴリズムは動的計画法に基づく. 本論文では, 近似文字列マッチングを動的計画法で求めるNaive法とLL法について述べ, 最小編集距離を計算する回路の面積を見積もる. Altera社FPGA上に二つの実現法を実装し, 面積と動作周波数を求めた. 面積見積り値が実装結果と一致してることを示す. |
(英) |
An approximate string matching finds the most similar pattern in the text.
A dynamic programming is used for the approximate string matching. This paper considers two algorithms: Naive method and LL method. Also, it derives area complexities with respect to the pattern length. Our implementations on an Altera's FPGA agree with the derived area complexities. |
キーワード |
(和) |
近似マッチング / FPGA / / / / / / |
(英) |
Approximate Matching / FPGA / / / / / / |
文献情報 |
信学技報, vol. 109, no. 462, VLD2009-123, pp. 145-150, 2010年3月. |
資料番号 |
VLD2009-123 |
発行日 |
2010-03-03 (VLD) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2009-123 |