コンテンツにスキップ
ドキュメント
リファレンス
技術ホワイトペーパー

技術ホワイトペーパー

はじめに

tzf は当初、座標をタイムゾーンに変換するバックエンドサービス向けに設計されました。主な対象は地理サービスと気象サービスです。

プロジェクトの発展に伴い、Python サポートの追加が必要になりました。当時の timezonefinder は境界付近の検索速度がプロジェクトの要件を満たせませんでした。

その結果、tzf (Go)、tzfpy (Python)、tzf-rs (Rust) が順に整備されました。

設計目標は次の通りです：

  • 座標をタイムゾーンに変換する。
  • 性能を優先しつつ、完全精度モードも提供する。
  • 最低でも Go と Python をサポートする。（Rust は PyO3 エコシステムのために開発されました。）
  • バックエンドサービス向けに配布ファイルとバイナリサイズを抑える。

このホワイトペーパーでは、tzf のコア最適化技術を 2 つのカテゴリに分けて解説します：

オフラインデータパイプライン：生の境界データをコンパクトで事前インデックス済みの配布ファイルに変換します：

  1. トポロジー認識簡略化（ステージ 1）
  2. 共有エッジ重複排除（ステージ 2）
  3. Polyline エンコーディング（ステージ 3）

実行時クエリ最適化：クエリ時に検索を高速化します。タイルインデックスとグリッドインデックスはパイプラインがビルド時に埋め込む補助データ構造に依存します：

  1. タイルベースインデックス（FuzzyFinder プレインデックス）
  2. 1°×1° グリッドインデックス
  3. YStripes 空間インデックス

オフラインデータパイプライン

生のタイムゾーン境界データは、Protocol Buffers バイナリ（Timezones 形式）として約 96 MB から始まります。 2 つの並行オフラインパイプラインが 3 つの配布ファイルを生成します（ファイル名には combined-with-oceans. プレフィックスが付きます）：

完全精度パイプライン：重複排除 + 圧縮のみ、簡略化なし：

生 .bin                     (96 MB,   Timezones)
  ↓ 共有エッジ重複排除
.topo.bin                   (54.6 MB, TopoTimezones,              −43%)
  ↓ Polyline デルタエンコーディング
.compress.topo.bin          (17 MB,   CompressedTopoTimezones,    −82%)  ← 埋め込み（完全版）

ライトパイプライン：トポロジー認識簡略化 + 重複排除 + 圧縮、プレインデックス分岐付き：

生 .bin                               (96 MB,   Timezones)
  ↓ トポロジー認識 D-P 簡略化
.topology.bin                          (12.5 MB, Timezones,              −87%)
  ├─→ preindextzpb → .topology.preindex.bin  (2.0 MB)  ← 埋め込み（プレインデックス）
  ↓ 共有エッジ重複排除
.topology.topo.bin                     (10.0 MB, TopoTimezones,          −90%)
  ↓ Polyline デルタエンコーディング
.topology.compress.topo.bin            ( 5.4 MB, CompressedTopoTimezones,−94%)  ← 埋め込み（ライト版）

最終的な配布ファイル：

ファイル形式サイズ
combined-with-oceans.compress.topo.binCompressedTopoTimezones約 17 MB
combined-with-oceans.topology.compress.topo.binCompressedTopoTimezones約 5.4 MB
combined-with-oceans.topology.preindex.binPreindexTimezones約 2 MB

完全精度データセットは約 96 MB（生 protobuf）から約 17 MB に縮小されました。このサイズなら、tzf-rs は手動ファイルダウンロードを不要にし、オプションの Cargo feature として提供できます。

これらのファイルは ringsaturn/tzf-dist 経由で配布されます。

ステージ 1：トポロジー認識簡略化

背景：ポリゴンごとのアプローチとその限界

生の GeoJSON ポリゴンデータはまず Protocol Buffers を使用してバイナリエンコーディングに変換されます。スキーマはシンプルです：

message Point {
  float lng = 1;
  float lat = 2;
}

message Polygon {
  repeated Point points = 1;
  repeated Polygon holes = 2;
}

message Timezone {
  repeated Polygon polygons = 1;
  string name = 2;
}

message Timezones {
  repeated Timezone timezones = 1;
}

この変換後も、データをメモリに読み込むには約 900 MB 必要です。次のステップは Ramer-Douglas-Peucker (RDP) アルゴリズム を適用して各ポリゴンのポイント数を削減することです：

パラメトリック RDP 実装における epsilon の変化の効果、出典

パラメトリック RDP 実装における epsilon の変化の効果、出典

各ポリゴンに RDP を独立して適用することで、データは約 11 MB に縮小されました。しかし、この単純なアプローチには根本的な正確性の問題がありました （tzf#183）：隣接するタイムゾーンポリゴンはエッジを共有していますが、各ポリゴンは独立して簡略化されます。D-P アルゴリズムが共有境界の両側から異なる中間ポイントを削除するため、2 つのポリゴンはわずかに異なるエッジ形状になり、生データでは見えないギャップと重複が簡略化後に生じます。DefaultFinder の ±0.02° 空間許容フォールバックは、この問題への一時的な回避策でした。データ層で問題を修正するものではありません。

