FFTを用いた近似文字列照合のスコア計算のための最適な写像
スポンサーリンク
概要
- 論文の詳細を見る
文字列中から与えられたパターンを見つけ出す文字列照合問題は，Web の情報検索やDNA 配列の特定パターンの検索に用いられるなど，幅広い応用範囲を持つ．パターンの編集に置換のみを許した近似文字列照合は，不一致を許す文字列照合と呼ばれ，単なる文字列照合より応用範囲が広く，また難易度も高い．この問題の解法として，高速フーリエ変換(FFT) を利用した高速な確率アルゴリズムが幾つか提案されている．それらは文字から数値への写像の生成方法により，写像総数と，解の推定値の分散が異なる．本稿で提案するアルゴリズムは，総写像数が理論上での最小であり，推定値の分散も小さい．String matching is the problem of finding all occurrences of a given pattern string in a given text string. It is applicable to a wide range of fields, such as Web information retrieval and pattern discovery of DNA sequences. An extension of the string matching is string matching with mismatches, which allows inexact match with substitution, is expected to have wider application even though it has higher complexity. Several randomized algorithms have been proposed which use fast Fourier transformation (FFT) and run fast to solve the problem. All of these algorithms introduce certain number of mappings that convert symbols into numbers. The total number of such mappings and variance of estimates depends on the method to generate the mappings. The present paper shows an algorithm which achieves the theoretical minimum number of mappings, and yields an estimate with small variance.
- 2007-12-21
著者
関連論文
- FFTを用いた近似文字列照合のスコア計算のための最適な写像
- PVMを用いた1次元有限セルオートマトンの挙動解析
- CCSに基づく並列処理言語の実装(計算理論とその応用||)
- 大学情報の組織内共有と活用 －九州大学大学評価情報室の取組から－
- 大学評価担当者の抱える現場の課題--アンケートの結果から
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- D_040 WebDBをコンポーネントとするセマンティック・メタ検索の提案(D分野:データベース)
- 九州大学における一般情報処理教育支援システムについて
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- 安全な暗号プロトコルの十分条件について
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- 安全な暗号プロトコルの十分条件について
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- FFTを用いた近似文字列照合のスコア計算のための最適な写像
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- 不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価
- 2K1 大学評価の報告書作成支援システムと大学情報のデータウェアハウスについて((課題研究2)ICTを活用した教育支援環境,教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- リサイクルデータを用いた大学情報のデータベース化について
- 情報インフラとしての大学情報データベースのあり方について--大学および社会の視点から
- 国立大学法人評価における教育成果に関する記述の現状と課題について : 現況調査表・現況分析結果の記述の分析を中心に
- 国立大学におけるインスティテューショナル・リサーチの機能・人・組織等に関する意識と現状 : IR担当理事に対するアンケート調査結果を基に
- 機関リポジトリと研究者データベースの連携