# Questions tagged [compression]

The tag has no usage guidance.

52 questions
5k views

### What is the most efficient way to store a numeric range?

This question is about how many bits are required to store a range. Or put another way, for a given number of bits, what is the maximum range that can be stored and how? Imagine we want to store a ...
224 views

### How can I reduce the amount of storage needed for a gravitational n-body simulation?

I am currently attempting to create a gravitational n-body simulation using a modified Barnes-Hut algorithm, to be more amicable to GPU computation. This is primarily as a learning project. My goal is ...
114 views

### Non-precise Input/Using Probability in File Compression

I'm a high school student interested in topics of computer programming. Recently I became interested in file compression, and in my head I tried to combine this with a completely different part of ...
135 views

### A collision-free hash-like function for use in hash tables and other data structures?

A short introduction to the problem: I'm working with a small database where I have a table of strings (web URLs, to be precise) as pairs: hash|string. Another table references these strings by hash ...
221 views

### Algorithm for optimizing text compression

I am looking for text compression algorithms (natural language compression, rather than compression of arbitrary binary data). I have seen for example An Efficient Compression Code for Text ...
733 views

### How to deal with large data in Websocket message?

I wrote a websocket server in Spring Boot and a client in Javascript. These work fine. I also wrote a second client in Java. When this one attempts to handle a frame after connecting to the host, I ...
77 views

### compression techniques for true random permutation of given integer N

Is it possible to compress true random permutation using low order polynomial interpolation? If yes, how it can be achieved?
2k views

### compression algorithm for non-repeating integers

I have an array of unique integers, for example: {1,3,,7,9,31,46,...}, which I want to compress. I have found compression techniques and algorithms for the list of integers, where some integers are ...
85 views

### Find Randomized Sequence Seed To Compress files statistically

I was wondering if what I have in mind already exists in any known compression programs/algorithms or not. We know that Seed gives us constant sequence of random numbers. so if we be able to find seed ...
231 views

### Why does WinRAR not compress picture duplicates?

I made a test today, how good WinRAR can compress a folder with several times the same picture in it. For that I just put one picture with 300 kB into a folder and copied it there 11 times, so that I ...
202 views

### Advantages of application-level data compression?

This question was inspired by MessagePack, but I'm looking for a general answer about the advantages of in-app vs. external compression. For network I/O, doesn't the transport protocol (at least ...
12k views

### Does storing plain text data take up less space than storing the equivalent message in binary?

As a web developer I have very little understanding of binary data. If I take the sentence "Hello world.", convert it to binary, and store it as binary in an SQL database, it seems like the 1s and ...
92 views

### I need to find a set of hierarchical symbols that can represent input binary data in near optimal space. What algorithms can I look into? [closed]

I have a stream of binary data. Assume no prior knowledge about the expected pattern in input data. The symbols can represent binary data or other symbols, hence hierarchical. The output should ...
74 views

### Direction-free optimal encoding

Consider an alphabet of k symbols and a requirement to optimally encode a series of values of known frequency. The obvious choice for this is to use Huffman coding, which is known to be optimal for ...
496 views

### Is saving disk space a valid reason to forgo migrating to a standard text format (e.g. JSON)?

A while ago I asked a question about custom text data formats, instead of using existing tools such as XML, JSON, YAML, etc. Now, in favor of converting our custom format to a relational database and ...
2k views

### Fast and simple hex compression

I'm working on a project that requires a TCP connection between a client and server. The current protocol encodes the data into hex and then sends it. However, hex increases the length of the payload ...
290 views

### PDF content : text or graphics?

Is there a possible test to check if a PDF file contains text or it is created by scanning paper sheets ? text : plain text that, for example, I can copy & paste while I am reading the PDF. Not ...
2k views

### Fast, lossless compression of a video stream

I have a video coming from a stationary camera. Both the resolution and the FPS are quite high. The data I get is in Bayer format and uses 10 bit per pixel. As there's no 10 bit data type on my ...
198 views

### finding optimal token definitions for compression

I have a collection of strings which have a lot of common substrings, and I'm trying to find a good way to define tokens to compress them. For instance, if my strings are: s1 = "String" s2 = "Bool" ...
61 views

### Efficient saving of long strings with recurring substrings

following problem: I need to save a lot of xml strings of variable length and structure. As it is with xml, a lot of substrings are the same (some elements, attribute and value combination). Often the ...
643 views

### Best compression algorithm for timelapse photos

I have a folder containing about 9,000 JPEG photos (about 30Gb), which I want to archive with some sort of compression. I understand that compressing JPEGs is not normally very effective, but these ...
414 views

### Why use last column of Burrows-Wheeler-Transform

The Burrows-Wheeler-Transform takes a string with length n, creates a matrix with n rows by shifting this string one position to the left for each row. Then the rows are sorted by the first column in ...
760 views

### Best two-way compression algorithm for 32-bit numbers

I need to compress an id for marketing campaigns. The current campaign id is 32-bit integer but obviously this is too long for a customer to type by hand. I would like to compress this to minimum ...
236 views

### What is this compression algorithm? (Similar to RLE)

In Run Length Encoding (RLE), a large set of information is encoded by storing the quantity of consecutive sequences. A canonical example is: ...
130 views

### Sparse set lossy compression algorithm

I am looking for algorithm or idea for the following problem. Suppose we have a data type, say 64-bit integer. Now we have a relatively small set of such items, say few hundred at most. The simplest ...
311 views

### Minimizing compression overhead in a simple compression algorithm

Note: this question has been re-written to simplify and generalize the problem. The original is available below. Suppose I created a simple compression scheme for lists of 2-digit numbers. It has 2 ...
1k views

### Calculating uncompressed file size without uncompressing file in zlib

I am writing a python program which parses zip (currently only zlib, using DEFLATE compression) files and verifies the correctness of their headers and data. One of the things I'm trying to achieve is ...
2k views

### Turn on gzip on nginx, upstream (nodejs) or both? [closed]

I have an application running behind a proxy, both on the same machine. Which approach is more suited regarding compression, while preserving reasonable performance. turn on compression at the ...
1k views

### What should I do when using Golomb/Rice code for large values？

When using Golomb/Rice code in image compression, it is inevitable for us to meet large values. Golomb coding uses a tunable parameter M to divide an input value N into two parts : q, the result of a ...
189 views

### Why is there little use of filesharing as compression (outside of libraries)?

Recently I was looking for a program that will run as a daemon and find files that have the same size/type, check if they're the same, then make both a hard link to a single copy if they are. And I ...
1k views

### How does Yahoo's Smush.It work and why doesn't everyone use it?

I've recently come across an application by Yahoo called SmushIt. Apparently it does lossless compression on images. Sometimes the image size is reduced by as much as 90%. This of course has major ...
6k views

### How would you go about compressing a list of integers that are non unique and retain the original order?

Let's start out with an example [1,1,1,5,3,1,1,2,78,2,3,1,1,...,1] As you can tell by the example, 1 is repeated a lot, but there will be outliers (like 78, and really anything that isn't 1). The ...
800 views

