代码之家 › 专栏 › 技术社区 › alamar

以预建字典为数据结构的压缩算法

compression data-structures dictionary java

1

alamar · 技术社区 · 8 年前

我很确定这是一个常见的用例,但是经过半天的谷歌搜索,我不得不回答一个问题。

我真的很想要一个算法,我可以在一个数据集上运行来确定字典(作为一个数据结构),然后使用字典来压缩新到达的数据非常快速和高效,这要感谢字典。

有那种东西吗?IBM DB2公司 does exactly that 但我怀疑他们是否公开了这种方法。小精灵 allows one to pass dictionary ,但它是原始字节数组,需要对每条消息进行处理,并且没有生成该字节数组的方法。

将数据结构保存在内存中的想法是为了避免每个消息处理的任何开销。

Java实现的加分。

2 回复 | 直到 8 年前

1

2

alamar 7 年前

最后我被指向 Zstd compression 允许提供您自己的(共享)字典。有 Java bindings 具备基于样本的词典训练能力。

它能够在512字节的共享字典中胜过我自己的算法:

( s 是样本数, d 是字典长度, l 是压缩级别)

2

0

alamar 8 年前

我最终使用lzw-huffman混合实现了自己的压缩。

我使用lzw构建了一个字典(使用参考数据集),其中码位映射到字节序列,然后根据这些码位的频率生成huffman树。然后我使用treemap在输入数组中查找字节序列,并将它们传递给huffman编码器。

它工作得相当好。0.4压缩在大约120字节的条目上是典型的,其中gzip给出0.75。

我仍然对这个问题的优化库存解决方案感兴趣。