7 ms·

Lossless Text Compression [pdf]

66 points by kronxe 6y ago

AnotherGoodName 5y ago
One thing I'd encourage looking at is dynamic Markov coding. It's easy enough to implement and gets you to 1/5th size for text compression. Still not at the ~6x ratio of the current best (paq8) but it's close. There's no dictionary involved. As you encode or decode you update the probabilities and build the dictionary on the fly and encode with arithmetic coding.
- woliveirajr 5y ago
  Prediction by partial match (PPM) is also very good. The "D" version, which comes within 7zip, gives very good compression. The longer the text and the more "common", the better.
- kronxe 5y ago
  Yes I think Markov coding also Markov chains is such good things to learn. But in this article my point is there should be stable dictionary because for big data purposes, especially in databases it is hard to calculate every time new probs.
quiescant_dodo 5y ago
Cool idea. I would expect the code to be very clean and simple for this, so I'm surprised there isn't a pseudocode algorithm presented (or a real implementation in some language).
- kronxe 5y ago
  These ideas all tested in Python and then I achieved results. I did not add codes because it is a 'philosophical' research for me actually.
spicybright 5y ago
What exactly is lossy text compression then? EDIT: I love every single answer below
- sodality2 5y ago
  Ths is losy tet comresio
  - faeyanpiraat 5y ago
    Que?
- theawless 5y ago
  d way v used 2 txt b4 on fb
- vincnetas 5y ago
  Yes, was thinking the same thing when read title. I prefere to have my Dostojevski the same after compression/decompression. But seriously, is loosy text compression a thing (useful)?
- elil17 5y ago
  "Why waste time say lot word when few word do trick?"
  - tobr 5y ago
    Or, to quote the article, “there is a necessity of knowing dictionary that used in compression process”.
  - leokennis 5y ago
    Words said I like. Button press up.
    - elil17 5y ago
      Thank.
