A_006 正規表現関数を用いた文字列照合アルゴリズムの高速化に関する研究(A分野:モデル・アルゴリズム・プログラミング)
スポンサーリンク
概要
- 論文の詳細を見る
正規表現による文字列照合問題では、有限オートマトン(FA)を用いたアルゴリズムがよく知られている。一方で、この問題はキーワードによる文字列照合問題の一種の拡張とみなす方法もある。我々はこの方法に正規表現関数を適用した手法について研究を行っている。キーワードによる文字列照合問題を解くアルゴリズムである。Boyer-Moore法(BM法)やKnuth-Morris-Platt(KMP法)では、照合が失敗した際に次の照合開始位置を効率的に決定することで高速な照合を実現している。今回の研究ではそのような開始位置を決定する方法を、正規表現関数を用いた手法に導入することで、文字列照合の高速化を考察した。キーワードによる文字列照合問題を解くアルゴリズムはいくつかの型に分類できるが、ここではKnuth-Morris-Pratt型(KMP型)について述べる。
- 2006-08-21
著者
関連論文
- A_006 正規表現関数を用いた文字列照合アルゴリズムの高速化に関する研究(A分野:モデル・アルゴリズム・プログラミング)
- 3近傍可逆セルオートマトンについて (計算機科学基礎理論とその応用)
- 関係デ-タベ-スにおける従属性検証システムの実装 (代数・論理・幾何と情報科学)
- 関係文字列を用いた協調実行言語の意味論
- 1B-5 協調型言語における試験等価性と失敗等価性の関係とモデル検査への適用(テスト・検証,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 関係計算の自動検証の理論(サイバー増大ページ論文概要,サイバー増大号)
- 協調型言語に基づく並列プロセスのモデル検証 (計算機科学基礎理論の新展開)
- 5L-5 一斉通信のデッドロック解析へのプロセス代数的アプローチ