空间高效的长表示

问题描述：

我想在Java中取长整型值，并将其转换为字节数组。空间高效的长表示

但是，我希望表示对于较小的值很小，所以如果值小于127，那么它只需要一个字节。

编码和解码算法应该是非常有效的。

我敢肯定这已经完成，但我找不到任何示例代码，任何人有任何指针？

也许你可以看看UTF-8编码的灵感？ – 2011-02-16 22:33:04

没错，我对这个概念很熟悉，但是我宁愿使用现有的实现（如果存在的话）（我肯定是必须的） – sanity 2011-02-16 22:37:08

'任何人都有任何指针？'必须是一个经典的文字游戏。真正的史诗。您可能会将长整型加载到字节缓冲区中，然后尝试将字节缓冲区编码为char到utf-8字符串。如果你的最低7位与ASCII的最低位对齐，它可能会工作得很好。 – 2011-02-16 22:45:20

答

您可以使用停止位编码，例如

public static void writeLong(OutputStream out, long value) throws IOException { 
    while(value < 0 || value > 127) { 
     out.write((byte) (0x80 | (value & 0x7F))); 
     value = value >>> 7; 
    } 
    out.write((byte) value); 
} 

public static long readLong(InputStream in) throws IOException { 
    int shift = 0; 
    long b; 
    long value = 0; 
    while((b = in.read()) >= 0) { 
     value += (b & 0x7f) << shift; 
     shift += 7; 
     if ((b & 0x80) == 0) return value; 
    } 
    throw new EOFException(); 
}

这是一种快速的压缩形式，但所有的压缩都需要付出代价。（但是，如果你的带宽有限，传输速度可能会更快并且价值不菲）

顺便说一句：值0到127使用一个byte。您也可以对short和int值使用相同的例程。

编辑：你仍然可以在这之后使用通用压缩，它可以小于不使用这个。

public static void main(String... args) throws IOException { 
    long[] sequence = new long[1024]; 
    Random rand = new Random(1); 
    for (int i = 0; i < sequence.length; i+=2) { 
     sequence[i] = (long) Math.pow(2, rand.nextDouble() * rand.nextDouble() * 61); 
     // some pattern. 
     sequence[i+1] = sequence[i]/2; 
    } 
    testDeflator(sequence); 
    testStopBit(sequence); 
    testStopBitDeflator(sequence); 
} 

private static void testDeflator(long[] sequence) throws IOException { 
    ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
    DataOutputStream dos = new DataOutputStream(new DeflaterOutputStream(baos)); 
    for (long l : sequence) 
     dos.writeLong(l); 
    dos.close(); 
    System.out.println("Deflator used " + baos.toByteArray().length); 
} 


private static void testStopBit(long[] sequence) throws IOException { 
    ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
    for (long l : sequence) 
     writeLong(baos, l); 
    baos.close(); 
    System.out.println("Stop bit used " + baos.toByteArray().length); 
} 

private static void testStopBitDeflator(long[] sequence) throws IOException { 
    ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
    DataOutputStream dos = new DataOutputStream(new DeflaterOutputStream(baos)); 
    for (long l : sequence) 
     writeLong(dos, l); 
    dos.close(); 
    System.out.println("Stop bit & Deflator used " + baos.toByteArray().length); 
} 

public static void writeLong(OutputStream out, long value) throws IOException { 
    while (value < 0 || value > 127) { 
     out.write((byte) (0x80 | (value & 0x7F))); 
     value = value >>> 7; 
    } 
    out.write((byte) value); 
}

打印

Deflator used 3492 
Stop bit used 2724 
Stop bit & Deflator used 2615

什么工作最好是高度依赖于要发送的数据。例如如果你的数据是真正随机的，你使用的任何压缩技术只会使数据变大。

平减指数是gzip的输出的精简版（减去头和CRC32）

答

请参阅C＃中的Read7BitEncodedInt。（这是相同的概念。）

答

简单地使用GZipOutputStream - 像GZip这样的熵编码基本上完全是你描述的，只是一般的。

编辑： 只是可以肯定：你是否意识到，对于小的数字仅使用1个字节的可变长度编码不一定需要使用超过8个字节的最大的呢？除非您知道自己的数据量远远小于大数量，否则最终可能会增加数据的整体大小。而GZIP适应您的实际数据集，并且可以压缩以不同方式倾斜的数据集。

虽然这听起来不是CPU效率很高： -/ – sanity 2011-02-16 22:35:44

答

如果要存储具有不同长度的值long，那么您将需要一个分隔符，否则您无法确定哪个字节属于哪个long值......并且分隔符会为数据添加额外的字节...

如果你正在寻找一个快速的库来存储长期价值（每个64Bit），我建议colt。它是快。

答

（我可能会说明明显的一些人......但在这里不用。）

如果您正在做某些外部序列化中减小值long的值，继续。

但是，如果您试图在Java程序中节省内存，您可能会浪费时间。 Java中byte[]的最小表示形式是2或3个32位字。这是一个长度为零的字节数组。为大于零的任何数组长度添加一些32位字的倍数。然后，您必须允许至少一个32位字保存对该对象的引用。

如果加上，至少需要4个单词来表示除0L之外的任何给定long作为byte[]。

如果您在单个byte[]中代表long值的数目，您将获得任何保存的唯一情况。您可能需要至少3个long的价值才能达到平衡，即使如此，如果平均值过大，您也会失去价值。

空间高效的长表示

相关推荐