meiji163 5y ago
My favorite is Context Tree Weighting (CTW) (https://ieeexplore.ieee.org/document/382012 https://ieeexplore.ieee.org/document/382012). Mathematically it's much nicer than PPM. Modern implementations of CTW achieve ratios close to or better than PPM in most domains (see e.g. P. Volf's Thesis "Weighting techniques in data compression")
- bayindirh 5y ago
  If you're compressing Turkish, you can use syllables. Turkish has a nice feature of deterministic syllable division, which can be done via a neat state machine. I've implemented it once, however I failed to encode it very efficiently on the disk. Nevertheless, it's promising. Here's what I've done: https://www.ccis2k.org/iajit/PDF/vol.8,no.1/12.pdf https://www.ccis2k.org/iajit/PDF/vol.8,no.1/12.pdf
123pie123 5y ago
I've always thought could you compress english text easily by getting the top X number of words/phrases and then using rarely used ascii letters/ combinations to represent those words. Then extending this concept for the remainding words using the most commonly used word groups (eg -ight) I've been too way too busy (cough.. lazy) to test this idea
- compressedgas 5y ago
  That's what Re-Pair does. It repeatedly replaces the most frequent substring with a symbol until the input has no repeating substrings. See https://en.wikipedia.org/wiki/Grammar-based_code https://en.wikipedia.org/wiki/Grammar-based_code
  - kwhitefoot 5y ago
    I had to do this by hand in the 1980s when I ran out of space in the ROM of the embedded controller I was working on for messages to be printed. There was no way to increase the size of ROM (2716 EPROM) at that stage in the development. The text was all 7 bit ASCII so I used the MSB as a flag to say that the remaining bits were a pointer into a table of frequently used fragments. This saved enough space to include the decompressor; it was recursive too so the fragments could also be compressed.
- web007 5y ago
  This is how LZW and Huffman compression work. LZW finds repeated symbol groups and encodes them as new symbols, and Huffman compression codes frequent symbols with fewer bits and infrequent symbols with more bits.
lifthrasiir 5y ago
I can't tell if this post is presenting a trivial idea as a novel one or not. Typical compression algorithms indeed are not good at compressing a short text, but only because they have no prior knowledge about the input distribution. There are several ways to feed that knowledge to existing algorithms (e.g. zstandard custom dictionaries). The "Type-Based Compression Algorithm" presented in the post does not do any kind of distribution modelling. It simply assumes that every possible input is uniformly distributed, hence incompressible, and that's obviously not true. The post gives an example of Turkish car number plates; its first two digits indicate the province code, so you will see certain two-digit prefixes more frequently. TBCA can't see this distribution. TBCA can also try to limit the range of first two digits for the better coding, but it will break with a new province code. Typical compression algorithms might be inefficient for those inputs but can surely handle them. This is perhaps the biggest drawback of TBCA: a wrong assumption of the input data results in a hard failure (unless you have an escape code). It is not the same kind of algorithm you can compare with general compression algorithms. It is just a clever database schema that gives some compression without those general compression algorithms.
- kronxe 5y ago
  My one of the main goals is protect the database structure as it is, because in big data age we should get data as fast as possible. I see your point to see this algorithm as a basically some sort of look-up table but actually it is not. For example, we can think a well-developed city carries all data related to the city and the people to a big database. Then this city uses a TBCA that specialized for only the this big database's needs like a framework or engine method. However, this specific TBCA is not totally different than other TBCAs used in other types of databases like a game database since they have common propertries like people's names and surnames, the structure of a name database is generally same but TBCA plays huge rol in here, you can configure your algorithm with your needs like an optimizing. Today I am not sure how it should be done, maybe with an ML algorithm. I wrote too much I know but my point is TBCA is not an specific algorithm like gzip or LZW it is a sub branch of compression like an universal set. In the future, There may communities share their specificated algorithms for some structures and their datasets( frequency analysis). It will becomes a pool that you can choose best engine(structural method) and best dataset(freq. analysis) from there.
jokoon 5y ago
Isn't possible to achieve a great compression ratio when you recognize grammar forms? Statistical compression seems a little random and unpredictable.
- kronxe 5y ago
  It is possible and actively used but in this article my point is like an universal engine for ,big data and databases that need speed, as I mentioned in name Type-based. You cannot used a grammar algorithm in only number based data.
kronxe 5y ago
By the way, I want to add something. I do not use any codes in paper but I tested these all in Python and they can be implemented in most languages. Also, my other point is it is not an stable, constant algorithm. Everyone may have different TBCAs for their specific purposes but there should be generic ideas like human names or in an online game if you give '~' for 'GG' , you can save too many locations in memory. For a chat application, if you change 'hello' to some two bytes and you save both memory and time (because transmission of long bytes takes more than compression process probably if you dont have a huge dictionary).

66 points by kronxe 6y ago

One thing I'd encourage looking at is dynamic Markov coding. It's easy enough to implement and gets you to 1/5th size for text compression. Still not at the ~6x ratio of the current best (paq8) but it's close. There's no dictionary involved. As you encode or decode you update the probabilities and build the dictionary on the fly and encode with arithmetic coding.

woliveirajr 5y ago
Prediction by partial match (PPM) is also very good. The "D" version, which comes within 7zip, gives very good compression. The longer the text and the more "common", the better.
kronxe 5y ago
Yes I think Markov coding also Markov chains is such good things to learn. But in this article my point is there should be stable dictionary because for big data purposes, especially in databases it is hard to calculate every time new probs.

quiescant_dodo 5y ago

Cool idea. I would expect the code to be very clean and simple for this, so I'm surprised there isn't a pseudocode algorithm presented (or a real implementation in some language).

kronxe 5y ago
These ideas all tested in Python and then I achieved results. I did not add codes because it is a 'philosophical' research for me actually.

spicybright 5y ago

What exactly is lossy text compression then? EDIT: I love every single answer below

sodality2 5y ago
Ths is losy tet comresio
- faeyanpiraat 5y ago
  Que?
theawless 5y ago
d way v used 2 txt b4 on fb
vincnetas 5y ago
Yes, was thinking the same thing when read title. I prefere to have my Dostojevski the same after compression/decompression. But seriously, is loosy text compression a thing (useful)?
elil17 5y ago
"Why waste time say lot word when few word do trick?"
- tobr 5y ago
  Or, to quote the article, “there is a necessity of knowing dictionary that used in compression process”.
- leokennis 5y ago
  Words said I like. Button press up.
  - elil17 5y ago
    Thank.

meiji163 5y ago

My favorite is Context Tree Weighting (CTW) (https://ieeexplore.ieee.org/document/382012 https://ieeexplore.ieee.org/document/382012). Mathematically it's much nicer than PPM. Modern implementations of CTW achieve ratios close to or better than PPM in most domains (see e.g. P. Volf's Thesis "Weighting techniques in data compression")

bayindirh 5y ago
If you're compressing Turkish, you can use syllables. Turkish has a nice feature of deterministic syllable division, which can be done via a neat state machine. I've implemented it once, however I failed to encode it very efficiently on the disk. Nevertheless, it's promising. Here's what I've done: https://www.ccis2k.org/iajit/PDF/vol.8,no.1/12.pdf https://www.ccis2k.org/iajit/PDF/vol.8,no.1/12.pdf

123pie123 5y ago

I've always thought could you compress english text easily by getting the top X number of words/phrases and then using rarely used ascii letters/ combinations to represent those words. Then extending this concept for the remainding words using the most commonly used word groups (eg -ight) I've been too way too busy (cough.. lazy) to test this idea

compressedgas 5y ago
That's what Re-Pair does. It repeatedly replaces the most frequent substring with a symbol until the input has no repeating substrings. See https://en.wikipedia.org/wiki/Grammar-based_code https://en.wikipedia.org/wiki/Grammar-based_code
- kwhitefoot 5y ago
  I had to do this by hand in the 1980s when I ran out of space in the ROM of the embedded controller I was working on for messages to be printed. There was no way to increase the size of ROM (2716 EPROM) at that stage in the development. The text was all 7 bit ASCII so I used the MSB as a flag to say that the remaining bits were a pointer into a table of frequently used fragments. This saved enough space to include the decompressor; it was recursive too so the fragments could also be compressed.
web007 5y ago
This is how LZW and Huffman compression work. LZW finds repeated symbol groups and encodes them as new symbols, and Huffman compression codes frequent symbols with fewer bits and infrequent symbols with more bits.

lifthrasiir 5y ago

I can't tell if this post is presenting a trivial idea as a novel one or not. Typical compression algorithms indeed are not good at compressing a short text, but only because they have no prior knowledge about the input distribution. There are several ways to feed that knowledge to existing algorithms (e.g. zstandard custom dictionaries). The "Type-Based Compression Algorithm" presented in the post does not do any kind of distribution modelling. It simply assumes that every possible input is uniformly distributed, hence incompressible, and that's obviously not true. The post gives an example of Turkish car number plates; its first two digits indicate the province code, so you will see certain two-digit prefixes more frequently. TBCA can't see this distribution. TBCA can also try to limit the range of first two digits for the better coding, but it will break with a new province code. Typical compression algorithms might be inefficient for those inputs but can surely handle them. This is perhaps the biggest drawback of TBCA: a wrong assumption of the input data results in a hard failure (unless you have an escape code). It is not the same kind of algorithm you can compare with general compression algorithms. It is just a clever database schema that gives some compression without those general compression algorithms.

kronxe 5y ago
My one of the main goals is protect the database structure as it is, because in big data age we should get data as fast as possible. I see your point to see this algorithm as a basically some sort of look-up table but actually it is not. For example, we can think a well-developed city carries all data related to the city and the people to a big database. Then this city uses a TBCA that specialized for only the this big database's needs like a framework or engine method. However, this specific TBCA is not totally different than other TBCAs used in other types of databases like a game database since they have common propertries like people's names and surnames, the structure of a name database is generally same but TBCA plays huge rol in here, you can configure your algorithm with your needs like an optimizing. Today I am not sure how it should be done, maybe with an ML algorithm. I wrote too much I know but my point is TBCA is not an specific algorithm like gzip or LZW it is a sub branch of compression like an universal set. In the future, There may communities share their specificated algorithms for some structures and their datasets( frequency analysis). It will becomes a pool that you can choose best engine(structural method) and best dataset(freq. analysis) from there.

jokoon 5y ago

Isn't possible to achieve a great compression ratio when you recognize grammar forms? Statistical compression seems a little random and unpredictable.

kronxe 5y ago
It is possible and actively used but in this article my point is like an universal engine for ,big data and databases that need speed, as I mentioned in name Type-based. You cannot used a grammar algorithm in only number based data.

kronxe 5y ago

By the way, I want to add something. I do not use any codes in paper but I tested these all in Python and they can be implemented in most languages. Also, my other point is it is not an stable, constant algorithm. Everyone may have different TBCAs for their specific purposes but there should be generic ideas like human names or in an online game if you give '~' for 'GG' , you can save too many locations in memory. For a chat application, if you change 'hello' to some two bytes and you save both memory and time (because transmission of long bytes takes more than compression process probably if you dont have a huge dictionary).