プログラミング

k-d木(多次元二分探索木)の基本概念多次元二分探索木(略してk-d木)は、複数のキーを持つレコードを格納するためのデータ構造として定義されます。この構造は、統計学やデータ分析において数多くの「幾何学的」問題を解決するために実装されてきました。k-d木(k-dimensional tree の略)は、k次元空間内の点を整理するための空間分割データ構造です。k-d木は、多次元検索キーを用いた検索(例えば範囲検索や最近傍探索)など、さまざまな用途に活用されています。また、k-d木は二分空間分割木(BSP木)の特殊なケースとして扱われます。非形式的な説明:k-d木の仕組みk-d木は、すべての葉ノード

多方向ツリー（多分木）の定義多方向ツリー（multiway tree、多分木）とは、各ノードが2つ以上の子ノードを持つことができる木構造のことです。通常の二分木では子ノードは最大2つに制限されていますが、多方向ツリーではこの制限が緩和され、より柔軟なデータ構造を実現できます。もし多方向ツリーの子ノード数の最大値が m 個である場合、その木は「次数 m の多方向ツリー（m-way tree、m分木）」と呼ばれます。ノードの構造これまで学習してきた他の木構造と同様に、m-way ツリーの各ノードは以下の要素で構成されます。キー（鍵）フィールド： 最大 m-1 個子ノードへのポインタ： 最大 m 個

フィンガー探索（finger search）とは、データ構造が本来サポートする探索操作を拡張した手法で、クエリとともに構造内の特定要素への参照（これを「フィンガー」と呼びます）を与えることができる探索です。通常の探索時間は構造内の要素数の関数として表されることが多いのに対し、フィンガー探索の所要時間は、対象要素とフィンガー（基準点）との距離の関数として扱われる点が大きな特徴です。 フィンガー探索の基本的な考え方 m個の要素からなる集合において、2つの要素aとbの距離 d(a, b) は、両者のランク（順位）の差として定義されます。たとえば要素aとbがそれぞれ構造内でi番目とj番目に大きい要素で

動的フィンガー探索木とはフィンガー探索とは、あらかじめ保持しておいた位置（フィンガー）から目的の要素までの距離 d を基準に探索を行う手法です。先頭や根から探索を開始する通常の方法と比べ、d が小さい場合に大幅な高速化が期待でき、ソート済みリストのマージや計算幾何アルゴリズムなど、近接した位置への連続アクセスが発生する場面で特に威力を発揮します。動的なフィンガー探索データ構造には、このフィンガー探索に加えて、フィンガーで示された位置への要素の挿入・削除も効率的に行えることが求められます。フィンガー探索木の基本性質フィンガー探索木はB木の変種として定義され、移動可能なフィンガーを定数個だけ維持す

本記事では、レベルリンク(level links)の導入によって(2,4)木がどのように効率的な指探索(finger search)を実現できるのかを解説します。ここで説明する考え方は、b ≥ 2a を満たす、より一般的な高さ平衡木である(a,b)木のクラスにもそのまま適用できます。(2,4)木の基本性質(2,4)木とは、すべての葉が同じ深さを持ち、すべての内部ノードの次数(子の数)が2、3、4のいずれかである高さ平衡探索木として定義されます。要素は葉に格納され、内部ノードには探索を導くためのキーのみが格納されます。各内部ノードの次数が2以上であるため、(2,4)木の高さは O(log n)

決定論的な探索木に対するランダム化された代替手法として、「トレップ（treap）」と「スキップリスト（skip list）」という2つのランダム化二分探索木が広く知られています。どちらもエレガントなデータ構造として定義されており、ランダム化の導入によってシンプルかつ効率的な更新操作が可能になっています。本記事では、これらのデータ構造そのものを変更することなく、トレップとスキップリストを効率的なフィンガー検索木として実装する方法について解説します。両データ構造とも、期待計算量 O(log d) の時間でフィンガー検索をサポートします。ここでいう期待値は、データ構造の構築過程においてアルゴリズムが

スキップリストは、確率的に階層を構築することで平衡木に匹敵する高速な探索を実現する連結リスト型のデータ構造です。本記事では、スキップリストにおける「フィンガー探索（finger search）」の仕組みと、その基盤となる重要な特性についてわかりやすく解説します。 スキップリストにおけるフィンガー探索の基本 スキップリストでは、要素 b を含むノードを出発点として、別の要素 a に対するフィンガー探索を行うことができます。具体的には、そのノードの位置から探索をそのまま継続するだけでよく、必ずしもリストの先頭からやり直す必要はありません。 ここで重要なのは探索の方向です。a < b の場合

