平面のマス目に1番、2番、3番と順番をつけたい。素直にやるなら左上から右へ、行の終わりで次の行へ(行優先)。ただしこの並べ方だと、縦に隣り合う2マスの番号が大きく離れる。256列あれば、真下のマスは256番先だ。

ヒルベルト曲線は、この問題への古典的な答えとされている。1本の線が平面を折り返しながら埋め尽くし、2次元で近いマスは1次元でも近い番号になる。データベースの空間インデックス(地理検索など)や、画像処理の走査順に実際に使われている。

本当に近さは保たれるのか。行優先やZ階数(モートン順)と比べて、どれくらい良いのか。測った。

実験に使ったコードの全文はGitHubに置いています。

3つの並べ方

ヒルベルト曲線は「1歩進むと必ず隣のマスに移る」という性質を持っている。実装が正しいかの確認にもなるので測ったところ、$256 \times 256$ の全65,535歩すべてで移動距離1だった。Z階数のほうは最大256の飛びがある。

曲線が描かれていく様子はこうなる。

近さは保たれるのか

$256 \times 256$ の格子で、2次元で隣り合うすべての画素ペアについて、1次元での番号の差を測った。

並べ方	中央値	平均	最大
ヒルベルト順	1	155.6	54,613
Z階数	2	128.5	21,846
行優先	128	128.5	256

予想と違った。

中央値ではヒルベルトの圧勝だ。1。2次元で隣り合うマスの過半数は、1次元でも隣り合っている。行優先の128とは比べものにならない。

ところが平均は155.6で、行優先の128.5に負けている。最大に至っては54,613対256で、200倍以上の差をつけられている。

理由は曲線の構造にある。ヒルベルト曲線は入れ子のU字で平面を埋めるが、大きなU字の折り返し地点では、隣り合うマスが曲線上で最大級に離れる。そういう場所は数としては少ないが、離れ方が桁違いなので平均を押し上げる。行優先は「常に256」という上限があるかわりに、ほぼ全部が256だ。

つまり両者は「たまに大きく外すが、ほとんどは完璧」対「常にそこそこ外す」という関係にある。平均という1つの数字は、この違いを潰してしまう。

逆向きに見ると、話は変わる

空間インデックスで実際に効くのは逆向きの性質だ。「1次元で連続した範囲を読んだとき、それが2次元で狭い範囲に収まっているか」。ディスクから連続領域を読み出す場面がこれにあたる。

$k$ 個離れた2点	ヒルベルト	Z階数	行優先
1	1.00	1.66	1.99
4	2.12	3.31	7.86
16	4.29	6.57	29.95
64	8.61	12.90	95.91
256	17.24	24.92	1.00

こちらはヒルベルトが一貫して最良だ。$k=64$ では8.61対95.91で、行優先の11分の1に収まる。

$k=256$ で行優先が1.00になっているのは偶然で、格子の幅がちょうど256なので「256個先＝真下のマス」になっただけだ。格子幅を変えればこの行だけ壊れる。都合のいい数字が出たときは、それがパラメータの一致による偶然でないかを疑ったほうがいい。

「次元2」はどこにあるのか

ヒルベルト曲線は空間充填曲線で、フラクタル次元は2とされる。マンデルブロ集合の回と同じbox-countingで測ってみた。

最初の測定では次数を上げるほど次元が0→1→2と上がる、という結果が出た。だがこれはコードの不備だった。曲線の頂点だけを塗っていたので、次数が低いと点線になり、箱が正しく数えられていなかった。線分そのものを塗るように直して測り直した結果がこれだ。

どの次数の曲線も、2つの領域を持っている。

• 箱が曲線の折り返し間隔より大きいとき：傾き2。箱はすべて埋まっていて、曲線は面として振る舞う
• 箱が折り返し間隔より小さいとき：傾き1。箱の中では曲線はただの線分でしかない

