タイル画像のアーカイブを zip から独自ファイル形式に変更して、国土地理院の標準地図および 航空地図(オルト地図)で動作確認できた。
zipよりもはるかに高性能であり、タイルの更新、追加にも対応している。
ファイル構造は先頭に全体管理部、次に、エントリ管理部、そのあとにエントリ本体を続ける。 エントリ管理部には更新や追加のための予備エントリを含む。
対象はタイル画像だけではなく、OSM(OpenStreetMap)地図のレンダリングに使うOSMバイナリレコードも 同じファイル形式とする(地図アプリでの追加/更新はないため、予備エントリはない)。
zip から 独自方式の切り替えは期間をかけて、少しずつ行うが、極力、全体を考えた仕様としたい。
当面、全体管理部の大きさを 64バイトとしておく。項目追加のときは予備を使う。
version ８バイト iniEntries ４バイト（初期エントリ数） curEntries ４バイト（現在エントリ数） maxEntries ４バイト（全エントリ数） unused ４４バイト（予備）
初期およびファイル再構築時には iniEntries と curEntries は同じで、 先頭から iniEnries まではエントリは id の昇順となっている。
更新または新規タイルの追加があるごとに curEntries は +1 される。 iniEntries から curEntries までのエントリは登録順であり、id 順とはなっていない。
予備エントリ数（maxEntries－curEntries）は、少なくなったら、警告を出す。
再構築処理の実行は数か月～数年に一度でよいので、自動起動とはしない。 バックアップをとってマニュアルで行う。
curEntries は現在は 10万未満、ファイルサイズは 4GB未満であるが、 その 10倍程度までを想定している。
初期または再構築時の予備 (maxEntries - curEntries) は１万エントリとする。 したがって、iniEntries に比べて予備エントリはごく小さい。
エントリ管理部はエントリ毎に次の 16バイトとする。
id（zoom, x, y） ８バイト（zoom ２バイト、x ３バイト、y ３バイト） offset ８バイト
予備エントリには何も値は設定しなくてもよいが、 id は zoom=30, x=0, y=0 とする。 offset は、-1 としておく。
OSMバイナリレコードの場合は offset は４バイト範囲であるが、 タイル画像の場合は数10GB まで想定しているため、offset は８バイトとした。
メモリ上では id の昇順に並び替え、バイナリ検索を使う。
zoom は１バイトで十分なため、id ７バイト、offset ５バイトとすれば、 １６バイトを１２バイトに縮小でき、メモリ使用量が削減できる。
しかし、４バイトのメモリ節約よりも分かりやすさから、８バイトにしておく。
全体管理部およびエントリ管理部はメモリに読み込む。
エントリ管理部は byte配列として curEntries までを読み込む。 iniEntries から curEntries までについては、１エントリ分(８バイトｘ２)ずつ、 id、offset を long値に変換して、HashMap<Long, Long> に登録する。 id をキー、offset を値とする。この追加分の中でもタイル更新があった場合、 id が同じことがあるが、その場合、後の方ほど新しいため、offset を書き換える。
地図表示での検索では、そのタイルの id をまず、この HashMap で検索する。 見つかれば、その offset を返す。これが最新のタイル画像を指している。
HashMapに存在しなかった場合、iniEntries までの byte配列から探す。 バイナリ検索の比較対象となったエントリの id、offset について、byte配列から long値を取り出す必要がある。
20～30エントリについてこの変換が必要になるかもしれないが、 地図アプリ起動時に 10～100万エントリについて、byte配列を long配列に変換することに比べれば、 少ない回数(変換時間)で済むであろう。
バイナリ検索では同じエントリとの id との比較が起きるため、アプリ起動後、比較のために得た (id、offset）ペアは、バイナリ検索用の HashMap に登録しておく。キーは id ではなく、 0 から iniEntries-1 までのインデクス(Integer)であり、値は Entry（id、offsetがメンバー変数）または または要素が二つ(id、offset)の long配列である。この HashMapを使えば、 byte配列から long 値への変換回数は最適化され、総変換回数は iniEntries 以下となるため、 起動時に全エントリ(iniEntries)の id、offset を long値に変換するより効率的である。
しかし、最初はバイナリ検索用のHashMapは使わず、それで十分なパフォーマンスが得られればそれでよい。 100万エントリの場合、比較回数は最悪で 20回である。合計40回の byte配列(8バイト)からlong値への変換 時間が微々たるものであれば、HashMapは不要である。
各エントリには次のローカルヘッダ（44バイト）を置く。
id（zoom, x, y） ８バイト エントリデータの最終更新時刻 ８バイト (ミリ秒単位の UNIXタイム) エントリデータの最終参照時刻 ８バイト (ミリ秒単位の UNIXタイム) CRC32 チェックサム ８バイト 参照回数 ４バイト 更新所要時間 ４バイト（レンダリングまたはダウンロード時間、単位：ミリ秒） エントリデータの長さ ４バイト（単位：バイト）
id はエントリ管理部にもあるが、例えば、エントリ管理部を使わず、エントリ本体部だけをスキャンすることに 全エントリを階層ディレクトリ構造で展開できるようにするためものである。
それほどの時刻精度はいらないので時刻は４バイトでもいいが、プログラムが分かりやすい。
CRC32は４バイトで表せるが、Javaには unsigned int がないため、long の方がプログラムが シンプルですむ。
ヘッダの 44バイトが全体に占める比率は微々たるもののため、以上のように決めた。
国土地理院地図の場合、センターに更新時刻を問い合わせ、保存データの時間より 新しければ、ダウンロードするが、ある地域の一部が更新されただけで、実際には更新されて いないことが多い。これをチェックサムで判定する。変更がないときは、 最終更新時刻だけを書き換える。
更新があった場合、古いエントリはそのまま残し、新しいデータを予備エリアに追加する。 予備エリアがたりなくなったとき、古いタイルを削除し、改めて予備エリアを確保する。 新規追加タイル分だけ、ファイルサイズは大きくなる。
この再構築時に、最終参照時刻が古く、参照回数が極めて小さいものは除外する。 一般にサイズが小さいタイルはダウンロードやレンダリングに時間がかからないため 必要が生じたときダウンロード/レンダリングすればよい。
エントリ管理部に更新された古い情報もあるため、 最新データだけではなく、過去のデータも得ることができる。
タイル更新の際、旧エントリ本体および旧エントリ管理データはそのまま残し、 新しいエントリを追加登録する。
更新による追加が起きたアーカイブファイルを読み込もうとしたとき、 同じ id をもつエントリが二つ以上存在することに注意がいる。
地図アプリでは追加分は HashMap で管理する。
現在の総エントリ数は 20万程度である。 現在は全アーカイブファイルのエントリ管理部と全体管理部を メモリに読み込み、常駐させることができる。
200万エントリでも必要メモリは 32MB であるから問題ない。 1000万タイルとしも 180MB である。 しかし、一つのアーカイブファイルのサイズが大きくなりすぎる。
100万～200万タイルになった場合、 zoom 別のアーカイブファイルとする。
タイル画像については、Tile.Source の順序数をindexとした配列で 管理するのが分かりやすいであろう。
レンダリング用はこれとは別の管理方法をとる。
C言語による実装例[1]を下に示す。これは int配列での検索である。 タイル管理部でのバイナリ検索は int が byte に変わる。また、key は long であり、 binary_search の戻り値も long である。 16バイト単位で最初の８バイトが id、次の８バイトが offset である。 比較の対象は最初の８バイトである。これを long 値に変換して比較する。 比較の過程では後ろの８バイトのlong変換はいらない。 最終的に key に一致する id が見つかった場合、後続のoffset(８バイト)を long値に変換してこの値を戻り値とする。
一致するものが見つからなかったときは、-1 を返す。 現在のファイル構造では offset が 0 になることはないので、0 を返してもよい。
int binary_search(int[] ary, int key, int imin, int imax) {
if (imax < imin) {
return KEY_NOT_FOUND;
} else {
int imid = imin + (imax - imin)/2;
if (ary[imid] > key) {
return binary_search(ary, key, imin, imid - 1);
} else if (ary[imid] < key) {
return binary_search(ary, key, imid + 1, imax);
} else {
return imid;
}
}
}
byte配列に対するバイナリ探索は次のようになるであろう。 このプログラムを実装してみる。
まずは更新や新規タイルによるエントリ追加はない状態で試す。
imin = 0、imax = iniEnries - 1 が探索のスタートである。
long binary_search(byte[] ary, long key, int imin, int imax) {
if (imax < imin) {
return -1;
} else {
int imid = imin + (imax - imin)/2;
long vmid = bytesToLong(ary, imid*16);
if (vmid > key) {
return binary_search(ary, key, imin, imid - 1);
} else if (vmid < key) {
return binary_search(ary, key, imid + 1, imax);
} else {
//return imid;
return bytesToLong(ary, imid*16 + 8);
}
}
}
public long bytesToLong(byte[] bytes, int off) {
return ((long) (bytes[off] & 0xFF) << 56) |
((long) (bytes[off + 1] & 0xFF) << 48) |
((long) (bytes[off + 2] & 0xFF) << 40) |
((long) (bytes[off + 3] & 0xFF) << 32) |
((long) (bytes[off + 4] & 0xFF) << 24) |
((long) (bytes[off + 5] & 0xFF) << 16) |
((long) (bytes[off + 6] & 0xFF) << 8) |
((long) (bytes[off + 7] & 0xFF));
}
パソコン側にある階層ディレクトリ下のタイル群をアーカイブファイルにまとめるプログラムとしては 全体管理部だけが少し変更された。
スマホ側のプログラムの修正は大きかったが、ひとまず動いた。細部ではバグが残っているかもしれない。
まず、アプリ起動時のエントリ管理部の読み込み時間は大幅に短縮された。gsi.arc は 5mS、ort.arc は 3mS となった。エントリ追加により、読み込み時間は多少増えるが、エントリ数が10倍になっても十分に小さい値で済む だろう。
次にバイナリ検索時間を測定する。 結果は殆どが 0mS、時たま 1mS であった。タイル読み込み時間としても大抵は 10mS 未満となった。 よって、十二分な速さと言える。
少し動かしてから、OSMタイルアーカイブも zip から arc に変更する。
タイル更新があった場合、前のデータはそのまま残し、新しいデータを追加するため、月日がたてば無駄が増える。
無駄を除いてアーカイブファイルを作り変える方法を考える。
再構築では現在のアーカイブファイルはそのまま残し、新しいアーカイブファイルを作る。 再構築中はこのアーカイブの使用は禁止する。例えば、OSM地図を表示しているときに国土地理院地図のアーカイブを再構築する。
メモリ上では新規または再構築(スタート)後に追加されたエントリは HashMap で管理しているが、再構築ではこの HashMap を利用する。 スタート時の iniEntriesタイル をこの HashMap に追加登録する。その id が既に登録済みであれば、古いデータであるため、 offset の登録(書き換え)は行わない。
新しいアーカイブファイルの拡張子は tmp としておく。
すべての登録が終わったら、そのエントリ数が新しい iniEntries になる。*.tmp に全体管理部の書き込みを行う。
HashMapのキーは id、値は offset である。class Entry { long id; long offset; } として、 HashMap から Entry[] entries; を作る。この配列を id の昇順にソートする。
(id、offset)を順に *.tmp に書き込む。その後ろが予備エントリ管理部となる。このデータは読み込むことはないが、 zoom=30, x=0, y=0 としての id および offset = -1 を書き込んでおく。そうすれば、maxEntries がすべて id の昇順となる。
そのあとにローカルヘッダ、エントリデータを続けるが、HashMap から id に対応する offset を取り出し、元の *.arc から ローカルヘッダとエントリデータを読み出し、それをそのまま、*.tmp に追加書き込みを行えばよい。
そのあと、*.arc を *.bak、*.tmp を *.arc に変更して、再構築処理終了となる。 *.bak よりも日付を入れて、例えば *20260329.arc として、しばらくは保存した方がいいだろう。
以上のように、再構築プログラムは簡単であり、実行時間も短いと思われる。
再構築されたアーカイブのエントリのサイズにバグがあるようである。
エントリ offset が間違えているようである。並び替え後にoffset を算出して Entry#offset に設定する処理が漏れている。
ひとまず、完成した。gsi.arc 約6.5万エントリ、1.2GB の場合、実行時間は約１分となった。