括弧列の簡単・簡潔な表現法
スポンサーリンク
概要
- 論文の詳細を見る
括弧列(balanced parentheses sequences,BP)は順序木の表現法であり,近年多くの研究がある.任意のn節点の木は2n+o(n)ビットで表現でき,木の上での様々な操作がword-RAMモデル上で定数時間で行える.それらは漸近的性能は良いが,データ構造が複雑であり,実用的な実装はない.本論文は,非常に簡単な括弧列のデータ構造を提案する.これは簡単なだけでなく,既存のものよりも理論的にも実際的にも優れている.必要な領域は2n+O(n/log n)ビットであり,低次項を改善しており,また,知られている全ての操作を定数時間で行える,その簡単さから,実装も易しい.また,必要な領域は備えている操作によって異なり,2.30n〜3.30nビットである.最もサイズの小さいものでも最近共通祖先や深さ指定祖先を計算でき,最も大きいものは次数やi番目の子を高速に求められる.これは既存の親と兄弟のみを求められる3.73nビットを用いる実装と比較して大きな改善である.
- 社団法人電子情報通信学会の論文
- 2008-10-03
著者
関連論文
- 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)
- Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)
- 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)
- DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths
- RA-003 A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting
- 圧縮接尾辞配列構築アルゴリズムの改良
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- 簡潔データ構造による全文検索のハードウェアを用いた高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- ディスクレパンシー基準によるディジタルハーフトーニング : 自動評価手法と最適化手法
- 実数列の大域的丸めの数え上げ
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- Computational Geometry on Statistical Manifolds for Clustering : Extended Abstract (Models of Computation and Algorithms)
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- Patrascu, M., Succincter (より簡潔な), Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp.305-313, 2008
- 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)
- k-集合合意問題を解く故障検知器
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- $k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
- 局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用)
- 部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 局所情報を用いたランダムウォークの拡張
- DNA配列に適した圧縮全文索引
- ラベル付けされたグラフ上におけるオンライン予測
- 曲線のピーク削減アルゴリズムの考察と実装
- F-050 数値データベースに対するエキスパート付き決定木の構築(F.人工知能)
- 境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)
- 負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)
- 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)
- DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 局所情報を用いたランダムウォークの拡張
- 順序木の新しい表現法
- 圧縮データ構造の更なる圧縮
- 量子計算での幾何学データ処理
- 動的簡潔順序木
- 4.超簡潔データ構造(特定領域研究「新世代の計算限界-その解明と打破-」)
- 括弧列の簡単・簡潔な表現法
- 大規模データ処理のための簡潔データ構造
- 最小重み負荷分散枝被覆について
- メモリの圧縮
- 木上の関数の簡単な並列計算アルゴリズム
- AGPUモデルでの並列ソートアルゴリズムの計算量について
- GPUのための並列計算モデル
- ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造(一般)
- 木上の関数の簡単な並列計算アルゴリズム
- DS-1-13 AGPUモデルにおけるマルチスレッディングの効果(DS-1.COMP学生シンポジウム,シンポジウムセッション)