Compressing Sets and Multisets of Sequences

DOI10.1109/TIT.2015.2392093zbMATH Open1359.94560arXiv1401.6410MaRDI QIDQ2978752FDOQ2978752

Christian Steinruecken

Publication date: 28 April 2017

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

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.

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)

Cited In (7)

• Disk compression of \(k\)-mer sets
• Title not available (Why is that?)
• Identities of the Kauffman monoid K3
• Compressed depth sequences
• On the Version Space Compression Set Size and Its Applications
• Title not available (Why is that?)
• Compressions of compact tuples

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)