Questions tagged [data-compression]
The data-compression tag has no usage guidance.
194
questions
2
votes
1answer
18 views
on-the-fly decompress a flat-file database
I'm facing the following problem. I have a flat-file database (e.g. CSV).
Since it's relatively large to store in memory, I'd like to compress it.
Given a key, I need to return the uncompressed text (...
0
votes
0answers
15 views
Alternatives to multiplication/division/modulo for encoding choices?
The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % ...
3
votes
1answer
60 views
Applying SVD compression to integral point images
Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
1
vote
1answer
15 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 ...
1
vote
2answers
53 views
Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
0
votes
1answer
39 views
How a Data Compression Software Reads a File as pure Binary File and makes Output?
I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,
I read texts ...
0
votes
1answer
22 views
Find an infinite set of strings that are compressable better than in $O(\log n)$ space
The task is to find an infinite set of strings $a_1,a_2\ldots$, where $|a_{i+1}|>|a_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a_i)|=o(\log_2 |a_i|)$ with $i\to\...
1
vote
2answers
37 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
110 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 ...
3
votes
1answer
56 views
How many “compressible” strings are there?
Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.
It is easy to see that almost all ...
0
votes
0answers
23 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 ...
3
votes
3answers
105 views
Is it possible to have high compression but low predictability?
Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?
'impossible to predict' - sequence cannot be predicted ...
0
votes
0answers
43 views
Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?
In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g.
...
2
votes
1answer
27 views
Proof high-entropy sequences are hard to compress
When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress?
In ...
1
vote
1answer
46 views
Is a complete code always optimal?
According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?
-1
votes
2answers
52 views
Can data be compressed through this hash function technique?
I'd like to know if this data compression scheme would work or not, and why:
Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
3
votes
0answers
50 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 ...
1
vote
0answers
40 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
1answer
39 views
How to find optimal token set for compression?
By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like ...
0
votes
2answers
44 views
is there a (FLAC like) loseless compression coding format for EEG data? [closed]
EEG and Audio data are very similar, both
are numerical samples in continuous sequence
have a sample rate
need and can have multiple channels
channels for multi-channel audio
channels for each ...
1
vote
1answer
101 views
Run Length Encoding Compression With Nested Level
I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:
ABABABCABABABC --> 3(AB)C3AB(C) --> 2(3(AB)C) ?
It's ...
0
votes
0answers
36 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 ...
1
vote
1answer
44 views
Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler
In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link.
On page number 5. please describe this line
If the original string $S$ is of the form $Z^p$ for ...
0
votes
0answers
46 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
1answer
47 views
Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)
For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
4
votes
1answer
727 views
How does a predictive coding aid in lossless compression?
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen ...
0
votes
1answer
57 views
Is it possible to achieve greater than perfect compression using machine learning and big data?
Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using ...
3
votes
3answers
1k views
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which ...
1
vote
0answers
36 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 ...
35
votes
6answers
7k views
Do lossless compression algorithms reduce entropy?
According to Wikipedia:
Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
2
votes
1answer
36 views
Is there an algorithm to achieve optimal compression in a “streamed” manner, assuming equal probability of each possibility?
(Sorry for the question title; edits are welcome.)
Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ ...
2
votes
1answer
146 views
what is a shearlet/shearlet transform and how can i use it?
from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles ...
-1
votes
3answers
258 views
I think you can always compress compressed data, is it true?
In compressed data, repetition of same pattern is not a lot, so, you can expect it to be with space inside to contain always. I found a way to compress data without limitation. Is it right? Am I ...
3
votes
1answer
431 views
What is the best way to compress a string with only numbers and commas in it?
I have a string like this:
11,512,64,23,46,12,67,85,84
And I'm sure it's following these rules below:
Only , and ...
3
votes
2answers
198 views
Compression algorithms for small strings - building upon / extending Huffman
I'm exploring algorithms to compress small strings like the following - every line is to be compressed individually, i.e. even those small strings should get compressed:
...
18
votes
4answers
6k views
Can data be compressed to size smaller than Shannon data compression limit?
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of ...
0
votes
1answer
141 views
What is the most compact (space efficient) method of storing an array of distinct integers?
I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must ...
7
votes
1answer
188 views
Most space-efficient lossy dictionary?
Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?
Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
2
votes
1answer
62 views
Algorithm for estimating lossless compression factor
Is there any algorithm for estimating how well certain array of bytes could be compressed in lossless manner?
Usage for me is to automatically choose "best" data reorder method without knowing what ...
2
votes
2answers
72 views
Does this progressive image compression exists?
I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.
The algorithm consists of converting one high ...
-3
votes
1answer
36 views
Character in Huffman encoding [closed]
Is a full stop regarded as a character along or must it be with a space in huffman encoding. I know of taking a comma with a space to a character.
1
vote
1answer
40 views
Compression with random dictionary
Is the following scenario theoretically possible, or provably impossible?
Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice ...
1
vote
0answers
29 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
2answers
96 views
Data compression with Turing Machine
For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best ...
0
votes
0answers
33 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
0answers
284 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 ...
3
votes
2answers
316 views
How would the use of an external lookup table affect file compression?
It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My ...
1
vote
1answer
149 views
Was my Huffman coding solution wrong?
I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:
A: 0.15
B: 0.2
C: 0.55
D: 0.1
I encoded them as ...
1
vote
1answer
52 views
Generate numeric or string ID for a sequence of elements
How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.
Example:
[41,1001,32] should generate the ...
2
votes
1answer
41 views
Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:
Here's a reference: https://en....
