Questions tagged [data-compression]

The tag has no usage guidance.

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
25 votes
1 answer
1k views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
eggyal's user avatar
  • 359
5 votes
0 answers
143 views

What is the intuition behind the Geometric Burrows-Wheeler Transform?

What is the intuition behind the Geometric Burrows-Wheeler Transform? And how can I use a GBWT with blocking factor $d$ to match a given pattern $P$ of length $|P| = m$ with $m \ge d$ $m < d$ ...
mike's user avatar
  • 175
5 votes
0 answers
136 views

Evaluating sums of subsets

Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$ $$ \begin{align*} s_1&=x_1+x_2+x_3+x_9,\\ s_2&=x_1+x_2+x_4+x_9,\\ s_3&=x_1+x_2+...
Igor's user avatar
  • 187
5 votes
0 answers
268 views

Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
Sebastian's user avatar
  • 4,536
4 votes
0 answers
215 views

Modifying the JPEG compression to use custom block patterns

recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks. I should ...
kindoflike's user avatar
4 votes
0 answers
157 views

Interpretation of Burrows-Wheeler transform, Steps Q2, Q4 and Q6

This question refers to steps Q2, Q4 and Q6 of Algorithm Q, described in the paper "A Block-sorting Lossless Data Compression Algorithm", by M. Burrows and D.J. Wheeler, SRC Research Report, 1994. My ...
Attilio's user avatar
  • 255
4 votes
0 answers
70 views

Approximate estimation of stream compressibility?

I wish to estimate the compression ratio of a stream of bytes. Specifically, I'm interested in DEFLATE compression. I'm looking for some algorithm/heuristic that can estimate roughly the ...
leonbloy's user avatar
  • 256
3 votes
0 answers
53 views

Can you give me insight into the time and space complexity of those pairing functions?

I am looking for a pairing function with linear time complexity. I found one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving. another ...
Raoul's user avatar
  • 205
3 votes
1 answer
139 views

Clustering data for compression with PCA

If I have datapoints in a high dimensional space and want to find a (linear) subspace onto which a data-set projects well, I can use PCA and then discard less important dimensions of the new basis to ...
matthias_buehlmann's user avatar
3 votes
0 answers
273 views

Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
Realz Slaw's user avatar
  • 6,191
3 votes
1 answer
457 views

LZ-type compression vs. entropy-encoding of BWT data

Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data? I noticed that data ...
Log's user avatar
  • 31
3 votes
0 answers
106 views

Bayesian Coding

Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
user6605's user avatar
3 votes
0 answers
117 views

Lossless Video Compression Pipeline

The only paper I can find about an implementation of a lossless video codec is an article by Michael Niedermayer which explains the FF1V compression pipeline. I'm wondering if anyone else has found ...
ninjaneer's user avatar
  • 131
2 votes
1 answer
92 views

Efficient way to calculate many Dutch auctions?

I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily). Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to ...
Neel's user avatar
  • 141
2 votes
0 answers
64 views

Permuting matrix entries to lower rank

Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
Calvin Elder's user avatar
2 votes
0 answers
27 views

Asymptotically Optimal Universal Code In Other Bases

Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
LambdaBeta's user avatar
2 votes
0 answers
51 views

Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
sten's user avatar
  • 139
2 votes
0 answers
164 views

Is arithmetic coding slightly more efficient than rANS?

I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed ...
Wout12345's user avatar
2 votes
0 answers
171 views

Relationship between algorithm size and compression power

Does the size of an algorithm restrict how many bitstrings it can compress, and how much it can compress the bitstrings? Some definitions and an example to illustrate this is the case. An elite ...
yters's user avatar
  • 1,417
2 votes
0 answers
74 views

Clustering with probabilities / vector quantization with arbitrary distance measures

Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). ...
D.W.'s user avatar
  • 159k
2 votes
0 answers
64 views

Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
John L. Jegutanis's user avatar
1 vote
0 answers
96 views

Succint data structure for storing n numbers using a mask-based partition

I've a set $N$ of $n$ distinct numbers of $d$-bits each; call them words ($1\leq n\leq 2^d$, with $d\geq 1$). I want to store $N$ using as least space as possible, by partitioning $N$ and factoring ...
ABu's user avatar
  • 529
1 vote
0 answers
274 views

Theoretically the most efficient compression algorithm

I remember in high school we did this thing where we were given a bunch of numbers in a row that had a pattern. We were asked to work out what the next number in the pattern would be. It was very easy ...
ApplePiePoodle's user avatar
1 vote
1 answer
165 views

Best compression algorithm for CNF SAT instances in DIMACS

For a CNF SAT instance in the DIMACS format what is the best algorithm to compress it? What is the best algorithm for 3-SAT instances in particular? In 2020 SAT competition used .xz which if I ...
dimacs's user avatar
  • 11
1 vote
0 answers
37 views

How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated? A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
user avatar
1 vote
0 answers
55 views

How do I compress data vectors in broadcast messages?

Let us model a wireless broadcast network as an undirected graph $G(V,E)$ where there is an edge between every pair of nodes ${i,j}\in V$ if they are in transmission range of each other. $w_{i\to j}$ ...
fhm's user avatar
  • 21
1 vote
0 answers
68 views

Mathematical limits on lossless data compression

Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the sequence directly but ...
wotot4's user avatar
  • 11
1 vote
0 answers
205 views

Source code or detailed explanation of "WKS" virtual memory compression algorithm?