トポロジー認識アプローチ

修正は、RDP 簡略化をトポロジー認識パイプラインに統合し、すべての隣接ポリゴンにわたって共有境界を一貫して処理することです。簡略化の前に、すべてのポリゴンリングに対してトポロジーグラフが構築されます：

  1. 巻き方向の正規化（外環は CCW、穴は CW）により、隣接するリングが反対方向で共有境界を走査するようにします。これにより逆エッジマッチングが安定します。
  2. ゼロ長エッジの削除（一部のリングには共有エッジ検出を妨げる重複隣接頂点が含まれます）。
  3. T 字路頂点のスナップ：トポロジーノードが隣接エッジの内部にある場合、分析の前に新しい頂点として挿入します。
  4. 正準キーハッシュによる共有エッジの検出。各セグメントを分類します：
    • 固定：3 つ以上のリングが交わる頂点。これらのアンカーポイントは移動不可。
    • 共有セグメント内部：簡略化可能ですが、一度だけ処理します。すべてのパートナーリングが同じ簡略化結果を再利用します。
    • 非共有：独立して簡略化（海岸線、独立境界）。
  5. 飛地リング（内部タイムゾーンの外環と形状が等しい穴）は特別に処理： 両方のパートナーリングが辞書順最小頂点（正準スタート）に回転し、共有簡略化キャッシュに入り、固定頂点なしで同一の出力を保証します。
  6. フォールバック：簡略化後に一意のポイントが 3 未満になる、ゼロ長エッジが生じる、または（小リング ≤ 100 点で）自己交差するリングは、元の未修正の入力リングに戻します。

このトポロジー認識アプローチは 2026 年春に完了しました。その実装はinternal/topology/README.md に文書化されています。

結果：ポイント数は 86% 削減され（8 M → 1.09 M ポイント）、共有境界はトポロジー的に一貫します。ギャップなし、意図しない重複なし。

ステージ 2：共有エッジ重複排除

簡略化後も、長い共有境界セグメントはファイル内に 2 回現れます。隣接するタイムゾーンリングごとに 1 回ずつです。deduplicatetzpb ツールはTimezones バイナリを TopoTimezones 形式に変換し、各共有セグメントを一度だけ保存します：

  • グローバルな SharedEdge ライブラリが各長共有境界セグメントを ID でインデックスします。
  • 各リングは RingSegment エントリのシーケンスになります：短いインラインポイントシーケンス（≤ 10 点）または SharedEdge ID への順方向/逆方向参照。

巻き方向の正規化は、簡略化前と同じ理由で重複排除の前にも実行する必要があります： 隣接するリングが共有境界を反対方向に走査する場合にのみ、重複排除がそれらを同じエッジとして認識します （争議領域の同方向重複として分類されるケースを避けられます）。

結果（簡略化データ）：約 20% のさらなるサイズ削減 （12.5 MB → 10.0 MB）。TopoTimezones 形式は完全なポリゴンにクリーンに往復変換できるため、下流ツールにとって有用な交換形式です。

ステージ 3：Polyline エンコーディング

最後のオフラインステージでは、Google Maps の Encoded Polyline アルゴリズムを適用してTopoTimezones に保存された座標シーケンスを圧縮します。地理的に連続するポイントは小さなデルタを持つため、デルタ + zig-zag エンコーディングが簡略化・重複排除済みデータに対して約 45% の追加圧縮を達成します。

共有エッジポイントシーケンスとインラインセグメントポイントはデルタエンコードされ、エッジ ID 参照（int32 順方向/逆方向参照）はそのまま通過します。

結果：10.0 MB → 5.4 MB（CompressedTopoTimezones）、生の 96 MB ソースから累計 94% の削減。

実行時クエリ最適化

タイルベースインデックス

単純な Ray Casting アプローチは O(n²) 時間で動作し、高並行性バックエンドサービスには不適切です。空間 R-tree を検討しましたが、グローバルタイムゾーンの数が少なく、面積分布が不均一であるため、パフォーマンス向上はごくわずかでした。

そこで、気象データサービスで使用される地図タイル形式に着想を得たタイルベースのインデックス方式を採用しました。各タイルは特定のズームレベルで四辺形領域を定義します：

┌───────────┬───────────┬───────────┐
│           │           │           │
│           │           │           │
│ x-1,y-1,z │ x+0,y-1,z │ x+1,y-1,z │
│           │           │           │
│           │           │           │
├───────────┼───────────┼───────────┤
│           │           │           │
│           │           │           │
│ x-1,y+0,z │ x+0,y+0,z │ x+1,y+0,z │
│           │           │           │
│           │           │           │
├───────────┼───────────┼───────────┤
│           │           │           │
│           │           │           │
│ x-1,y+1,z │ x+0,y+1,z │ x+1,y+1,z │
│           │           │           │
│           │           │           │
└───────────┴───────────┴───────────┘

