データ構造

【でーたこうぞう (data structure)】

概要

与えられたデータを, 計算の高速化のために構造をもたせて記憶する手法の総称. 目的に合わせ, あるいくつかの機能を, 高速, あるいは省メモリで行えるよう設計される. 例えば, ある言葉を$n\,$ 個の言葉の辞書データから検索するとき, 通常の配列では, 最悪で挿入・削除に $O(n)\,$, 検索に $O(\log n)\,$ か, 挿入と削除に $O(1)\,$, 検索に $O(n)\,$ の時間を要する. 二分探索木というデータ構造は, これらの機能を $O(\log n)\,$ 時間で行い, 使用メモリは $O(n)\,$ である.

詳説

　データ構造とは, 与えられたデータに対して, そのデータを使った計算の高速化, そのデータを記憶するために必要な領域の減少等の目的で, データに構造を持たせ, データに対する操作の効率化を行う手法の総称である. あるいくつかの機能を, データの記憶形式と, その形式のデータを操作するアルゴリズムにより実現する.

　通常のコンピューター言語では, データを蓄える手法として配列かリスト, またはその両方が用意されている. 配列は指定した位置にあるデータに${\mbox{O}}(1)\,$時間でアクセスでき, リストは与えられたデータを並べて記憶し, 隣のデータに${\mbox{O}}(1)\,$時間でアクセスできる. リストは配列により実現可能だが, リストで配列は実現できない.

　配列やリストは最も単純なデータ構造である. ここで両者を使ったデータ構造の性能の違いを見てみよう. 例として $n\,$ 行 $n\,$ 列の行列 $M\,$ を保持し, 他の行列との掛け算を行うためのデータ構造を考える. 通常の配列を使用して行列を記憶する場合 ${\mbox{O}}(n^{2})\,$ のメモリが必要であるが, もし $M\,$ の非零要素の数 $H\,$ が小さい場合, 非零要素を連結してリストで持つことにより, 記憶容量を ${\mbox{O}}(H)\,$ まで減少させることができる. 行列の掛け算は非零要素に関する部分だけ計算を行えばよいので, 計算時間も2つの行列の非零要素の数の積に比例する. しかし, リストは一要素を記憶するのに必要なメモリが配列に比べて大きいので, 非零要素が多い場合はリストのほうが遅く, メモリも多くなる.

　次に, $n\,$ 個の用語の辞書データを保持し, その中から与えられた用語を検索するためのデータ構造を考える. データに変更がないときは, 用語を辞書順で並べて記憶すれば, 二分探索により${\mbox{O}}(\log n)\,$時間で1つの用語が検索できる. しかし, 辞書データの中の用語を削除する・新しい用語を追加する, という操作が必要な場合には, 通常平均的に${\mbox{O}}(n)\,$の時間を要する. 辞書順に並べるかわりに, 二分探索木 (AVL木, 2-3木など) というデータ構造を用いれば, 使用メモリは${\mbox{O}}(n)\,$のままで, これらの操作の実行時間を${\mbox{O}}(\log n)\,$まで減らすことができる. このようにデータの動的な変化に対しても効率が良く操作が行えるよう設計されたデータ構造を動的データ構造という. 辞書データを扱う他の効率の良いデータ構造としてはハッシュ表が知られている.

　動的データ構造の中で最も基礎的なものとしてはヒープが挙げられる. 基本的なヒープは, $n\,$ 個の要素の中の最小値を得る・要素の追加・削除するという操作を, 1回あたり${\mbox{O}}(\log n)\,$時間で実行し, またメモリ使用量も${\mbox{O}}(n)\,$である. 応用も広く, プリム法 (最小木問題のアルゴリズム), 最少費用フロー問題 (最小費用流問題) のアルゴリズムなどで使用される. また, 改良版の Fヒープ (フィボナッチヒープ) は, 最短路問題を解くアルゴリズムで使われている. その他, $n\,$ 個の区間の集合を保持し, 質問点を含む区間を列挙する, 区間の挿入・削除を行う, などの操作を1回あたり ${\mbox{O}}(\log n)\,$時間で行う区分木, 大きさ $n\,$ の木構造のグラフに対し, 合併・分割・変形・ある頂点の子孫数を求める, など多くの操作を${\mbox{O}}(\log n)\,$時間で行う動的木, 集合の合併と要素の探索を高速化し, $n\,$ 回の合併と $m\,$ 回の探索の合計時間がほぼ ${\mbox{O}}(m+n)\,$ となる集合ユニオン・ファインド木, 動的に変化する有向グラフの強連結性を保持し, $k\,$ 回の枝の挿入・削除を ${\mbox{O}}(kn^{1.3})\,$ で行うデータ構造[7], など数多くのものが考案されている. 文字列やグラフを扱う離散アルゴリズムの多くは, これらの基礎的なデータ構造に手を加えたものを使用することにより高速化されている. また, アルゴリズムの動作記録を変換して保持し, パラメーターの変更による計算結果の変化を出力するデータ構造は動的計画, 組み合わせ最適化問題の感度分析などに応用が広い.