I've been trying to find information on various program data virtual memory compression algorithms that are in the "WK" family of algorithms. So far, I've been successful with the "WKdm" compression ...
jdb2's user avatar
  • 11
1 vote
0 answers
998 views

Advantages/Disadvantages of adaptive contexual arithmetic coding

What are the advantages and drawbacks of considering ever longer block lengths or context lengths, if one was to work with estimated probabilities(measuring on the fly: aka "adaptive") rather than ...
Duke Glacia's user avatar
1 vote
0 answers
93 views

Implementing binary arithmetic encoder

I have set integers that are normally distributed, and I'm trying to implement binary arithmetic encoding, as suggested in this post: Compressing normally distributed data I'm running into trouble ...
compscinoob's user avatar
1 vote
0 answers
78 views

Computing (near) optimal displacement tables

Suppose we have a two-dimensional table $T$ with $r$ rows and $c$ columns that is sparse. Let $T[i][j]$ be the element at the $i$th row and $j$th column of $T$, with zero-based indexing. We can ...
orlp's user avatar
  • 13.4k
1 vote
0 answers
50 views

Attribute Selection for minimum number of clusters

I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic. Now, any of the headers $P,Q,R,S$ ...
Niloy Saha's user avatar
1 vote
0 answers
37 views

Using less Random Access Memory

Suppose you were to compress data before it was sent to Random Access Memory. Wouldn't you technically be using less R.A.M?
user avatar
1 vote
0 answers
182 views

Compression of gaussian variables

Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with ...
alpha's user avatar
  • 21
1 vote
0 answers
105 views

Which algorithms provide high compression ratios for bit matrices?

I have an x*y bit matrix where the total number of bits fluctuates between ~1,000,000 and ~20,000,000 bits. The rows are much smaller than the columns. An example matrix might be of size 1,000,000 x ...
petro444's user avatar
1 vote
0 answers
56 views

Compressing dataset by cartesian products cover

I have the following problem and I wonder if there exist a solution (or some algorithm to approximate it, even if it's far from optimal, as long as it is tractable) to it. Say I have a set $V\...
Shawn's user avatar
  • 111
1 vote
0 answers
233 views

How well does DEFLATE perform, compared to the theoretical optimum?

I know that there is an inherent limit to how much you can compress data using lossless compression. Basically, the only thing lossless compression can do is reduce dependencies between symbols, ...
GregRos's user avatar
  • 515
1 vote
0 answers
398 views

Compression of a complete Directed Acylcic Graph

Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$: $g ::= l \enspace \bar{g}$ This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths ...
choeger's user avatar
  • 610
1 vote
0 answers
122 views

Can file entropy be predictable?

I am working on some lossless compression topic and looking on any resources or prior studies on lossless file entropy predictability. Assuming we know type of the file (we can tell its belongs to ...
22332112's user avatar
  • 111
1 vote
0 answers
95 views

How to efficiently represent any possible mutations to a string of a given length?

I'm trying to find a "language" or a way to express any change that has occurred to a string. I'm given two strings; a seed string and a new string of the same length that came from it. I'm trying to ...
MetaStack's user avatar
  • 327
0 votes
0 answers
31 views

What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?

I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
Sanjay  Biswas's user avatar
0 votes
0 answers
39 views

Compression Gzip/7Zip

When I calculate the entropy values of files compressed with Gzip, PKZIP, 7ZIP and Winrar, I find that the compression rate of Gzip is higher than the others. The entropy value is higher (indicating ...
Questions123's user avatar
0 votes
0 answers
66 views

Calculation of compression ratio using arithmetic encoding?

Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image. For this, I am using the built-in function of Matlab that also gives other values such ...
Sahil Sharma's user avatar
0 votes
3 answers
296 views

File conversion to binary format to save storage space

Our test log files are stored in .asc format. Each file contains around 5000 rows of these Logging Strings as shown in the image. I would like to reduce the size of these files.They are around 4-5 MBs ...
Sajeev Pillai's user avatar
0 votes
0 answers
45 views

How to compress highly correlated arrays?

I want to write a compression algorithm for a specific use case that I have. I have many arrays which are for the most part, very similar. Each value in the array is an integer and is related to the ...
Shriram's user avatar
  • 101
0 votes
0 answers
46 views

An efficient, probabilistic data structure for storing relationships between elements

I am fascinated by the bloom filter data structure. Is there a similar probabilistic data structure that can efficiently store and update the relationships between certain elements and the strength of ...
magnetlion's user avatar
0 votes
0 answers
92 views

temporal compression of binary data

I have a sequence of source files that are very similar (akin to frames in a video), and each file can be compressed by a codec independently, but there is no temporal compression. I want to further ...
chaohuang's user avatar
  • 101
0 votes
0 answers
25 views

Is defragmentation a kind of minification, a kind of compression or perhaps both?

As far as I understand defragmentation: Removes spaces between objects by putting objects nearer one to the other reorganizes objects for better performance The first action feels to me as some kind ...
timesharer's user avatar
0 votes
0 answers
147 views

File compression using prime numbers

My theory take a file examplesize:(3GB) convert said file to a number divide that number by a large prime number example:(2^82,589,932 · (2^82,589,933-1))[2018 Dec 07] get the quotient and the ...
Steven's user avatar
  • 1
0 votes
0 answers
82 views

How can 4 GB of data can expand into 40 GB of data, when I install Windows on a Computer

Say I start with an iso with about 4GB of data and use this, to install windows on a computer. After installation, the operating system will take up about 40GB of disk space. Where does all this &...
justjates's user avatar