8

位置データ（緯度、経度、日付、時刻）を圧縮します。すべての番号は固定形式です。そのうちの2つ（緯度、経度）は10進形式です。他の2つは整数です。

現在、これらの数値は固定フォーマットの文字列になっています。

固定形式で数値を圧縮するためのアルゴリズムは何ですか？数値のみの圧縮（ある場合）は文字列の圧縮よりも優れていますか？文字列を数値に変換せずに直接圧縮してから圧縮する必要がありますか？

前もって感謝します。

4

5 に答える 5

7

これは、ちょっとした理論が役立つ場所の 1 つです。いくつかのことを考える必要があります。

  • 測定の分解能は?: 0.1° または 0.001°? 1秒ですか、それとも1マイクロ秒ですか？
  • 測定値は何らかの順序で関連付けられていますか、それともランダムにまとめられていますか?

たとえば、分解能が 0.01° だとします。値の範囲が -180° から +180°、つまり 35900 の異なる値であることを知っています。Lg(35900) ≈ 16 なので、16 ビットが必要です。-90° ～ +90° の場合は 14 ビット。明らかに、この種の値を浮動小数点として格納している場合、データをすぐに半分に圧縮できます。

日時と同様に、範囲は何ですか。何ビット必要ですか？

ここで、データが何らかの順序である場合 (1 隻の船に乗って連続して採取されたサンプルなど)、必要なのは開始値とデルタだけです。それは大きな違いを生む可能性があります。船が 30 ノットで移動している場合、位置は 1 時間に約 0.03 度、または 1 秒に約 0.0000083 度しか変化しません。これらのデルタは非常に小さい値になるため、それらを非常に少数のビットに格納できます。

要点は、できることはたくさんありますが、推奨を行うには、データについてより多くのことを知る必要があるということです。

更新:ああ、待って、固定小数点文字列?!

わかりました、これは（比較的）簡単です。まず、文字列を何らかのバイナリ表現に変換したいと考えています。データ項目を作成するだけで、

040.00105.0020090518212100Z

あなたが変換できるもの

| | 4000 | short int、16 ビット |  
| | 10500 | short int、16 ビット |  
| | 20090518212100Z | 64 ビット |

これは 96 ビットで、12 バイト対 26 バイトです。

于 2009-05-18T18:52:03.003 に答える
5

圧縮は通常、バイト ストリームで機能します。ストリームのバイト値の分布が不均一な場合 (たとえば、テキスト、またはテキストとして格納された数値)、達成できる圧縮率は高くなります。圧縮）。

通常、話しているデータは単純に 2 進数 (テキストではなく) として保存されます。これは通常、スペースと検索の効率が高くなります。

The Data Compression Bookをご覧になることをお勧めします。

于 2009-05-18T18:23:03.077 に答える
2

どのようなデータを圧縮していますか? どのように配布されますか？それは何らかの方法で注文されていますか？これらすべてが圧縮の程度に影響を与える可能性があり、おそらくデータをより簡単に圧縮できるものに変換したり、単純に小さくしたりすることができます。

データ圧縮は、「ランダム」データではうまく機能しません。データがより狭い範囲内にある場合は、それを活用できる可能性があります。

実際には、一般的なアルゴリズムのいずれかを実行して、データが「十分に圧縮」されているかどうかを確認する必要があります。そうでない場合、および圧縮アルゴリズムによって「直観」できる以上にデータについて知っている場合は、その情報を活用する必要があります。

たとえば、データが緯度と経度だけではなく、互いに「近い」と想定されているとします。次に、おそらく「原点」の緯度と経度を保存し、残りを差分にすることができます。おそらく、これらの違いは、符号付きの 1 バイトに収まるほど小さいものです。

これは、データの知識でできることと、一般的なアルゴリズムでは理解できないことの単純な例です。

于 2009-05-18T18:30:33.297 に答える
1

それは、データで何をしようとしているのか、どの程度の精度が必要なのかによって異なります。

緯度/経度は伝統的に度、分、秒で表され、1 分は 60 秒、1 度は 60 分、緯度 1 度は公称 60 海里 (nmi) に相当します。1 分は 1 nmi で、1 秒は 100 フィート強です。

緯度は -90 度から +90 度まで変化します。緯度を整数秒で表すと、範囲は -324000..+324000、つまり約 20 ビットになります。経度は -180 から +180 になるため、同じ方法で経度を表すには、さらに 1 ビット必要です。

したがって、41 ビットで +/- 50 フィートまでの完全な緯度/経度位置を表すことができます。

明らかに、それほど精度が必要ない場合は、ビット数を減らすことができます。

従来の単精度 32 ビット浮動小数点数では約 24 ビットの仮数が使用されることに注意してください。したがって、秒単位の緯度/経度を浮動小数点数に変換するだけで、約 +/- 6 フィートになります。この種の場合、2 つの単精度 float を打ち負かすのはちょっと難しいです。

于 2009-05-18T19:23:38.900 に答える
0

利用可能なキャラクターによっては、非常に簡単に何かを作成できます。

たとえば、入力が数字 (0..9) のみの場合、Kotlin でそれらをエンコードおよびデコードするソリューションを次に示します (Java で同様のもの)。

fun encodeDigitsOnlyString(stringWithDigitsOnly: String): ByteArray {
    //we couple each 2 digits together into a single byte.
    //For the last digit, if it has no digit to pair with, it's paired with something that's not a digit
    val result = ArrayList<Byte>()
    val length = stringWithDigitsOnly.length
    var lastDigit: Byte? = null
    for (i in 0 until length) {
        val char = stringWithDigitsOnly[i]
        val digitAsByte = char.toString().toInt().toByte()
        if (lastDigit == null) {
            if (i == length - 1) {
                //last digit
                val newByte = (digitAsByte + 0xf0).toByte()
                result.add(newByte)
            } else {
                //more to go
                lastDigit = digitAsByte
            }
        } else {
            val newByte = (digitAsByte + lastDigit.toInt().shl(4)).toByte()
            result.add(newByte)
            lastDigit = null
        }
    }
    return result.toByteArray()
}

fun decodeByteArrayToDigitsOnlyString(encodedDigitsOnlyByteArray: ByteArray): String {
    val sb = StringBuilder(encodedDigitsOnlyByteArray.size * 2)
    for (byte in encodedDigitsOnlyByteArray) {
        val hex = Integer.toHexString(byte.toInt()).takeLast(2).padStart(2, '0')
        if (hex[0].isLetter())
            sb.append(hex.last())
        else
            sb.append(hex)
    }
    return sb.toString()
}

使用例:

val inputString="12345"
val byteArray=encodeDigitsOnlyString(inputString) //produces a byte array of size 3
val outputString=decodeByteArrayToDigitsOnlyString(byteArray) //should be the same as the input
于 2020-07-12T08:40:28.017 に答える