この四分木ライクなレイアウトにより、親タイルが正確に 4 つの子タイルを含み、ギャップなしの集約が可能です：

タイルベースのタイムゾーンインデックスのデモ。ポリゴンとインデックスを含むライブデモは tzf-web で確認できます

タイルベースのタイムゾーンインデックスのデモ。ポリゴンとインデックスを含むライブデモは tzf-web で確認できます

各タイムゾーンは独立して処理されます。各タイムゾーンについて：

  1. インデックスズームレベル（ズーム 13）でポリゴンに接触するすべてのタイルを生成します。
  2. ポリゴン内に完全に収まるタイルのみを保持します（EnsureInside）。
  3. エッジタイルを削除します。8 つの隣接タイルのいずれかがタイルセットに存在しないタイルが対象です。このステップは 2 回適用され（dropEdgeLayer = 2）、内部境界から 2 層剥がして、ポリゴンエッジ付近のタイルを除外します。
  4. MergeUp で残りのタイルを集約ズームレベル（ズーム 3）にマージし、マージ結果に再度 EnsureInside を適用します。

各タイムゾーンは独立してインデックスされるため、複数のタイムゾーン内に収まるタイルは、すべての関連タイムゾーンのインデックスエントリに現れます。メモリ内のマップはmap[Tile][]string であり、1 つのタイルが複数のタイムゾーン名を返すことができます。これは Asia/Shanghai と Asia/Urumqi のような共有エリアを処理し、それらの重複する内部領域が両方のタイムゾーンのプレインデックスエントリに一致するタイルを生成します。

クエリ時には、最も粗いズーム（3）から最も細かい（13）まで走査し、最初に一致するタイルですべてのタイムゾーン名を返します：

  • 一致するタイルが見つかった場合 → そのタイムゾーンリストを返します（曖昧でない内部タイルは 1 つ、共有エリアのタイルは複数）。
  • 一致するタイルがない場合（境界領域、海岸線、疎なエリア） → プレインデックスは結果なしを返します。

FuzzyFinder はこのプレインデックスのみを使用します。GetTimezoneNames は完全なリストを返し、GetTimezoneName は最初のエントリを返します。未カバーエリアでは推測せずにエラーを返します。呼び出し側が空結果を処理する必要があります。

DefaultFinder はこれを自動的に処理します：最初にタイルプレインデックスを試み、結果が返されない場合はFinder による完全なポリゴン検索にフォールバックします。これにより、すべての座標に対して正確でありながら、大部分の世界都市クエリでプレインデックスの速度を維持します。

タイルプレインデックスはオフラインで独立した .topology.preindex.bin ファイルとして構築され、ライト版の圧縮バイナリと並行してロードされます。

1°×1° グリッドインデックス

tzf v1.2.0 / tzf-rs v1.3.3 以降、CompressedTopoTimezones バイナリは圧縮ステージ末尾に 1°×1° グリッドインデックスを自動的に埋め込みます。地球を 360 × 180 = 64,800 個のセルに分割し、各セルにはバウンディングボックスが交差するタイムゾーンインデックスのソート済みリストが格納されます。少なくとも 1 つのタイムゾーンを含むセルのみが保存され（全世界で約 65,000 から 65,500 個）、配布ファイルのサイズは約 870 KB 増加します。

クエリ時、Finder は O(1) の map 検索により PIP 候補数を ~444 タイムゾーンから通常 1 から 3 個に削減します。セルの候補が 1 つだけで、クエリポイントが日付変更線と極点から離れている場合は、PIP テスト自体をスキップします。グリッドインデックスを含まない旧データファイルは元の全量線形スキャンに透明にフォールバックするため、呼び出し側への API 変更はありません。

twitchax/rtz に着想を得ています。

YStripes インデックス

tzf v1.1.0 (Go) および tzf-rs v1.2.0 (Rust) 以降、ポリゴンレベルのポイントインポリゴンテストは、Josh Baker の tidwall/tg プロジェクトから移植された YStripes 空間インデックスを使用します。

YStripes は、各ポリゴンのエッジを水平ストライプに事前分割することで、単純なレイキャスティングを改善します。クエリポイントに対して、該当するストライプ内のエッジのみがテストされ、完全な空間ツリーのオーバーヘッドなしでポリゴンごとの作業量を大幅に削減します。

これはデフォルトで有効です。無効にする（メモリ制約のある環境など）には、 Rust の FinderOptions を使用します。YStripes を使用すると、DefaultFinder で最新ハードウェア上で単一ランダム都市検索が一貫して 1 µs 未満で動作します。

アルゴリズムの詳細については、作者による説明POLYGON_INDEXING.md を参照してください。

最終更新日
エコシステム