Compressing Sets and Multisets of Sequences

DOI10.1109/TIT.2015.2392093MaRDI QIDQ2978752zbMATH OpenFDO

Authors Christian Steinruecken

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6410

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: This article describes lossless compression algorithms for multisets of sequences, taking advantage of the multiset's unordered structure. Multisets are a generalisation of sets where members are allowed to occur multiple times. A multiset can be encoded na"ively by simply storing its elements in some sequential order, but then information is wasted on the ordering. We propose a technique that transforms the multiset into an order-invariant tree representation, and derive an arithmetic code that optimally compresses the tree. Our method achieves compression even if the sequences in the multiset are individually incompressible (such as cryptographic hash sums). The algorithm is demonstrated practically by compressing collections of SHA-1 hash sums, and multisets of arbitrary, individually encodable objects.

Cited in

(7)

• Compressed depth sequences
• Compressions of compact tuples
• On the Version Space Compression Set Size and Its Applications
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• scientific article; zbMATH DE number 1421006 (Why is no real title available?)
• scientific article; zbMATH DE number 4204287 (Why is no real title available?)
• Disk compression of \(k\)-mer sets

This page was built for publication: Compressing Sets and Multisets of Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978752)