Let's say I have a file with symbols of an alphabet [0,N-1], N around 50. The actual data is a file with a lot of lines, each containing 100 of these symbols.

I want to compress this data. By doing a frequency analysis over a large amount of lines to build a probability density function and then calculate the entropy you get far better than just log2(N), but yet it is not enough. Getting to the entropy is pretty easy as I'm using arithmetic coding and it really nails it, the problem is getting the model right...

I've tried using some contexts and it gets slightly better, but it is not computationally feasible to use models with the last 1000 symbols... so I'm basically looking for another approach.

Does it make sense to use Neural Networks? what would be the approach? I can't figure out what the inputs would be... perhaps the last K symbols, and the output the predicted one, then compress the error? Truth is I've never dealt with Neural Networks before.

Also, is there any way I can know if using a NN would indeed work better? Looking at the raw data it surely seems that there is some pattern... or at least sometimes...

  • 1
    $\begingroup$ How about standard compression algorithms, like those implemented by standard utilities? Say, Lempel–Ziv–Welch? Burrows–Wheeler? $\endgroup$ – Yuval Filmus Oct 26 '15 at 21:43
  • $\begingroup$ @YuvalFilmus They don't perform as well as a specific one (specific for this data). With Burrows it gets even worse than just using a context of 1. With my current implementation entropy is arround 2bits/symbol, and using general-purpose algorithms compress it to around 3bits/symbol. $\endgroup$ – Carlos Navarro Astiasarán Oct 26 '15 at 21:49
  • 1
    $\begingroup$ You might have to tell us more about the data – where does it come from? $\endgroup$ – Yuval Filmus Oct 26 '15 at 21:51
  • 1
    $\begingroup$ Your question sounds super-broad to me: it sounds like it is basically asking "How do I compress a file?" There's tons of research and methods and algorithms out there on that topic. One could write an entire book on the topic, and some people have. Have you read en.wikipedia.org/wiki/Data_compression and other overviews of standard methods for data compression? We expect you to do a significant amount of research before asking -- what research have you done? What is your specific question here? $\endgroup$ – D.W. Oct 26 '15 at 22:01
  • $\begingroup$ I don't think there's enough to go on, here. You have some data. Given only the information that it's kinda special so it should probably compress decently well, we have to figure out how to compress it. I don't see how anyone could make anything better than a guess at an answer. $\endgroup$ – David Richerby Oct 26 '15 at 22:38