### Is hash calculated before/after compression?

I had a question regarding compression and calculation of checksum/hash of data. I would like to know if checksum has to be calculated before or after the compression of data before transmission. ...
316 views

### Estimation of space is required to store 275305224 of 5x5 MagicSquares? [closed]

Here are some examples of 5x5 Magic Squares found by some good solvers : Magic Square Generator by Marcel Roos this program state using 2.4GHz Intel takes about 95 hours to generate all solutions. ...
372 views

### JavaScript Compression and Caching of Assets

I'm working on an idea that i can't seem to find a good answer though hours and hours of searching, I'm planning a small Canvas/WebGL Application this application will be using WebSockets to talk to ...
179 views

### If we could get a file's binary form, would this method of file compression work?

I'm not quite sure how easy it is to fetch the binary composition of a file, but suppose we have some file with this representation: 010011 We could make 2 arrays. One which stores the position of ...
18k views

### How do I find average bits per symbol using huffman code?

I'm trying to write a program in c for Huffman coding, but I am stuck. For input I have: Sample input: 4 // here I scan how many letters I have A 00 // and for everyone I scan how they are ...
1k views

### What is (or where can i find) the algorithm to decode FLAC to PCM?

I'm trying to program a very basic FLAC player using 100% C# completely from scratch. My understanding of this type of thing is very limited, so I'm using this project as a way to learn about ...
2k views

### How to choose parameter for Golomb coding?

I am trying to implement Golomb coding, but I don't understand how it's tuned to obtain optimal code. It is said that Golomb coding uses a tunable parameter M to divide an input value into two ...
5k views

### What data cannot be compressed by huffman codes?

What kind of data cannot be compressed by using the huffman codes and why? I tried looking for the answer, but I only came across loss-less and lossy compression. I don't really understand what ...
252 views

### Algorithm for compression of a dictionary (words and definitions)

The theoretical situation is this: Let's say that we have a digital dictionary (by which I mean a traditional list of words and definitions, not an associative array). For the sake of simplicity, ...
391 views

### Take dynamic PHP array, package up as separate files inside a single zip file

I have this dynamic data in PHP, but for each array record, I want to allow a downloadable option to save a zip archive of all records (each as a separate file). These are actually DNS zone records ...
10k views

### Fast compression in C++ and decompression in C#

Overview I am working on a client-server application. The client is written in C++ (working on Windows, planning to support Linux) and the server is a .NET RESTful service. I need to HTTP POST some ...
525 views

### Arithmetic Coding vs. Machine Numeric Precision

When subdividing intervals for arithmetic coding, the worst case scenario is that the final interval will have size 2^(1-n), where n is the number of unique symbols you are encoding. This will reach ...
721 views

### Arithmetic Coding Questions

I have been reading up on arithmetic coding and, while I understand how it works, all the guides and instructions I've read start with something like: Set up your intervals based upon the frequency ...
391 views

### What should developers know about Windows executable binary file compression?

I'd never heard of this before, so shame on me, but programs like UPX can compress my files by 80% which is totally sweet, but I have no idea what the the disadvantages are in doing this. Or even ...
158 views

### Is it possible to modify a video codec + distribute it?

this is my first question on this particular stackexchange node, not sure if it's the most appropriate place for this question (if not, guidance to the appropriate node would be appreciated). the ...
242 views

### Where can I find good example of techniques to compact data in-memory? [closed]

I'm writing a Java framework to manipulate a large amount of data in-memory, where many "cells" that are near each other will have the same value. I'm looking for algorithms and/or techniques ...