そして次数を上げると、折れ曲がる位置が細かいほうへ移動していく。次数6なら折り返し間隔は32画素、そこが境目になる。

「ヒルベルト曲線の次元は2」というのは、この境目を無限に細かいほうへ追いやった極限の話であって、実際に描ける有限の曲線はどれも、十分細かく見れば次元1の折れ線だ。有限の次数で測ると1.00前後にしかならない。

前回のマンデルブロ集合では「細すぎて測れない」だったが、今回は逆で「極限にしか存在しないので、有限のものを測っても出ない」。どちらも理論値が出なかったが、出ない理由は正反対だった。

圧縮では負けた

最後に実用的な確認をした。局所性が保たれるなら、画像をヒルベルト順に並べ替えてから圧縮すると小さくなるはずだ。$256 \times 256$ の画像4種をgzipにかけた。

画像	行優先	Z階数	ヒルベルト順
なめらかな勾配	18,624B	34,899B	32,983B（+77.1%）
ぼかした乱数	23,756B	34,823B	32,022B（+34.8%）
純粋な乱数	65,574B	65,574B	65,574B（±0%）
同心円	19,250B	45,319B	41,798B（+117.1%）

全敗だった。ヒルベルト順に並べ替えると、どの画像でも圧縮後のサイズが大きくなる。

理由はgzip(DEFLATE)の仕組みにある。LZ77は「過去に出た同じ並び」を探して参照に置き換える。行優先で並べた画像は、各行が前の行とよく似ているので、ちょうど256バイト前に長い一致がある。この規則正しい繰り返しがgzipにとって理想的な餌になる。

ヒルベルト順は局所性を保つ代わりに、この周期構造を破壊する。近い画素が近くに来るので値の変化は小さいが、同じ並びが再登場しない。gzipが探しているのは「値が近いこと」ではなく「並びが同じこと」だった。

局所性が高いことと圧縮しやすいことは、別の性質だ。

まとめ

• 2次元で隣り合う画素の1次元距離は、ヒルベルトが中央値1（行優先128）だが、平均155.6・最大54,613で行優先の128.5・256に負ける
• 逆向き(1次元で近い→2次元で近い)ではヒルベルトが一貫して最良。$k=64$ で8.61対95.91
• 次元2は極限の性質。有限の曲線は「粗い箱では傾き2、細かい箱では傾き1」の2領域を持ち、境目は折り返し間隔にある
• ヒルベルト順に並べ替えてgzipすると4種すべてで大きくなった(+34.8%〜+117.1%)。局所性と圧縮率は別物

---

「ヒルベルト曲線は近さを保つ」は正しかった。ただしどの指標で見るかで結論がひっくり返る。中央値なら圧勝、平均なら敗北、最大なら惨敗、逆向きなら圧勝。

自分がどれを見るべきかは、何に使うかで決まる。連続した領域を読み出すなら逆向きの指標が効くので、空間インデックスにヒルベルト曲線を使うのは正しい。だが「最悪でも何マス以内」を保証したいなら、行優先の256という上限のほうが価値がある。

厄介なのは、指標を選ぶ前に結論を知ってしまっていたことだ。私は「ヒルベルト曲線は優れている」と聞いた状態で測り始めた。もし最初に平均だけを見ていたら、たぶん「実装を間違えた」と思ってコードを疑っていた。

数字が期待と違ったとき、まず疑うべきなのは自分の測り方だ。だがそのとき、期待のほうを疑う準備もしておかないと、正しい測定を捨ててしまう。

• 実践記
• フラクタル・カオス
• アルゴリズム

関連記事

• マンデルブロ集合の境界は「2次元」だと証明されている。同じコードで測ったら1.09にしかならなかった
• 3つの国の国境が、どこを取っても3か国すべてに接している。ニュートン法の吸引域で「和田の湖」を実測した
• 次元の呪いを実測したら、82倍あった最近傍と最遠点の距離比が300次元で1.21倍まで潰れた

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。