<p>This is an addition to the Navin Goyal's answer.</p>

<p>Since a JSON file can be regarded as a tree data structure, you can use <a href="http://dl.acm.org/citation.cfm?id=1613680" rel="noreferrer">the XBW-transform</a> for trees, which is an extension of the Burrows-Wheeler transform for strings.</p>

CC BY-SA 3.0
2015-03-05T22:17:56.980Z
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.
Jayen
CC BY-SA 3.0
2015-03-05T15:21:51.070Z
2015-03-05T15:21:51.070Z
Hiroki Yanagisawa
<p><a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" rel="nofollow">Burrows--Wheeler transform</a> is a well-known compression algorithm that works by reordering the characters in the string to be compressed. </p>

CC BY-SA 3.0
2015-03-05T22:15:50.430Z
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.
Jayen
CC BY-SA 3.0
2015-03-05T09:15:47.090Z
2015-03-05T09:15:47.090Z
Navin Goyal
<p>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.</p>

CC BY-SA 4.0
2019-03-19T21:22:18.170Z
that doesn't sound tractable, but if someone does try it, please post a comment with your results
Jayen
CC BY-SA 4.0
2019-03-20T16:37:54.917Z
I'll try to test it. I'm curious about this problem. Besides that, why do you think it isn't tractable?
Rafael Ribeiro
CC BY-SA 4.0
2019-03-20T23:55:05.420Z
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.
Jayen
CC BY-SA 4.0
2019-03-21T16:01:54.900Z
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?
Rafael Ribeiro
CC BY-SA 4.0
2019-03-21T18:00:23.793Z
I was searching here and maybe editdistance cost can be reduced using levenshtein automata
Rafael Ribeiro
CC BY-SA 4.0
2019-03-22T00:00:34.347Z
the operation won't occur that often, but i would have liked it to have taken less than a day to run, which i don't know if your solution can do.
Jayen
CC BY-SA 4.0
2019-03-19T14:28:27.923Z
2019-03-19T14:28:27.923Z
Rafael Ribeiro
<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-06T09:38:57.867Z
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.
Jouni Sirén
CC BY-SA 3.0
2015-03-06T23:49:43.203Z
@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).
Jayen
<optimization><permutations>
Reordering data (set of strings) to optimize for compression?
Jayen
# Reordering data (set of strings) to optimize for compression?

(Asked by: username_0 on 2015-03-05)

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.

**Tags:** optimization, permutations

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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).  

---

## 3 answers

### Answer by username_2 on 2015-03-05. Score: 6

This is an addition to the username_3's answer.

Since a JSON file can be regarded as a tree data structure, you can use [the XBW-transform](http://dl.acm.org/citation.cfm?id=1613680) for trees, which is an extension of the Burrows-Wheeler transform for strings.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2015-03-05. Score: 3

[Burrows--Wheeler transform](http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform) is a well-known compression algorithm that works by reordering the characters in the string to be compressed.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_4 on 2019-03-19. Score: 0

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.

> **Comments:**
> **username_0**: that doesn't sound tractable, but if someone does try it, please post a comment with your results  
> **username_4**: I'll try to test it. I'm curious about this problem. Besides that, why do you think it isn't tractable?  
> **username_0**: 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.  
> **username_4**: 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?  
> **username_4**: I was searching here and maybe editdistance cost can be reduced using levenshtein automata  
> **username_0**: the operation won't occur that often, but i would have liked it to have taken less than a day to run, which i don't know if your solution can do.  

---

