8

我要压缩位置数据（纬度、经度、日期、时间）。所有数字都是固定格式。其中 2 个（纬度、经度）采用十进制格式。其他 2 是整数。

现在这些数字是固定格式的字符串。

以固定格式压缩数字的算法是什么？仅数字压缩（如果有的话）是否比字符串压缩更好？我应该直接压缩字符串而不将其转换为数字然后压缩吗？

提前致谢。

4

5 回答 5

7

这是一些理论很有帮助的地方之一。你需要考虑几件事：

  • 您的测量分辨率是多少：0.1° 或 0.001°？1 秒还是 1 微秒？
  • 测量值是关联的并按某种顺序排列，还是随机组合在一起？

例如，假设分辨率为 0.01°。他们知道您的值范围从 -180° 到 +180°，或 35900 个不同的值。Lg(35900) ≈ 16 所以你需要 16 位；-90°–+90° 为 14 位。显然，如果您将这种值存储为浮点数，您可以立即将数据压缩一半。

与日期时间类似，范围是多少；你必须有多少位？

现在，如果数据按某种顺序排列（例如，在一艘船上按顺序采集样本），那么您只需要一个起始值和一个增量；这可以产生很大的不同。一艘船以 30 节的速度航行，位置不能再改变大约每小时 0.03 度或每秒大约 0.0000083 度。这些增量将是非常小的值，因此您可以将它们存储在很少的位中。

关键是您可以做很多事情，但您必须比我们更了解数据才能提出建议。

更新：哦，等等，定点字符串？！

好的，这（相对）容易。首先，是的，您想将字符串转换为某种二进制表示形式。只是组成一个数据项，你可能有

040.00105.0020090518212100Z

你可以转换成

| 4000 | 短整数，16 位 |  
| 10500 | 短整数，16 位 |  
| 20090518212100Z | 64 位 |

所以这是 96 位，12 字节与 26 字节。

于 2009-05-18T18:52:03.003 回答
5

压缩通常适用于字节流。当流的字节值分布不均匀时（例如文本或存储为文本的数字），您可以获得的压缩率会更高，因为用于存储更频繁出现的字节的位更少（在 Huffman压缩）。

通常，您所谈论的数据将简单地存储为二进制数（而不是文本），这通常是空间和检索效率。

我建议你看看The Data Compression Book

于 2009-05-18T18:23:03.077 回答
2

你在压缩什么样的数据？它是如何分布的？是否以任何方式订购？所有这些事情都会影响它的压缩程度，并且可能允许您将数据转换为更容易压缩的东西，或者只是一开始就更小。

数据压缩在“随机”数据上效果不佳。如果您的数据在较小的范围内，您很可能可以利用它。

事实上，您应该简单地尝试运行任何常用算法，看看数据是否“足够压缩”。如果不是，并且您对数据的了解比压缩算法“直觉”的多，那么您应该利用该信息。

举个例子，假设您的数据不仅仅是 Lat 和 Long 的数据，而且它们被假定为彼此“接近”。然后你可能会存储一个“原点”纬度和经度，其余的可以是微分的。也许这些差异小到足以放入单个有符号字节。

这只是一个简单的例子，说明您可以利用数据知识做的事情与一些通用算法可能无法弄清楚的事情。

于 2009-05-18T18:30:33.297 回答
1

这取决于您将如何处理数据，以及您需要多少精度。

纬度/经度传统上以度、分和秒表示，60 秒到分钟，60 分钟到度数，1 纬度名义上等于 60 海里 (nmi)。1 分钟是 1 nmi，1 秒刚好超过 100 英尺。

纬度从 -90 度到 +90 度。将纬度表示为整数秒为您提供 -324000..+324000 的范围，或大约 20 位。经度从 -180 到 +180，因此以相同方式表示经度需要多 1 位。

因此，您可以以 41 位表示完整的纬度/经度位置，达到 +/- 50 英尺。

显然，如果您不需要那么高的精度，您可以降低您的位数。

请注意，传统的单精度 32 位浮点数使用大约 24 位尾数，因此如果您只需将纬度/经度（以秒为单位）转换为浮点数，就可以降低到大约 +/- 6 英尺。对于这种事情，很难击败两个单精度浮点数。

于 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 回答