SAXのようなやり方でディスクからのバイナリ検索XML？可能？

Question

アニメーションフレームタイプの速度で特定のタイムスタンプを持つアイテムの（大規模な）XMLファイルを検索する必要があります。

私は最近のプロジェクトで同様のことをしていますが、XMLはメモリに収まるほど小さいため、単純なオブジェクトの配列に解析し、バイナリ検索しました。ブーム！フレームあたり800奇数のタイムスタンプ付きアイテムによる超高速検索。

今回は、XMLファイルのサイズが十分に大きいため、それらを解析するのが愚かなアイデアになる可能性があります（これはiOSのものなので、RAMは限られています）。私の頭の中の解決策は、ファイルからSAXのようなストリーム解析を行うことですが、設定可能なポインタを使用しています。だから私は別のバイナリ検索でファイルの周りのポインタをジャンプすることができます、ファイル内の次の完全なノードを解析し、検索ポインタが次にジャンプする場所を通知するために使用します。

良い理論だと思います。しかし、インターネットを見渡すと、ファイル内に現在の行番号を設定できるSAXパーサーが見つかりませんでした。多くの場合、ステータスとして読み取り専用アクセス権が与えられますが、あまりにも重要な位置設定を許可するものはありません。

です。そのような能力を持つXML解析ライブラリを知っている人はいますか？繰り返しますが、これはiOSの世界なので、C/C++ベースのものは何でもできますが、Obj-Cラッパーがあればボーナスポイントになります。

Answer 1

XMLでは、少なくとも直接行うことはできません。あなたは特定の行番号にジャンプしたいと言ったが、それはXMLが行ベースではないので、あなたを助けないかもしれない。また、XMLを完全に解析する必要があるため、一部のノードのn番目の子に簡単にジャンプできません。

まず、ファイル全体を解析してインデックスを作成します。ジャンプする必要があるノードのそれぞれについて、ファイル内の開始位置（おそらくバイトオフセットとして）を記憶します。 SAX（またはSAXライクな）パーサーを使用してこれを行うことができます。文書全体をメモリに保存する必要はありません。

このようにすると、ファイル全体を1回解析する必要があります（O（n）操作）が、ノードを飛ばしてすぐに解析できます（O（1））。検索実行者。

または、検索するプロパティに基づいてインデックスを作成できます。これを行うと、バイナリ検索全体がメモリ内になり、必要な1つ（または少数）のノードだけを解析することができます。これはさらに高速でなければなりません。