3

この質問は、私が与えられた宿題から来ています。ストレージ システムは、次の 3 つのフォーマットのいずれかをベースにすることができます。

DD MM SS.S

DD MM.MMM

DD.DDDDD

できるだけ少ないバイト数を使用して、格納できるデータの量を最大化する必要があります。

私の解決策は、最初の形式に基づいています。緯度には 3 バイトを使用しました。DD には 8 ビット (-90 から 90)、MM には 6 ビット (0 から 59)、SS には 10 ビット (0 から 59.9) です。次に、経度に 25 ビットを使用しました。DDD に 9 ビット (-180 から 180)、MM に 6 ビット、SS.S. に 10 ビットです。このソリューションはバイト境界にうまく収まりませんが、次の読み取り値は前の読み取り値の直後に格納でき、8 つの読み取り値は 49 バイトしか使用しないと考えました。

他の人が思いつく方法に興味があります。このデータを保存するためのより効率的な方法はありますか? 注意として、オフセットベースのストレージを検討しましたが、問題は読み取り間で値がどれだけ変化するかを示していないため、変更が可能であると想定しています.

4

3 に答える 3

2

提案された方法は最適ではありません。10 ビット (1024 の可能な値) を使用して、範囲 (0..599) の値を格納しています。これはスペースの無駄です。

緯度に 3 バイトを使用する場合は、範囲 [0, 2^24-1] を範囲 [-90, 90] にマップする必要があります。したがって、2^24 の値はそれぞれ 180/2^24 度、つまり 0.086 秒を表します。

0.1 秒の精度だけが必要な場合は、緯度に 23 ビット、経度に 24 ビットが必要になります (0.077 秒の精度が得られます)。これは、49 ビットではなく合計 47 ビットであり、精度が向上します。

もっとうまくやれるだろうか？

0.1 秒の精度に必要な正確なビット数は、log2(180*60*60*10 * 360*60*60*10) < 46.256 です。つまり、46256 ビット (5782 バイト) を使用して 1000 の (緯度、経度) ペアを格納できますが、関連する数学では非常に大きな整数を処理する必要があります。

もっとうまくやれるだろうか？

場合によります。データ セットに集中がある場合は、いくつかのポイントとこれらのポイントからの相対距離のみを、より少ないビット数で保存できます。クラスタリング アルゴリズムを使用する必要があります。

于 2011-02-18T20:15:12.620 に答える
1

既存の技術へのこだわり:

DD.DDDDD データのみを格納するために半精度 浮動小数点数を使用した場合、スペース効率は大幅に向上しますが、15 の指数バイアスを受け入れる必要があります。つまり、格納された座標は正確ではない可能性があります。 、ただし元の値からのオフセットにあります。

これは、基本的に浮動小数点数の保存方法によるものです。正規化された有効桁数に指数を掛けて、単一の値を保存するのではなく (整数のように、ソリューションの数値を計算する方法)、数値を生成します。 ）。

2 番目に高い一般的に使用される浮動小数点数メカニズムは 32 ビット (多くのプログラミング言語では「float」型) を使用しますが、それでも効率的ですが、カスタム形式よりも大きくなります。

ただし、独自のカスタム浮動小数点型も設計し、徐々にビットを追加すると、結果はより正確になり、最初に見つけたソリューションよりも効率的になります。有意および指数に使用されるビット数をいじって、fp 近似が目的の結果にどの程度近いかを見つけてください。

于 2011-02-08T11:57:29.530 に答える
0

これが多数の読み取り値の場合は、差分アプローチを試すことができます。絶対的な場所から始めて、インクリメンタルな変更の保存を開始します。変更の性質によっては、理想的には必要なビット数が少なくなるはずです。これにより、ストリームが効果的に圧縮されます。でもどういうわけか、それがこの宿題の目的だとは思いません。

于 2011-02-18T21:10:55.857 に答える