Questions tagged [data-compression]

The tag has no usage guidance.

60 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
23
votes
1answer
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 ...
5
votes
0answers
131 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$ ...
5
votes
0answers
128 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+...
5
votes
0answers
245 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, ...
5
votes
0answers
327 views

LZ-type compression with a limited recursion depth

I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get ...
4
votes
0answers
136 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 ...
4
votes
0answers
66 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 ...
3
votes
1answer
35 views

Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset

Problem Description I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
3
votes
0answers
68 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 ...
3
votes
0answers
258 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 ...
3
votes
0answers
344 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 ...
3
votes
0answers
104 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 ...
3
votes
0answers
111 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 ...
2
votes
0answers
11 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://...
2
votes
0answers
33 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 : ...
2
votes
0answers
30 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 ...
2
votes
0answers
63 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 ...
2
votes
1answer
64 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 ...
2
votes
0answers
161 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 ...
2
votes
0answers
52 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$). ...
2
votes
0answers
60 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 ...
1
vote
1answer
35 views

LZW with dictionary clearing

How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used ...
1
vote
0answers
43 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}$ ...
1
vote
0answers
57 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 ...
1
vote
2answers
78 views

Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
1
vote
0answers
508 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 ...
1
vote
0answers
46 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 ...
1
vote
0answers
63 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 ...
1
vote
0answers
44 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$ ...
1
vote
0answers
36 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?
1
vote
0answers
147 views

Compression of gaussian variables

Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with ...
1
vote
0answers
99 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 ...
1
vote
0answers
42 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\...
1
vote
0answers
331 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 ...
1
vote
0answers
116 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 ...
1
vote
0answers
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 ...
0
votes
0answers
18 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 ...
0
votes
0answers
41 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 ...
0
votes
0answers
15 views

Efficiently compressing and decompressing an array of combinations

I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example ...
0
votes
0answers
22 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 ...
0
votes
0answers
48 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 &...
0
votes
0answers
41 views

Design of a synchronized clock

I was living in a country where Internet wasn't that fast so the younger me had the following idea for compressing data Let say 2 parties want to send data to each other, we know that data can be ...
0
votes
0answers
20 views

Significance of model in arithmetic coding

I am trying to understand the concept of arithmetic coding, i understand how the range is subdivided after each character is read from the string. But i am unable to understand why using a more ...
0
votes
0answers
46 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 ...
0
votes
0answers
32 views

How would I make sure my compressed string has the smallest length possible?

I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' ...
0
votes
0answers
25 views

How can i compare lossy image compression techniques?

I need to find which lossy image compression technique is the best. I chose to test JPEG, WebP and BPG. Which criteria can I choose for comparison apart from quality and speed of compression and how ...
0
votes
0answers
41 views

Is entropy a good indicator of the quality of a lossy compression?

Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator? To ...
0
votes
0answers
56 views

An interesting compression algorithm idea

I stumbled on this paper about compressing images using a kind of odd, but interesting idea. It seems pretty easy to implement and I was wondering if there is something wrong with it that I haven't ...
0
votes
0answers
110 views

How much data can be send in 1 minute of audio with Smartphone speakers / microphones?

Having the current news about Google Assistant in mind, I thought that robots might use interfaces designed for humans to send data. Like a telephone interface. Then I wondered: What is the maximum ...
0
votes
1answer
454 views

What algorithm is most suitable for large text compression?

Currently, I am looking for an lossless compression algorithm that is suitable for a large amount of text, that will be further encrypt by AES and use as the payload in steganography. Based on A ...