適応型マージソート（Adaptive Merge Sort）とは適応型マージソートは、通常のマージソートと同様にソート済みの部分リストをマージ（併合）していくソートアルゴリズムです。ただし、従来のマージソートが要素数1の部分リストから処理を開始するのに対し、適応型マージソートでは、リスト内にすでに存在する「整列済みの並び」を検出し、そのまとまりをそのまま初期の部分リストとして利用します。これにより、順序が整った要素を無駄に分割・再マージすることなく、マージの回数を大幅に削減できます。例として、次の図のようなリストを考えてみましょう。このリストは、あらかじめ2つのソート済み部分リストで構成されて

スプレー木（splay tree）は、自己平衡型二分探索木の一種であり、「最近アクセスした要素には再び素早くアクセスできる」という特別な性質を持つデータ構造です。挿入・検索・削除といった基本操作は、ならし計算量 O(log n) で実行できます。スプレー木の大きな特徴は、ランダムでない一連の操作に対して、そのパターンが事前に分からない場合でも、他の探索木よりも優れた性能を発揮することが多い点です。二分探索木における通常の操作はすべて、「スプレーイング（splaying）」と呼ばれる一つの基本操作と組み合わせて実行されます。スプレー木の基本的な性質各ノード a には、実数値のキー key(a)

動的最適性予想（Dynamic Optimality Conjecture）とはスプレー木（Splay Tree）は、SleatorとTarjanが1985年に提案した自己適応型の二分探索木です。アクセスされた要素を根へ移動させる「スプレー操作」により、頻繁にアクセスされる要素ほど素早く取り出せるようになるという特徴を持ちます。スプレー木には、ならし解析に基づく証明済みの性能保証がありますが、それとは別に、未証明のまま大きな注目を集めている予想が存在します。それが「動的最適性予想（Dynamic Optimality Conjecture）」です。この予想は次のように定式化されます。任意の二分

静的フィンガー定理（Static Finger Theorem）とは静的フィンガー定理は、スプレー木（splay tree）における一連のアクセス操作のコストを評価するための重要な定理です。ここでは、特定の要素 f を「フィンガー」と呼ばれる基準点として扱います。このとき、m 回の操作からなるシーケンスをスプレーする際のコストは、次の式によって上から抑えられます。O(m + n log(n) + Σ log(|f − i[j]| + 1))記号の意味|f − i|：フィンガー f と要素 i の間の、対称順（in-order）における距離を表します。m：最大 n 個のノードを持つ木に対して実行

