無順序木の編集距離の指数時間厳密アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿ではNP困難問題として知られる無順序木の編集距離の効率的な指数時間アルゴリズムを扱う。n_1とn_2を2つの入力の木のノード数とすると、一般の場合に対するO(1.26^<n_1+n_2>)時間アルゴリズムを示す。このアルゴリズムは動的計画法、全探索、最大重み付き二部マッチングを組み合わせて得られる。また、次数が制限されアルファベットが固定の時には、任意の定数ε>0に対し、O((1+ε)^<n_1+n_2>)時間でこの問題が解けることを示す。この結果は、小さい部分木内の同じ部分集合に対する再計算を避けることにより得られたものである。
- 2012-06-14
著者
-
高須 淳宏
国立情報学研究所
-
深川 大路
国立情報学研究所
-
深川 大路
National Institute of Informatics
-
阿久津 達也
京都大学化学研究所バイオインフォマティクスセンター
-
田村 武幸
京都大学化学研究所バイオインフォマティクスセンター
-
深川 大路
同志社大学
-
阿久津 達也
京都大学化学研究所
-
Fukagawa Daiji
Graduate School Of Information Science And Technology The University Of Tokyo
-
深川 大路
同志社大学文化情報学部
関連論文
- 知識ベースを用いた人名検索時の曖昧性の解消(言語処理,夏のデータベースワークショップDBWS 2006)
- 知識ベースを用いた人名検索時の曖昧性の解消(言語処理)
- 代謝ネットワークの最小反応カットを求めるアルゴリズム
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- 混合ディリクレ分布を用いた文書分類の精度について(情報融合)
- 文書間類似度によるソフトウェアパターン間関連分析と複合関連の導出
- マージン最大化によるメトリック空間分割手法(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般)
- 学術情報の統合に向けた大規模リンケージ基盤の構築
- 3.アカデミックリンケージ : 膨大な学術情報へのアクセスを支援するリンケージ基盤(パートII:情報分野研究者のためのオンリーワン共有イノベーションプラットフォーム,情報爆発時代におけるわくわくするITの創出を目指して)
- 6ZK-4 情報爆発時代におけるP2P情報検索向きデータ配置手法(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 6J-4 情報爆発時代のための制約つきクラスタリングを用いた制約つきフィードバック手法の提案(情報爆発時代における情報検索・推薦技術およびWebコミュニティ分析,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 5J-1 Name Disambiguation Using Topics Extracted from Web Directories in Information-explosion Era
- E-014 軽量のテキスト処理による複数文書要約システム(E分野:自然言語・音声・音楽)
- P2P情報検索における索引とファイルの分散配置手法(分散ファイル・システム)
- 検索語の曖昧性解消のためのトピック指向単語抽出および単語クラスタリング
- SVM/HMMによる引用文献データの同定(情報抽出・構造分析)(ユビキタス社会における情報流通および一般)
- 効率的能動学習のための能動サポートカーネルマシン(人工知能,認知科学)
- 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良
- 2J-3 確率モデルに基づく木の類似度のパラメータ学習について(情報爆発時代におけるマルチメディアデータと交通情報システム,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- Statistical learning algorithm for tree similarity (特集「知識発見の諸科学への応用」および一般)
- 木の編集距離の文字列の編集距離による近似
- 特徴ベクトルからの化学構造の推定(Bioinformatics)
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 類似度の高い無順序木の比較に対する高速アルゴリズム
- ブール関数推定のための貪欲アルゴリズムの性能解析
- カテゴリ階層構造を考慮した確率的トピックモデルとその応用
- カテゴリ階層構造を考慮した確率的トピックモデルとその応用
- DNAマイクロアレイ画像の解析
- 学術論文文書画像からのページレイアウトに依存しない自動書誌要素抽出
- テキスト分類における訓練データと性能の実験的考察(電子文書処理)
- 無順序木の編集距離計算のための厳密アルゴリズム
- パラメータ化された連結成分分解を用いたWeb情報の有効利用(セッション9A : Web(1))
- パラメータ化された連結成分分解を用いたWeb情報の有効利用(Web(1))(「夏のデータベースワークショップ(DBWS2003)」一般)
- P2P情報検索における単語の頻度情報に基づくデータ配置手法
- 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- ゲノムDNA解析のための2次元電気泳動画像システム
- 複製文字列検知に基づいた Splog フィルタリング手法
- A clique-based method for the edit distance between unordered trees (特集 「脳科学と知識処理」および一般)
- Web資源を利用した学術論文閲覧支援システム
- CRFを用いた学術論文OCRテキストからの自動書誌要素抽出
- 制約付きプロファイルアライメント(文字列アルゴリズム)
- パス頻度ベクトルからのグラフ推定問題の困難性について
- オーソライズされた文献に基づくドメインの視覚化
- 共著関係に基づくグラフを用いた書誌情報における著者同定手法の提案と評価(データマイニング・学習, 夏のデータベースワークショップDBWS2005)
- 共著関係に基づくグラフを用いた書誌情報における著者同定手法の提案と評価(データマイニング・学習, 夏のデータベースワークショップ2005)
- D-12-48 様々な学術論文誌OCRテキストからの書誌要素抽出(D-12.パターン認識・メディア理解A(パターンメディアの認識・理解・生成),一般セッション)
- D-008 類似検索の高速化を目的としたPivot選択手法の実験評価(D分野:データベース,一般論文)
- 2K-2 索引木の均衡を考慮した類似検索索引手法(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 2K-1 高さ制約付き無順序木の高速類似検索アルゴリズムについて(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 6ZC-2 コミュニティベースQ&Aからの類似質問検索手法(情報爆発時代におけるWebパーティカル検索,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- テキスト認識エラーモデルによる引用文献文字列からの書誌要素の抽出(画像認識,コンピュータビジョン)
- Web 資源を利用した学術論文閲覧支援システム
- 信頼度の高いタイトル情報を利用した固有ページ発見(セッション2 : Web文書の蓄積とアクセス)
- 信頼度の高いタイトル情報を利用した固有ページ発見(セッション2 : Web文書の蓄積とアクセス)
- 検索語の曖昧性を解消するキーワードの提示手法(情報推薦, 夏のデータベースワークショップDBWS2005)
- 検索語の曖昧性を解消するキーワードの提示手法(情報推薦, 夏のデータベースワークショップ2005)
- リンク情報の利用によるWeb検索性能の改善
- レコード同定問題に関する研究の課題と現状(データ工学論文)
- 非構造Peer-to-Peerシステム上でのピアの有用性に基づいた問い合わせ処理(P2P)(夏のデータベースワークショップDBWS2004)
- 非構造Peer-to-Peerシステム上でのピアの有用性に基づいた問い合わせ処理(セッション10B : P2P)(夏のデータベースワークショップ : DBWS2004)
- 芸術家の技術保存用ビデオデータベースの構築・公開・研究計画
- 複数書誌データベース統合における重複エントリーの高速検出法(セッション5 : 文書データベース)
- D-12 パラメータ化された連結性に基づくWebページのグループ化(Web構造分析,D.データベース)
- パラメータ化された連結成分分解によるWebページのグループ化
- パラメータ化された連結成分分解によるWebページのグループ化
- 頻度情報を用いた類似文字列検索のための可変長N-gram
- 頻度情報を用いた類似文字列検索のための可変長N-gram
- An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees
- TCGにおけるシャッフル手法に関する計算機実験を用いた考察
- 情報検索における単語間の関係の効果
- 複数書誌データベース統合における重複エントリーの高速検出法(セッション5 : 文書データベース)
- Margin-Based Pivot Selection for Similarity Search Indexes
- Webページ群の構造解析とグループ化
- 学術文献画像の書誌情報の近似マッチング法
- 異種データベース間でのレコード照合に関する研究動向
- HTMLからの情報抽出と統合(電子文書処理)
- Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes
- HTML Table情報のXMLによる統合
- HTML Table情報のXMLによる統合
- 日英言語横断検索における関連性の重ね合わせモデルの効果(情報の検索とテストコレクション)
- 関連性の重ね合わせモデルを用いた日英言語横断検索
- 2000-DBS-122-8 英語テキストにおける関連性の重ね合わせモデルの検索特性
- DE2000-30 英語テキストにおける関連性の重ね合わせモデルの検索特性
- 軽量のテキスト処理による部分類似単語列検出手法(「自動化:推論,発見,学習,データマイニング」及び一般)
- 無順序木の編集距離の指数時間厳密アルゴリズム
- 情報検索における単語間の関係の効果
- 2000-DBS-122-46 全文検索における構造化インデクスの性能評価
- DE2000-68 全文検索における構造化インデクスの性能評価
- 無順序木の編集距離の指数時間厳密アルゴリズム
- プローブカーデータを用いた自動交通異常検出
- RD-001 類似文字列検索におけるLCP配列を用いた可変長N-gram抽出手法の効率化(情報アクセスとマイニング,D分野:データベース)
- D-010 類似文字列検索における可変長N-gramを用いたマージの効率化(ストレージと検索,D分野:データベース)
- D-022 クラスタリングを利用した距離尺度の組み合わせによるTop-k検索(クラスタリング,D分野:データベース)
- プローブカーデータを用いた自動交通異常検出(交通センシング,通信,情報処理,一般)
- CRFによる和英文の参考文献文字列からの自動書誌要素抽出(情報抽出と情報検索,ビッグデータとソーシャルコンピューティング,及び一般)
- Twitterと論文との自動対応付け(「ソーシャルコンピューティング研究最前線」,ポスター発表のためのショートプレゼン,ソーシャルコンピューティング)
- 文字列の距離空間上の最大マージン識別器とそのタンパク質科学への応用
- 無順序木の編集距離の指数時間厳密アルゴリズム