高速な複数文字列照合アルゴリズム : FAST
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータによる文書処理にとって文字列の照合は最も基本的な操作である.文書処理の高速化への寄与が大きいので,効率の良い照合手法が求められている.パターンが1つの場合にはBoyer-Moore法が最も効率の良い手法として知られているが,この方法では複数パターンを同時に照合することはできない.複数パターンを同時に照合する方法としてはAho-Corasick法が有名であるが,効率は Boyer-Moore 法より劣る.筆者らは「パターンの後方からの照合」というBoyer-Moore法の基本的なアイデアと,「パターン照合機械による照合」というAho-Corasick法の基本的なアイデアを結合して,FAST法(A Flying Algorithm for Searching Terms)を考案した.FAST法では複数のパターンを同時に効率良く照合することができる.この輪文ではFAST法の基本的な発想と具体的なアルゴリズムについて述べる.FAST法の効率についても考察し,実験による結果も示す.文字種が多いときやパターンが長いときには高い照合効率が得られることを確認した.例えば,パターン長が2と短くても文字種が94のときには,パターン数60以下ではAho-Corasick法より効率がまさっている.また,この方法は多大なメモリを必要とする欠点を有しているが,この軽減方法についてもふれた.
- 一般社団法人情報処理学会の論文
- 1989-09-15
著者
関連論文
- 部分文字列への最適な分割と文脈を考慮した変換による翻字処理(自然言語処理)
- K-074 知識を統合しユーザの疑問に答えるTVエージェント(K分野:ヒューマンコミュニケーション&インタラクション)
- A-15-22 番組に関するユーザの疑問に答えるTVエージェントシステム(A-15. ヒューマン情報処理, 基礎・境界)
- B-024 番組情報獲得システムにおけるラッパエージェント構築法(B.ソフトウェア)
- 9-8 字幕番組制作技術の研究開発フェーズ2における計画の概要
- テレビ受信ナビシステムにおける番組選択用リモコンに関する評価実験 : 様々な視聴者が視たい番組を簡単に選択受信できるテレビを目指して(映像メディア処理,感性情報工学及び一般)
- 2チャネル音声集音系における楕円積分を乗算係数に用いたスペクトル減算法(音声, 聴覚)
- 視線情報を利用した番組選択インタフェースの開発(セッション5 : マルチモーダルデザイン(2))
- K-074 視線情報を利用したテレビ用ユーザインタフェースの開発(K.ヒューマンコミュニケーション&インタラクション)
- 高齢者におけるデータ放送コンテンツのユーザーインターフェース評価 : 2種類のリモコンを比較して
- A-14-10 音声対話によるテレビ操作インタフェース実験システム
- 7-4 高齢者によるデータ放送コンテンツのユーザーインターフェース評価
- プロトコル分析を用いたデータ放送コンテンツのユーザーインターフェース評価
- プロトコル分析を用いたデータ放送コンテンツのユーザーインターフェース評価
- World Wide Webを用いた外国人名の英訳自動獲得(自然言語)
- オブジェクト連動データ放送システムに適したユーザインターフェースの開発とその評価実験
- オブジェクト連動データ放送システムに適したユーザインターフェースの開発とその評価実験(放送・サービス, ITS画像処理, 映像メディア及び一般)
- オブジェクト連動データ放送システムに適したユーザインターフェースの開発とその評価実験(放送・サービス, ITS画像処理, 映像メディア及び一般)
- 指さしポインターの開発とその性能評価実験
- 指さしポインターの開発とその性能評価実験(画像技術・視覚・その他一般)
- 4. エージェント技術から見たテレビの未来像(未来への手紙)
- OE2-4 視聴者の視聴タイプを利用した番組選択システム(動き出したエージェントシステム,学術系企画)
- 文字列探索アルゴリズムを拡張した複数2次元パターンの高速探索アルゴリズム
- 高速な複数文字列照合アルゴリズム
- エージェントの基礎技術 (放送におけるエージェント技術 特集号)
- エージェント技術の動向と放送への応用 (放送におけるエージェント技術 特集号)
- ユーザモデルエージェントによる番組選択システム
- 4D-4 野球番組ダイジェストのためのアナウンス文の自動生成
- 8-3 ニュース原稿のクラスタリングを用いたトピック抽出
- デジタル放送受信機用ユーザ・インタフェースの試作と評価(ヒューマンインタフェース基礎,インタラクション技術の原理と応用)
- デジタル放送用受信機の少ボタン型ユーザ・インタフェースの試作と評価
- パーソナル化するTV受信ナビシステムの開発
- パーソナルTVナビシステムの開発と評価結果
- パーソナルTVナビシステムの開発と評価結果(画像符号化・通信・ストリーム技術,及び一般)
- パーソナルTVナビシステムの開発と評価結果(画像符号化・通信・ストリーム技術,及び一般)
- パーソナルTVナビシステムの開発と評価結果(画像符号化・通信・ストリーム技術,及び一般)
- 視聴態様に適合するテレビ受信ナビシステムの開発(映像メディア処理,感性情報工学及び一般)
- 番組推奨を含むテレビ受信ナビシステムの開発と主観評価結果(ハイビジョンおよび一般)
- テレビ受信ナビシステムの開発と評価結果
- 3-1 多様な視聴者にやさしい高度放送受信ナビゲーションシステムの検討課題
- K-075 頭部の自由な動きを許容する視線測定システム(K.ヒューマンコミュニケーション&インタラクション)
- 研究開発中の情報バリアフリー技術(人にやさしい放送,人にやさしい映像情報メディア)
- 静止画検索システム FORKS の試作
- 日本語ニュース文の表現パターンの分析
- 日本語ニュース文の慣用パターンの分析
- 2)放送用静止画検索システムFORKS(光・フィルム技術研究会)
- 放送用静止画検索システムFORKS
- 検索システムFORKSの操作性改善
- 12-7 オントロジを利用した番組関連情報獲得手法(第12部門 映像検索)
- 21-6 SD法によるデジタル放送受信機用試作リモコンの評価(第21部門 ヒューマンインフォメーション)
- 6-1 Q&Aシステムのための野球オントロジーの設計に関する検討(第6部門 インターフェース,画像・動画処理,その他)
- 9-2 テレビ受信ナビシステムにおける望ましい番組選択用リモコンに関する考察(第9部門 ヒューマンインフォメーションII)
- 20-6 番組選択行動における視線と興味の関係(第20部門 視覚の心理・生理)
- ニュース原稿データベースからの表現パターンの抽出
- FAST 法の効率の推定と長パターン時のふるまい
- 高速な複数文字列照合アルゴリズム : FAST
- 2次元パターン高速探索アルゴリズム
- 15-7 ランドサット画像における判別手法の検討