FAST 法の効率の推定と長パターン時のふるまい
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータによる文書処理にとって文字列の照合は最も基本的な操作の1つである.また,文書データベースのフルテキスト検索においては中心的な役割を担っている.文書処理の高速化への寄与が大きいので,効率の良い照合手法が求められている.筆者らは「パターンの後方からの照合」という Boyer-Moore 法の基本的なアイデアと,「パターン照合機械による照合」という Aho-Corasick 法の基本的なアイデアを結合して,複数パターンを高速に検索する FAST 法(a Flying Algorithm for Searching Terms)をすでに考案している.この論文ではマルコフモデルに基づいて FAST法 の probe rate (テキスト1文字当りの照合回数)の推定式を導出し,誤差に対する検討を行う.さらに,実験結果と対比し,これと良く一致することを示す.文字種 (q) がパターン数 (k) とパターン長 (m) の積に比べて十分大きい場合には,Q(probe rate)=1/m+(m+1)k/2mqで表されることを示す.また,パターンが長くて文字種が多い場合には,直感に反してprobe rateがパターン数に関して単調増加とならない(つまり,パターン数が増加しているのに probe rate が下がることがある)ことを実験結果とともに示す.この現象が起こるところでは,タミーパターンを追加することによって,検索効率が改善され得ることについても言及する.
- 一般社団法人情報処理学会の論文
- 1991-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 ランドサット画像における判別手法の検討