マルチトラック文字列の順列パターン照合と索引構造
スポンサーリンク
概要
- 論文の詳細を見る
文字列の多重集合,すなわちマルチトラック文字列上の新しいパターン照合として順列パターン照合を提案する.順列パターン照合では,トラック長n,トラック数Nのマルチトラックテキスト中に出現するトラック長m,トラック数Mのマルチトラックパターンを探す我々はこの問題が,一般のアルファベットではO(nN log lΣl)時間・0(mM+N)領域,整数型のアルファベットではO(nN)時間・領域で解くことができることを示す.また,テキストとパターンのトラック数が等しい場合(全順列パターン照合)に対し,我々はマルチトラック接尾辞木と呼ばれる新たな索引構造を提案し,このデータ構造の0(nN log lΣl)時間・0(nN)領域構築アルゴリズムを示す.マルチトラック接尾辞木を用いることで,全順列パターン照合問題が0(mN log lΣl+occ)時間で計算可能であることを示す.
- 2012-08-27
著者
-
稲永 俊介
九州大学大学院システム情報科学研究院
-
篠原 歩
東北大学大学院情報科学研究科
-
坂内 英夫
九州大学大学院システム情報科学府情報理学専攻
-
成澤 和志
九州大学大学院システム情報科学府情報処理学専攻
-
成澤 和志
東北大学大学院情報科学研究科
-
坂内 英夫
九州大学大学院システム情報科学研究院
-
桂 敬史
東北大学大学院情報科学研究科
-
坂内 英夫
九州大学大学院システム情報科学府
関連論文
- 無限n-ボナッチ文字列の繰り返し構造について
- 基本形式体系に対する非終端記号の導入 (コンピュテーション)
- 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム
- 平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム
- 半導体歩留り解析へのデータマイニング適用手法の提案
- 文字列の繰り返し構造の平均解析 (理論計算機科学の深化と応用)
- 連を多く含む文字列発見のための探索的手法 (理論計算機科学の深化と応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- 接尾辞配列による効率的な文字列上の同値類計算
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 間引き：ロボットのスキル発見における評価の削減手法
- 移調を許した圧縮文字列照合アルゴリズム
- 基本形式体系に対する非終端記号の導入
- 長さ優先置換による文字列圧縮の線形時間アルゴリズム(文字列アルゴリズム)
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- A-025 非可逆圧縮を用いた類似性指標と画像検索への応用(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-024 信頼区間上限の不確実性サンプリングへの応用(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 5N-2 文字列に含まれる繰り返し構造の頻度について(アルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- DS-1-6 例数制限付き教示の複雑さ(DS-1.計算理論における学生の研究パワー:COMP学生シンポジウム,シンポジウムセッション)
- DS-1-5 非終端記号を導入した基本形式体系の言語記述力について(DS-1.計算理論における学生の研究パワー:COMP学生シンポジウム,シンポジウムセッション)
- 置換のランク付けに対する$O$($n$log log$n$)ビット領域の線形時間アルゴリズム (理論計算機科学の深化と応用)
- 例数制限付き教示の複雑さ (理論計算機科学の深化と応用)
- 3R-2 通信規約学習の拡張による協調精度の向上(学習,学生セッション,人工知能と認知科学)
- 1V-3 間引きを用いたパス技術の自律学習(学習・推論,学生セッション,人工知能と認知科学)
- 電子マネーシステムの価値保存形式を考慮したモデル化(Session 3)
- 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-12 文字列に含まれる連構造(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- イベント列データにおけるVLDCエピソード生成モデル (「メディアとAI」および一般)
- 半導体歩留り解析に回帰木分析を適用するための仮説検証手法の提案
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習
- 非線形コラージュシステムにおける文字列パターン照合
- 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
- 役を構成するゲームに対する効率的な行動決定アルゴリズムの提案
- マルチトラック文字列の順列パターン照合と索引構造 (Theoretical Foundations of Computing)
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム (Theoretical Foundations of Computing)
- 組込環境用プロセス仮想マシンの実装とETロボコンへの適用 (制御研究会 : ETロボコン2012におけるソフトウェア設計モデル)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム
- マルチトラック文字列の順列パターン照合と索引構造
- 種々のパターン照合問題に対するポジションヒープの構築(一般)
- 類似度に基づくポリフォニックな楽曲の分類
- 2-E-7 SAT ソルバを用いた学位論文審査の時間割作成システムの試作(スケジュール(1))
- マルチトラックデータ上の近似順列パターン照合と索引構造
- 文字列に含まれる連の最大指数和の解析 : n=57までの厳密値と新たな下界2.03696の発見
- SVMによる2部ランキング学習を用いたコンピュータ将棋における評価関数の学習(情報・システム基礎)
- 高階圧縮の高速化と効率の良い符号化