12
$\begingroup$

Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I find research in this area?

Specifically, I have a json list of 1.5 million strings, and I want to reorder the strings so that gzip (for HTTP) compression is optimized. Sorting the strings does pretty well, but I don't really know if that is optimal.

$\endgroup$
  • 1
    $\begingroup$ Optimally reordering strings for gzip compression (LZ77 with a small sliding window) sounds like an NP-hard problem. You can probably come up with a reduction from the shortest common superstring problem. $\endgroup$ – Jouni Sirén Mar 6 '15 at 9:38
  • $\begingroup$ @JouniSirén I think longest common substring is a better approach since shortest common superstring limits me to having the common part back-to-back, right? I don't mind NP-hard as long as it's tractable (like takes a day to run on a modern machine). $\endgroup$ – Jayen Mar 6 '15 at 23:49
6
$\begingroup$

This is an addition to the Navin Goyal's answer.

Since a JSON file can be regarded as a tree data structure, you can use the XBW-transform for trees, which is an extension of the Burrows-Wheeler transform for strings.

$\endgroup$
  • 1
    $\begingroup$ Thanks for that. I only have a JSON list/array, not any JSON objects, so I don't see how it can be regarded as a tree. I could convert the strings into a trie, but then I don't see how this relates to the XBW-transform. $\endgroup$ – Jayen Mar 5 '15 at 22:17
4
$\begingroup$

Burrows--Wheeler transform is a well-known compression algorithm that works by reordering the characters in the string to be compressed.

$\endgroup$
  • 1
    $\begingroup$ Thanks for that, but I'm not sure how I can use this information. I want to reorder the strings in the list to be compressed, but I don't care if I can get back the original order. $\endgroup$ – Jayen Mar 5 '15 at 22:15
1
$\begingroup$

To improve gzip compression, you want "similar" strings to be close in the list. There are a number of ways to define such a similarity; let me describe a reasonable one that works well in practice. Recall that gzip's block size is 64K. Thus, your data will be split into blocks of 64K bytes and every block will be compressed independently. Tho optimize compression, one would need to minimize the number of distinct k-mers (substrings of size k) in every block. The motivation is that all such substrings will be replaced with an identifier.

While the above problem is hard in theory (it is a variant of hypergraph partitioning), there exist fast practical algorithms. I would recommend LSH-like clustering that can be implemented with a single pass over your data. Notice that (alphabetically) sorting is another way to "cluster" similar strings together. However, specialized clustering algorithms can perform better.

An alternative is to use zstd, which is (i) faster, (ii) obtains higher compression ratios, and (iii) does not have limitations on the block size (and thus, compresses strings equally well irrespective of input ordering).

$\endgroup$
0
$\begingroup$

I saw an algorithm some time ago which maybe can be useful. It uses an edit distance algorithm to calculate the distance between each word. Thus, it builds a graph which each edge weight is this distance. Finally, it gets a order choosing a path which has the lowest sum of weights. Maybe it can improve gzip.

$\endgroup$
  • $\begingroup$ that doesn't sound tractable, but if someone does try it, please post a comment with your results $\endgroup$ – Jayen Mar 19 at 21:22
  • $\begingroup$ I'll try to test it. I'm curious about this problem. Besides that, why do you think it isn't tractable? $\endgroup$ – Rafael Ribeiro Mar 20 at 16:37
  • $\begingroup$ so far as i know, edit distance is O(nm), where n and m are the number of letters in the pair of strings and you have to do this for every pair of strings O(s^2), so if n=m, that's O(s^2 * n^2) which sounds intractable to me for 1.5 million strings. $\endgroup$ – Jayen Mar 20 at 23:55
  • $\begingroup$ Oh, I didn't concern about complexity that much because I thought your problem is to decrease binary size only. So this operation will occur more often, right? $\endgroup$ – Rafael Ribeiro Mar 21 at 16:01
  • $\begingroup$ I was searching here and maybe editdistance cost can be reduced using levenshtein automata $\endgroup$ – Rafael Ribeiro Mar 21 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.