不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価
スポンサーリンク
概要
- 論文の詳細を見る
テキスト中から与えられたパターンを見つけ出す文字列照合問題は,Webの情報検索やDNA配列の特定パターンの検索に用いられるなど,幅広い応用範囲を持つ.パターンの編集に置換のみを許した近似文字列照合は,不一致を許す文字列照合と呼ばれ,テキスト全域での一致スコアを求めるために,正確な一致場所を求める文字列照合よりも計算量が大きい.この問題の解法として,高速フーリエ変換(FFT)を利用した高速な確率的アルゴリズムがいくつか提案されており,それらは文字から数値への写像の生成方法により,写像の総数と,得られる推定値の精度が異なる.我々の提案するアルゴリズム10)は写像の総数が理論上での最小であり,精度も提案されているアルゴリズム中で最も高い.本稿では,Atallah らのアルゴリズム1)による推定値の精度と実験的な比較を行い,提案アルゴリズムの推定値の精度がより高いことを確認した.
- 2009-12-24
著者
-
馬場 謙介
九州大学大学院システム情報科学研究院
-
森 雅生
九州大学大学評価情報室
-
森 雅生
九州大学総合理工学研究科情報システム学専攻
-
池田 大輔
九州大学大学院システム情報科学研究院
-
中藤 哲也
九州大学情報基盤研究開発センター
-
廣川 佐千男
九州大学情報基盤研究開発センター
-
森 雅生
九州大学 大学評価情報室
-
池田 大輔
九州大学システム情報
-
馬場 謙介
九州大学附属図書館
-
中藤 哲也
九州大学情報基盤センター
-
中藤 哲也
九州大学
-
池田 大輔
九州大学システム情報科学研究院
関連論文
- 〈「ディジタル図書館」ワークショップ第38回 発表論文〉スモールサイエンスのための e-Science リポジトリの要求分析
- 概念束によるヒヤリハット報告書の分析システム (言語理解とコミュニケーション・第1回集合知シンポジウム--言語処理が紡ぎ出す未来)
- 外部連携サービスによる機関リポジトリの潜在需要の解析
- FFTを用いた近似文字列照合のスコア計算のための最適な写像
- Ｗｅｂシラバス統合による教育情報ライブラリ構築
- 接尾辞木を用いた圧縮尺度計算による効率よいスパムポスト検出手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- プレーリストからの曲目やアーティストの相互関連抽出
- SNS(Social Networking Service)における信頼と図書館における応用(第33回ディジタル図書館ワークショップの論文)
- 6U-6 ウェーブレットに基づく音声認証システムの精度向上にむけて(ネットワーク応用,学生セッション,ネットワーク)
- ＜発表論文＞SNS (Social Networking Service) における信頼と図書館における応用 （「ディジタル図書館」ワークショップ 第33回）
- PVMを用いた1次元有限セルオートマトンの挙動解析
- CCSに基づく並列処理言語の実装(計算理論とその応用||)
- リサイクルデータを用いた大学情報のデータベース化について
- 大学情報の組織内共有と活用 －九州大学大学評価情報室の取組から－
- 大学評価担当者の抱える現場の課題--アンケートの結果から
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- D_040 WebDBをコンポーネントとするセマンティック・メタ検索の提案(D分野:データベース)
- 九州大学における一般情報処理教育支援システムについて
- マルチエージェントの知識論理における多様相化した推論の正当性について(アルゴリズムと計算量理論)
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- 安全な暗号プロトコルの十分条件について
- FFTを用いた繰り返しパターン発見手法の提案(セッション5B : パターン抽出)
- 3次元分散共有仮想空間を媒介とする3次元マルチメディアデータの交換・流通環境
- 統合検索システムDAISEnでの検索サイトフォーム分析(セッション9B : 情報統合)
- 統合検索システムDAISEnでの検索サイトフォーム分析(情報統合)(「夏のデータベースワークショップ(DBWS2003)」一般)
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- 6R-5 ユーザーの注視領域を考慮した類似画像検索システムの開発(自動生成・合成,学生セッション,人工知能と認知科学)
- 新個人認証システムPersonal IDが変える図書館の個人情報管理 : 個人情報やプライバシーに配慮した一歩先行く図書館サービスとは
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- 平成18年度における研究開発 電子図書館システムの研究開発
- WebDBのQuery Formにおけるメタデータ自動抽出
- Web データベースにおける入力フォーム情報の自動抽出
- 安全な暗号プロトコルの十分条件について
- D-1-5 掌紋による生体認証の計算時間と精度の関係(D-1.コンピュテーション,一般セッション)
- AI-1-6 ディペンダブルVLSI設計技術への挑戦(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- Bit-parallel Computation for Wavefront Algorithm
- RNA二次構造予測における塩基対数最大化アルゴリズム高速化の検討(セッション5)
- RNA二次構造予測における塩基対数最大化アルゴリズム高速化の検討(セッション5)
- 近似文字列照合プログラム実行の特徴解析と高速化に関する検討(解析・省電力,SWoPP2006)
- ハッシュを用いたID照合における計算時間についての考察(セッション2)
- RNA二次構造予測における塩基対数最大化アルゴリズム高速化の検討
- ビットパラレル手法によるアライメントアルゴリズム
- ビットパラレル手法によるアライメントアルゴリズム(バイオ)
- ビットパラレル手法によるアライメントアルゴリズム
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- FFTを用いた近似文字列照合のスコア計算のための最適な写像
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- 不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価
- 2K1 大学評価の報告書作成支援システムと大学情報のデータウェアハウスについて((課題研究2)ICTを活用した教育支援環境,教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- Webデータベースにおける入力フォーム情報の自動抽出(セッション4: メタデータとWebデータベース応用)
- Webデータベースにおける入力フォーム情報の自動抽出(セッション4: メタデータとWebデータベース応用)
- 部分文字列増幅法による共通パターン発見アルゴリズム
- 交代数を用いた多言語Webテキストからの共通部分特定とラッパーの生成法(データマイニング)
- D-039 検索サイトにおける入力項目と検索結果のフィールド名の対応調査(D.データベース)
- テンプレート発見問題の定式化と部分文字列増幅法を用いたアルゴリズム(文字列アルゴリズム)
- 部分文字列増幅法による共通パタン発見アルゴリズム(パターン認識)
- 半構造化文書に対する木構造と文字列を組合せたラッパーの自動生成法(コーパス構築)(セマンティックウェブと自然言語処理その他一般)
- 文字列の頻度分布による共通パタン発見(パタン発見)(セマンティックウェブと自然言語処理その他一般)
- 文字列の頻度分布による共通パタン発見
- 九州大学自己点検・評価関連情報システム(セッション2:XML応用システム)
- FETを用いた繰り返しパターン発見手法の提案(パターン抽出)(「夏のデータベースワークショップ(DBWS2003)」一般)
- Web上の多言語テキストデータからのラッパー自動生成
- D-5 検索サイトのための集合演算子の自動推定(Web検索(1),D.データベース)
- n-gram交代数を用いた半構造化データの不要部分削除
- n-gram交代数を用いた半構造化データの不要部分削除
- Webグラフの構造解析 (「Webシステムにおける情報獲得支援技術」)
- 3次元分散共有仮想空間を媒介とする3次元マルチメディアデータの交換・流通環境
- $\lambda_C$計算と$\lambda_P$計算との対応(計算理論とその応用)
- 近似文字列照合のための効率的なアルゴリズム
- D-1-6 動的刈り込み接尾辞木を用いた圧縮尺度計算によるスパム検出(D-1. コンピュテーション,一般セッション)
- 観光イベントについての「といえば検索」の提案(「コミュニティ上での知識の共有・再利用」及び一般)
- D-037 形式概念を用いた倒産情報の分析システム(D分野:データベース,一般論文)
- 背表紙画像を用いたネットワーク透過な仮想書架
- ＜発表論文＞研究支援ツールとしての機関リポジトリにおけるバージョン管理機能 （「ディジタル図書館」ワークショップ 第33回）
- ユビキタス図書館 ： 偏在する図書館サービス
- 電子図書館と利用者のプライバシー ： 履歴・個人情報の保護と利用の両立を目指して
- Ｗｅｂサービスを用いた読書録サービスの設計と実装
- 単純な部分文字列照合によるＷｅｂからの書誌情報の抽出
- 仮想書架における背表紙画像生成の自動化
- 高性能ＲＦＩＤリーダ付き書架の性能評価と新たな図書館サービスの提案
- ＜発表論文＞ＲＦＩＤ技術を用いた図書館自動化への期待 （「ディジタル図書館」ワークショップ第26回）
- RFID技術を用いた図書館自動化への期待
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- ウェブデータマイニング(「データマイニング特集号」)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集(Webマイニング)(テーマ:「Webマイニングによる情報活動と自然言語処理」その他一般)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集(Webマイニング)(テーマ:「Webマイニングによる情報活用と自然言語処理」その他一般)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集
- 概念の活性値の伝搬・争奪による並列意味解析
- 高性能RFIDリーダ付き書架の性能評価と新たな図書館サービスの提案
- 電子図書館の歴史と九大附属図書館の取り組み
- リサイクルデータを用いた大学情報のデータベース化について
- The Computational Complexity of Hereditary Elementary Formal Systems
- 情報インフラとしての大学情報データベースのあり方について--大学および社会の視点から
- 国立大学法人評価における教育成果に関する記述の現状と課題について : 現況調査表・現況分析結果の記述の分析を中心に
- 国立大学におけるインスティテューショナル・リサーチの機能・人・組織等に関する意識と現状 : IR担当理事に対するアンケート調査結果を基に
- 機関リポジトリと研究者データベースの連携
- SNSと検索エンジンを結合したコミュニティ型探索プラットフォームの提案