ソリッドツリー(実線木)の基本概念 与えられた森(forest)に対して、一部の辺を「破線(dashed)」に、残りを「実線(solid)」として扱います。各非葉ノードは、その子のうちただ一つだけを実線の辺で結び、それ以外の子はすべて破線の辺で接続します。 より具体的には、どの木においても「右端の子」へのリンクを実線で保持し、その他の子へのリンクはすべて「破線」として作成します。 木の分解と仮想木(virtual tree) この操作の結果、木は複数の実線パス(solid path)の集合へと分解されます。実線パスの根どうしは、破線の辺によって別の実線パスと接続されます。 ここで、「仮想木(

仮想木（Virtual Tree）では、一部の辺は実線（solid）として扱われ、その他の辺は破線（dashed）として扱われます。通常のスプレー操作は、実線で構成される木（solid tree）の内部でのみ実行されます。仮想木内のノード y でスプレーを行うには、以下に示す手法が用いられます。 このアルゴリズムは、木を3回走査し（各パスで1回ずつ）、その都度木を書き換えていきます。第1パスでは、ノード y から開始して実線の木内でのみスプレーを行うことで、y から木全体の根までの経路が破線に変わります。続いて、スプライシング（splicing）によってこの経路を実線に変換します。最後にノード

データ構造と情報理論の分野では、効率的なデータ圧縮を実現するための重要な概念として「ハフマン符号」と「エントロピー」があります。本記事では、ハフマン符号の基本的な仕組みと歴史、そしてシャノンエントロピーの理論的背景から具体的な計算方法までを、わかりやすく解説します。 ハフマン符号とは ハフマン符号とは、可逆データ圧縮（ロスレス圧縮）で広く利用されている「最適な接頭辞符号（プレフィックスコード）」の一種です。 この符号を構成する手法は「ハフマン符号化」と呼ばれ、David A. Huffman（デイビッド・ハフマン）がMITの博士課程（Sc.D.）在学中に考案し、1952年の論文「A Meth

シンプルな構築アルゴリズム ハフマン木は、各文字の出現頻度(重み)に基づいて最適な符号木を構築するための手法です。基本的な構築手順は以下の通りです。 初期化：n個の初期ハフマン木を用意します。それぞれの木は単一の葉ノードからなり、これらn個の木を、重み(出現頻度)順に管理できる優先度付きキュー(プライオリティキュー)に格納します。 結合：キューから重みが最小の2つの木を取り出します。この2つの木を子として持つ新しい木を作成し、その根(ルート)の重みは2つの子の木の重みの合計とします。 再登録：作成した新しい木を優先度付きキューに戻します。 反復：手順2〜3を、すべての部分ハフマン木が1本の

高さ・深さ制限付きハフマンツリーとは 高さ（深さ）に制限を設けたハフマンツリーの構成図は、下図のとおりです。 木の深さの制限は一見単純な問題に思われますが、実際のハフマン符号化の実装においては、多くの場合に対処すべき重要な課題となります。 標準的なハフマン構築には深さの制限がない 標準的なハフマン木の構築アルゴリズムは、木の高さや深さを一切制限しません。仮に深さを制限すると、「最適（オプティマル）」な符号 rather ではなくなるためです。ただし、ハフマン木の最大深度はフィボナッチ数列によって理論的な上限が定められており、際限なく深くなることはありません。それでも、実用上望まれる深さを大

不等コスト記号に対する最適な接頭辞符号の問題 不等な文字コストを持つ場合の最適な接頭辞自由符号（プレフィックスフリーコード）を求める問題とは、コスト（長さ）がそれぞれ α と β（ただし α ≤ β）である2種類の記号からなる符号化アルファベットを用いて、総コスト最小の接頭辞自由符号を計算する問題です。ここでは、二分木の場合に限定して考察します。 この符号は、ハフマン符号化問題の解がハフマン木によって表されるのと同じように、「偏り木（lopsided tree／ロプサイドツリー）」として表現されます。しかしながら、構造上の類似性にもかかわらず、文字コストが不等なケースは古典的なハフマン問題より

バケット化とは何かバケット化（Bucketing）は、ハッシュテーブルを構築する際に用いられる手法の一つです。通常のハッシュテーブルが1次元配列で構成されるのに対し、バケット化では2次元配列として実装します。配列の各エントリには、定数 M 個の要素を格納できる領域（バケット）が確保されます。ここで注意すべき点は、M はデータ量ではなく、あくまで各バケットに格納できる要素数を決める固定値であるということです。イメージとしては、1つの住所（ハッシュ値）に対応する「引き出し」の中に、複数のデータをまとめて収納する形になります。同じハッシュ値にマッピングされたデータ同士は、同一のバケット内で連結リスト

長方形データとは多変量の横断的データ(時系列データや反復測定データではないもの)は、一般に「長方形データ」として表現されます。これは、各列が変数(特徴量)を、各行がケースまたはレコードを表す形式のデータです。1. 点ベースのデータ構造による表現最初の手法は、長方形データを高次元の点データへマッピングし、グリッドファイル、PR四分木、点四分木、k-d木といった点ベースのデータ構造を利用する方法です。長方形を四次元の点へ変換する技法には複数の方式があります。例えば、対角にある2つの頂点のx座標・y座標を用いる方法や、1つの頂点の座標と幅・高さを組み合わせる方法などが挙げられます。ただし、この点ベー

平面直線グラフ（PSLG）の定義計算幾何学において、平面直線グラフ（PSLG：Planar Straight-Line Graph）とは、平面グラフを平面上に埋め込み、そのすべての辺を直線分として表現したグラフ構造を指します。「ストレートライン平面グラフ」「平面ストレートライングラフ」などと呼ばれることもあります。ファーリーの定理（Fárys theorem、1948年）によれば、あらゆる平面グラフは必ずこの種の埋め込みを持つことが証明されており、これがPSLGの理論的な基盤となっています。平面分割としてのPSLG計算幾何学の文脈では、PSLGはしばしば「平面分割（planar subdivi