　データ構造, 特に動的データ構造は, 計算幾何学における発展が著しい. 幾何的なデータはデータの量に対して構造が複雑なものが多い. 例えば, 平面上の $n\,$ 点の集合に対し, 距離が $d\,$ 以下の2点を枝でつないだグラフ(幾何グラフ)を考える. このグラフは $O(n^{2})\,$ 本の枝を含む可能性があるが, このグラフを記憶するには点集合だけ記憶すれば十分である. つまり, メモリや計算時間を省略するためには, 点集合のデータから必要な枝の情報を得るための構造が必要となる. また, 枝の交差など, グラフ的な情報からは導けないものもあり, それらの情報を効率的に得るためにもデータ構造はかかせない. 幾何的なデータ構造としては, 平面上の$n\,$点集合の凸包を保持し, 点の追加・消去に対し新しい凸包を ${\mbox{O}}(\log n)\,$ 時間で求めるもの, $k\,$ 次元の $n\,$ 点集合に対し, 質問点から近い順に点を1個あたり平均 ${\mbox{O}}(1)\,$時間で出力する $k-d\,$ 木, 質問領域の中に含まれる点を1個あたり${\mbox{O}}(\log ^{k-1}n)\,$ で出力するレンジサーチ木 [8], 平面をいくつかの領域に分割する $n\,$ 本の線分の集合が与えられたとき, 質問点がどの領域に含まれるかを ${\mbox{O}}(\log n)\,$ 時間で答える領域探索などが挙げられる. その他に, 線分の集合に対し, ある点から見える点, すなわち2点をつなぐ線分が他の線分と交差しないような点集合を保持するデータ構造など, 交差, 領域に関してさまざまなデータ構造が考案されている.

　前述の幾何的なデータ構造は, 幾何的な対象を扱う計算幾何学のアルゴリズムで多く使われている. 多角形の三角形分割の線形時間アルゴリズムなども高度な技術を用いてデータ構造を活用しているが, しかしその反面複雑になりすぎ, 現実的ではないという欠点がある. また, 個々のアルゴリズムで使用するデータ構造がそのアルゴリズムに特化した, 一般性のないアルゴリズムとデータ構造も少なくない. それゆえ, 最近では簡素化も視野に入れた研究が進んでいる. スパーシフィケイション [6] もその一つであり, 動的データ構造高速化の一般化した技術を提供している. スパーシフィケーションにより, $n\,$ 頂点 $m\,$ 枝を持つ無向グラフの最小全張木を保持するデータ構造は, 1回の枝の追加・削除・重みの変化に対する計算時間が, ${\mbox{O}}(m^{1/2})\,$ から${\mbox{O}}(n^{1/2})\,$ に高速化される. また同様にグラフの二部グラフ性の判定, 二連結性の判定, 頂点連結性の判定なども, 一回の操作の計算時間が ${\mbox{O}}(m)\,$ から ${\mbox{O}}(n)\,$ に高速化される.

　最後に参考文献を挙げる. 動的木などグラフ的なデータ構造は [3], [4], [5] 等に詳しい. また, 幾何的データ構造については [1], [2] 等が詳しい.

---

参考文献

[1] F. P. Preparata and M. L. Shamos, "Computational Geometry - An Introduction," Springer-Verlag, 1985. 浅野孝夫, 浅野哲夫 訳,『計算幾何学入門』, 総研出版, 1992.

[2] 今井浩, 今井圭子,『計算幾何学』, 共立出版, 1994.

[3] T. H. Cormen, C. E. Leiserson and R. L. Rivest, "Introduction To Algorithms," The MIT Press, 1990. 浅野哲夫, 岩間和生, 梅尾博司, 山下雅史, 和田幸一 訳,『アルゴリズムイントロダクション 1,2,3巻』, 近代科学, 1995.

[4] 浅野孝夫,『情報の構造 上, 下』, 日本評論社, 1994.

[5] 茨木俊秀,『アルゴリズムとデータ構造』, 昭晃堂, 1989.

[6] D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig "Sparsification - A Technique for Speeding up Dynamic Graph Algorithms," FOCS, 33, 1992

[7] S. Khanna, R. Motwani and R. H. Wilson, "On Certificates and Lookahead in Dynamic Graph Problems," SODA, 1995

[8] D. E. Willard "New Data Structures for Orthogonal Range Queries," SIAM Journal on Computing, 14 (1985), 232-253.