タイル画像のアーカイブを zip から独自ファイル形式に変更して、国土地理院の標準地図および 航空地図(オルト地図)で動作確認できた。
zipよりもはるかに高性能であり、タイルの更新、追加にも対応している。
ファイル構造は先頭に全体管理部、次に、エントリ管理部、そのあとにエントリ本体を続ける。 エントリ管理部には更新や追加のための予備エントリを含む。
対象はタイル画像だけではなく、OSM(OpenStreetMap)地図のレンダリングに使うOSMバイナリレコードも 同じファイル形式とする(地図アプリでの追加/更新はないため、予備エントリはない)。
zip から 独自方式の切り替えは期間をかけて、少しずつ行うが、極力、全体を考えた仕様としたい。
当面、全体管理部の大きさを 64バイトとしておく。項目追加のときは予備を使う。
version ８バイト inUseEntries ４バイト（有効エントリ数） nEntries ４バイト（全エントリ数） unused ４８バイト（予備）
予備エントリ数（全エントリ数－有効エントリ数）は定期的にチェックして、 少なくなったら、警告する。
再構築処理の実行は数か月～数年に一度でよいので、自動起動とはしない。 バックアップをとってマニュアルで行う。
エントリ管理部はエントリ毎に次の 16バイトとする。
id（zoom, x, y） ８バイト（zoom ２バイト、x ３バイト、y ３バイト） offset ８バイト
予備エントリの場合 id は zoom=30, x=0, y=0 とする。 offset は何でもいいが、-1 としておく。
予備エントリの zoom は使われている zoom の最大値（現在は 21）よりおおきければ よい。
ファイル上ではエントリ(タイル画像)更新により、同じ id が存在するが、メモリ上では、 前からあるエントリの offset を更新することにより、同じ id が存在することはない。 また、エントリ追加では id 順に並び替えるため、ファイル上の並びとは異なる。
OSMバイナリレコードの場合は offset は４バイト範囲であるが、 タイル画像の場合は数10GB まで想定しているため、offset は８バイトとした。
メモリ上では id の昇順に並び替え、バイナリ検索を使う。
zoom は１バイトで十分なため、id ７バイト、offset ５バイトとすれば、 １６バイトを１２バイトに縮小でき、メモリ使用量が削減できる。
しかし、バイナリ検索プログラムを自作しなければならない。 標準APIですませるため、シンプルにしておく。
各エントリには次のローカルヘッダ（44バイト）を置く。
id（zoom, x, y） ８バイト エントリデータの最終更新時刻 ８バイト (ミリ秒単位の UNIXタイム) エントリデータの最終参照時刻 ８バイト (ミリ秒単位の UNIXタイム) CRC32 チェックサム ８バイト 参照回数 ４バイト 更新所要時間 ４バイト（レンダリングまたはダウンロード時間、単位：ミリ秒） エントリデータの長さ ４バイト（単位：バイト）
id はエントリ管理部にもあるが、例えば、エントリ管理部を使わず、エントリ本体部だけをスキャンすることに 全エントリを階層ディレクトリ構造で展開できるようにするためものである。
それほどの時刻精度はいらないので時刻は４バイトでもいいが、プログラムが分かりやすい。
CRC32は４バイトで表せるが、Javaには unsigned int がないため、long の方がプログラムが シンプルですむ。
ヘッダの 44バイトが全体に占める比率は微々たるもののため、以上のように決めた。
国土地理院地図の場合、センターに更新時刻を問い合わせ、保存データの時間より 新しければ、ダウンロードするが、ある地域の一部が更新されただけで、実際には更新されて いないことが多い。これをチェックサムで判定する。変更がないときは、 最終更新時刻だけを書き換える。
更新があった場合、古いエントリはそのまま残し、新しいデータを予備エリアに追加する。 予備エリアがたりなくなったとき、古いタイルを削除し、改めて予備エリアを確保する。 新規追加タイル分だけ、ファイルサイズは大きくなる。
この再構築時に、最終参照時刻が古く、参照回数が極めて小さいものは除外する。 一般にサイズが小さいタイルはダウンロードやレンダリングに時間がかからないため 必要が生じたときダウンロード/レンダリングすればよい。
エントリ管理部に更新された古い情報もあるため、 最新データだけではなく、過去のデータも得ることができる。
タイル更新の際、旧エントリ本体および旧エントリ管理データはそのまま残し、 新しいエントリを追加登録する。
更新による追加が起きたアーカイブファイルを読み込もうとしたとき、 同じ id をもつエントリが二つ以上存在することに注意がいる。
そのまま読み込んでソートしてバイナリ検索を行うと、最新エントリの位置(index)が返される とは限らない。
旧エントリは無視して最新エントリだけをエントリ配列に読み込む必要がある。 エントリ配列の後部は予備のため、どのくらい重複があるか分からなくても配列は作成できる。 つまり、配列のサイズはファイル上のサイズと同じでよい。
エントリ配列に登録する際、id をキー、配列の index を値として HashMap に登録しておく。 登録前にこの HashMap を使って、既に、この id が登録済みかを調べる。 もし、登録済みであれば、後にある方が新しいため、エントリ配列に登録されているエントリの offset を新しいものに変更する。 HashMap に登録がなければ、エントリ配列に当該エントリ HashMap に id、配列index を登録する。
全てのエントリを登録すれば後は予備エントリとする。これでソートすれば、バイナリ検索が使える。
現在の総エントリ数は 20万程度である。 現在は全アーカイブファイルのエントリ管理部と全体管理部を メモリに読み込み、常駐させることができる。
200万エントリでも必要メモリは 32MB であるから問題ない。 1000万タイルとしも 180MB である。 しかし、一つのアーカイブファイルのサイズが大きくなりすぎる。
100万～200万タイルになった場合、 zoom 別のアーカイブファイルとする。
タイル画像については、Tile.Source の順序数をindexとした配列で 管理するのが分かりやすいであろう。
レンダリング用はこれとは別の管理方法をとる。
まず国土地理院地図のみこのアーカイブファイルを使うようにした。
zipよりも各段に速い。
現在はアーカイブファイルのタイル数は 10万未満である。 個人使用では日本全土をくまなく表示するわけではないので、最終的な想定タイル数は精々数100万タイルである。 １、２度参照しても、その後長期間参照しないタイルは破棄する。
所要メモリは 100万タイル当たり 18MB であるから、その点での問題はない。
気がかりはタイル管理部の読み込みに要する時間である。
現在の測定結果は以下の通りである。現状では問題ないが、保存タイル数が５倍、10倍に増えると 立ち上がりに時間がかかる。
gsi.arc ファイルサイズ 1.2GB gsi.arc タイル数 75000 （概数） byte配列読み込み時間 3mS long配列に変換するまで 345mS Entry配列にしてソート完了まで 575mS
byte配列として読み込む時間は極めて短い。同じファイルで 28mS かかったこともある。
long配列に変換するのにも驚くほど大きな時間がかかる。 Javaのせいである。C/C++であれば、byte配列をそのまま long配列としてとらえることができる。
Entry配列にするとき、id の重複を除去するために、HashMap を使っている。 重複がないならば、この時間は短縮できる。しかし、long配列への変換時間が大きいので、 全体としては大幅な時間短縮とならない。
スマホの場合、通常、アプリは動かしたままであるから、起動時間はさほど問題ではないが、 なるべく、２、３秒以内に収めたい。
地図アプリを終了させるとき、タイルキャッシュにあるタイルについて、 id と offset のペアを配列として保存しておく。
地図アプリ起動時はこの情報を使えば、直ちに地図を表示できる。
(src, zoom, x, y, offset)の参照履歴を残せば、タイル管理部を読み込まず、即座に表示できるタイルを増やせる。
いずれにせよ、タイル管理部読み込み時間短縮のためにプログラムを複雑化させるのはさけたい。
最初あるいは再構成後のアーカイブファイルではエントリは id の昇順とすることができる。 追加や更新分は除けば、byte配列のままで、バイナリ検索が可能である。 比較の都度、８バイトを long に変換する必要があるが、比較回数が限られているため、検索時間はさほど大きくはならないであろう。
アプリ起動後、Entry配列の準備が完了するまでとしては使えるだろう。 バイナリ検索は自前となるが、それほど難しいものではない。
メモリ上では Entry配列は id の昇順を維持している。アーカイブファイルで維持する場合、挿入位置から末尾までも byte配列に読み込み 16バイト後ろにずらした位置にこれを書き込み、16バイトの空きを作る。ここに、新しい (id、offset）ペアを書き込む。
アーカイブファイルが今の10倍になったとすれば、管理部の修正に 100mS程度かかるであろう。エントリ本体の書き込み時間よりも はるかに大きくなってしまう。しかし、ダウンロードやレンダリングには時間がかかるため、全体としては許容範囲である。
メモリ上には管理部をバイト配列として読み込むだけとする。long配列への変換は行わない。また、Entry配列も持たない。
byte配列を使ってバイナリ検索を行う。
全体としてプログラムは分かりやすいだろう。ただ、アーカイブファイルの管理部でエントリ挿入のために byte配列の読み書きに時間がかかるのが気がかりである。10万タイルでは問題はないとしても、100万タイルで大丈夫か確信が持てない。 時間だけの問題ではなく、やはり、大きなサイズの書き込みを頻繁には行いたくない。